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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
fort-_-minor
6 / 6 / 2
Регистрация: 30.07.2010
Сообщений: 87
11.08.2010, 19:54     ро-метод Полларда #1
Здравствуйте! Задание такое: Реализовать ро-метод Полларда факторизации челых чисел на примере 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++
C++ блок-схема к ро-методу Полларда
метод деления отрезка пополам и метод итерации C++
Есть метод класса внутри , есть проверка. Если условие сходится то метод должен выдать указатель, иначе булевую переменную C++
Метод Эйлера, и Метод Лагранжа, в долгу не останусь C++
C++ Метод оптимизации. Метод Фибоначчи
C++ Как передать в метод класса Menu указатель на метод дочернего класса?

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

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

Сам оригинал (думаю не понадобится):
ссылка удалена
 Комментарий модератора 
прикрепляйте архив к сообщению
Вложения
Тип файла: zip main.zip (729 байт, 175 просмотров)
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     ро-метод Полларда
Ответ Создать тему
Опции темы

Текущее время: 20:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru