Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
fort-_-minor
6 / 6 / 2
Регистрация: 30.07.2010
Сообщений: 87
#1

ро-метод Полларда - C++

11.08.2010, 19:54. Просмотров 3453. Ответов 2
Метки нет (Все метки)

Здравствуйте! Задание такое: Реализовать ро-метод Полларда факторизации челых чисел на примере 32 битовых чисел. Давно есть код сделаный на Паскале вот как это сделать на с++ подскажите пожалуйста
Если кому вдруг чем то поможет код на Паскале скину. По поводу ро-метода Полларда собственно вот из википедии если вдруг кто не знаком с темой
ρ-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основан на том, что вычисляется некий многочлен степени не выше второй от начального числа Х — f(X).
[править]
Описание алгоритма

Пусть надо разложить на множители число P
Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2. Обычно берется многочлен вида y = x2 + c(mod P).
Шаг 2. Случайно выбирается x0 = y0 меньше P.
Шаг 3. Вычисляются значения xi = f(xi − 1)(modP),yi = f(f(yi − 1))(modP).
Шаг 4. Находится d = ( | xi − yi | ,P).
Шаг 5. Если d = 1, происходит переход на шаг 3, если d = P, происходит остановка - факторизацию провести не удалось. Если 1 < d < P, то найдено разложение числа P.


[править]
Альтернативное описание
Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2 и целое число m.
Шаг 2. Случайно выбирается x0 меньше P.
Шаг 3. Вычисляются значения xi = f(xi − 1)(modP).
Шаг 4. Для h = 0,1,...,[logm] полагаем j = 2h − 1 и для каждого 2h < = k < 2h + 1 вычисляем d = ( | xj − xk | ,P). Если 1 < d < P, то нетривиальный делитель числа n найден. Если d=1 или d=P, то переходим к следующему значению h.
[править]
Сложность алгоритма

Пусть n — составное число. Тогда существует такая константа C, что для любого положительного числа λ вероятность события, состоящего в том, что ρ-метод Полларда не найдет нетривиального делителя n за время , не превосходит величины e − λ
Заранее спасибо

Добавлено через 22 часа 3 минуты
up
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2010, 19:54     ро-метод Полларда
Посмотрите здесь:

блок-схема к ро-методу Полларда - C++
Доброго времени суток. Есть программа, нужно нарисовать к ней блок-схему. Собственно далек от этого дела, поэтому помогите пожалуйста если...

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

Метод пузырька и метод слияния - C++
Сгенерировать одномерный массив из N случайных чисел xi ∈. Отсортировать массив методом пузырька и методом слияния. Подсчитать число...

Метод итераций и метод Зейделя - C++
Здравсвуйте программисты! Спасибо всем за помощь в предыдущих темах, осталась последняя лаба, которую нужно решить по предмету &quot;Численные...

Метод оптимизации. Метод Фибоначчи - C++
Дан отрезок минимизации и точность минимизации Е=0.01. Помогите пожалуйста решить данную задачу. Вроде как то через цикл надо все это...

Есть метод класса внутри , есть проверка. Если условие сходится то метод должен выдать указатель, иначе булевую переменную - C++
Есть метод класса внутри которого, посередине, есть проверка. Если условие сходится то метод должен выдать указатель на вектор, а если нет...

Описать метод Эйлера и обратный метод Эйлера - C++
Может кто помочь с методом &quot;обратный метод Эйлера(Backward Euler)&quot; как его описать? форлуму знаю, а вот как в самом коде - прямой...

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

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

ро-метод Полларда дискретного логарифмирования - C (СИ)
Добрый день. Задача: Элемент a имеет порядок q по модулю p. Найти дискретный логарифм x - такое целое число 1&lt;x&lt;q, что a^x = b (mod...

Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n) - C#
Доброго времени суток) Необходимо реализовать алгоритм Полларда (алгортим факторизации числа n). public partial class Form1 : Form ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,824
Завершенные тесты: 2
11.08.2010, 20:36     ро-метод Полларда #2
Нарыл кое-что в китайской помойке. См. вложение.
Скажу сразу, что пример нерабочий (неправильно реализован алгоритм, нужно где-то поправить) и может быть не по вашей теме.
В отличие от оригинала, который писал какой-то китаец, в нем более менее понятно что/зачем.

Сам оригинал (думаю не понадобится):
ссылка удалена
 Комментарий модератора 
прикрепляйте архив к сообщению
Вложения
Тип файла: zip main.zip (729 байт, 179 просмотров)
fort-_-minor
6 / 6 / 2
Регистрация: 30.07.2010
Сообщений: 87
13.08.2010, 18:21  [ТС]     ро-метод Полларда #3
Cпасибо большое, еще вопрос такой нубской а что должна программа показать на экран то есть мы вводим с клавиатуры число размером не более 32 бит а она выдает для него ключ дешифрования то ли шифрования, либо для каких то поределенных чисел, пример 32 битовых чисел есть во многих источниках. Признаю свое нубство в этом вопросе все это было в моих лекциях по спец розделам программирования на которые я благополучно появлялся раз в пять лет на протяжении семестра щас вот понял что это моя основная специальность начал учить просто программирование с++ вроде разобрался как мне кажется неплохо, длеаю все лабы что были в семестре всех вариантов ну и кое что стал соображать потихоньку. Разобраться с кодом думаю не составит труда главное знать что он должен выводить то на экран не прошу что то исправлять или еще что то делать просто скажите пожалуйста как оно работать должно вроде разобрался алгоритм не такой то и сложный Спасибо.

Добавлено через 14 часов 44 минуты
up

Добавлено через 6 часов 50 минут
up

Добавлено через 23 часа 5 минут
up
Yandex
Объявления
13.08.2010, 18:21     ро-метод Полларда
Ответ Создать тему
Опции темы

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