Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n) - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток) Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n).
 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));
 
        }
Дело в том, что не всегда удается получить корректные значения p и q. Например, при n=4, при n=10. Помогите разобраться

Решение задачи: «Необходимо реализовать алгоритм Полларда (алгортим факторизации числа 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));
 
        }
 
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 4.067 из 5
Похожие ответы