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

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

22.09.2012, 10:19. Просмотров 1722. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n) (C#):

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

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

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

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

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

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

4
Psilon
Master of Orion
Эксперт .NET
5981 / 4834 / 901
Регистрация: 10.07.2011
Сообщений: 14,439
Записей в блоге: 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
5981 / 4834 / 901
Регистрация: 10.07.2011
Сообщений: 14,439
Записей в блоге: 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