Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/10: Рейтинг темы: голосов - 10, средняя оценка - 4.60
ro0t
5 / 5 / 1
Регистрация: 13.02.2011
Сообщений: 48
1

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

22.09.2012, 10:19. Просмотров 1790. Ответов 4
Метки нет (Все метки)

Доброго времени суток)
Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n).
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 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.
Помогите разобраться
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2012, 10:19
Ответы с готовыми решениями:

Алгоритм факторизации. Курсач горит
Здравствуйте. У меня такая проблема: Я делаю курсовую, называется &quot;Вычисление...

Метод факторизации Полларда (p-1)
Весь форум облазил но не нашёл, пришлось зарегаться. Очень нужно реализовать...

Нужно реализовать Ро-алгоритм Полларда
Ребят вообщем нужно реализовать этот алгоритм.. Но что то я не пойму как......

Необходимо реализовать алгоритм в Маткаде
Здравствуйте, в Маткаде практически не работал, но вот пришлось с ним...

Необходимо реализовать расширенный алгоритм Евклида
Добрый вечер человеки! Необходимо реализовать расширенный алгоритм...

4
Psilon
Master of Orion
Эксперт .NET
6000 / 4850 / 902
Регистрация: 10.07.2011
Сообщений: 14,460
Записей в блоге: 5
Завершенные тесты: 4
23.09.2012, 01:41 2
ro0t,
C#
1
 b = a % (a = b);
а разве шарп вообще такое ест? Какая-то сишная запись
0
escapist
6 / 6 / 1
Регистрация: 21.09.2012
Сообщений: 12
23.09.2012, 22:46 3
Цитата Сообщение от Psilon Посмотреть сообщение
ro0t,
C#
1
 b = a % (a = b);
а разве шарп вообще такое ест? Какая-то сишная запись
все ок, красивое вычисление НОД
я бы перебросил
int nd = 0;
внутрь метода plrd
это правда не решает всех проблем
0
Psilon
Master of Orion
Эксперт .NET
6000 / 4850 / 902
Регистрация: 10.07.2011
Сообщений: 14,460
Записей в блоге: 5
Завершенные тесты: 4
23.09.2012, 22:48 4
escapist, нет, я в курсе, что в С такое можно записать, но я думал, что кроме return (a=b) он такое не любит. А то в цикле когда я пробовал вещи типа
C#
1
while((a=a.Next) != null)
он ругался
0
escapist
6 / 6 / 1
Регистрация: 21.09.2012
Сообщений: 12
24.09.2012, 01:18 5
Цитата Сообщение от Psilon Посмотреть сообщение
escapist, нет, я в курсе, что в С такое можно записать, но я думал, что кроме return (a=b) он такое не любит. А то в цикле когда я пробовал вещи типа
C#
1
while((a=a.Next) != null)
он ругался
вот мой коротенький примерчик для установления разницы между & и && :

C#
1
 bool a ; Console.WriteLine((a=false) & (a = true) ? true : a);


Добавлено через 12 минут
Не силен в алгоритме Полларда и у меня нет уверенности, что он всегда может найти множители непростого числа. Т.е. без повторных прогонов. Но если его повторять, то когда следует остановиться и решить, что число простое?

вот мой вариант без использования массивов (но проблема остается):

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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));
 
        }
 
    }
}
1
24.09.2012, 01:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2012, 01:18

Необходимо реализовать алгоритм обмена ключами по схеме Диффи-Хеллмана
Заранее благодарен

ро-метод Полларда (факторизация числа)
Доброго времени суток! Необходимо написать ро-алгоритм Полларда. Взял Кнута с...

Необходимо реализовать на машине Тьюринга умножение на 9 целого троичного числа.
помогите решить задание в машине Тьюринга Необходимо реализовать умножение на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru