Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n) - C#
Формулировка задачи:
Доброго времени суток)
Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n).
Дело в том, что не всегда удается получить корректные значения p и q. Например, при n=4, при n=10.
Помогите разобраться
public partial class Form1 : Form { int n; int nd = 0; public Form1() { InitializeComponent(); } int gcd(int a, int b) { while (b != 0) b = a % (a = b); return a; } Point plrd(int n) { int p = 0; int q = 0; Random rnd = new Random(); int x0 = rnd.Next(2, n); int k = 0; //M = n; int[] x = new int[200]; for (k = 1; nd<n; ++k) { x[k] = ((x0) * (x0) + 1) % n; x0 = x[k]; if (k % 2 == 0) { int j = k / 2; nd = gcd(n, Math.Abs(x[k] - x[j])); if (nd != 1) { if (nd < n) { p = nd; q = n / p; Point a = new Point(p, q); return a; } else { plrd(n); } } } } return new Point(); } private void button1_Click(object sender, EventArgs e) { try { n = Convert.ToInt32(textBox1.Text); } catch { MessageBox.Show("Введите корректное значение", "Error!"); } Point c = plrd(n); int p = c.X; int q = c.Y; MessageBox.Show(Convert.ToString(p)); MessageBox.Show(Convert.ToString(q)); }
Решение задачи: «Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n)»
textual
Листинг программы
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Pillard { public partial class Form1 : Form { int n; int z = 0; public Form1() { InitializeComponent(); } int gcd(int a, int b) { while (b != 0) b = a % (a = b); return a; } Point plrd(int n) { int i = 1; int nd = 0; int p = 0; int q = 0; Random rnd = new Random(); int x0 = rnd.Next(2, n); int k = 2; int x = x0; while (true) { i++; x = (x*x + 1) % n; int xx = Math.Abs(x0 - x); nd = gcd(n,xx); if (nd != 1) { if (nd < n) { p = nd; q = n / p; Point a = new Point(p, q); return a; } else { return new Point(); //return plrd(n); } } if (i==k) { x0 = x; k *= 2; } } } private void button1_Click(object sender, EventArgs e) { try { n = Convert.ToInt32(textBox1.Text); } catch { MessageBox.Show("Введите корректное значение", "Error!"); } Point c = plrd(n); int p = c.X; int q = c.Y; MessageBox.Show(Convert.ToString(p)); MessageBox.Show(Convert.ToString(q)); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д