Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.08.2010, 19:54. Просмотров 3675. Ответов 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2010, 19:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос ро-метод Полларда (C++):

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

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

СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя - C++
Помогите ребят. Не могу построить алгоритмы для этих методов Язык C++

Метод медиан из трех элементов VS улучшенный быстрый метод сортировки(метод Бентли-Макилроя) - C++
Здравствуйте! Дали весьма интересное задание. Сравнить два вышеуказанных метода сортировки для массива из 10000 элементов, результаты...

Мой код - метод бисекции, метод секущих (метод хорд) - C++
Всем привет!!! Изучаем в институте С++. Сделал код, и там, и там одна и та же проблема - при любых вбиваемых значениях программа делает...

Исследовать итерационный метод- метод касательных для решения нелинейных уравнений - C++
прочитал много всего , но сам пример реализовать никак не могу , кто может помогите F(x) = x5+5x+1=0 с...

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

Сам оригинал (думаю не понадобится):
ссылка удалена
 Комментарий модератора 
прикрепляйте архив к сообщению
2
Вложения
Тип файла: zip main.zip (729 байт, 183 просмотров)
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
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2010, 18:21
Привет! Вот еще темы с ответами:

Не сходится теория и практика метод Шелла и метод простого выбора - C++
Здравствуйте! Помогите пожулуйста найти ошибке в коде, Я уже не знаю где ее искать. У меня метод простого выбора работает по показателям...

Нахождения корней уравнения: метод половинного деления (бисекции) или метод хорд - C++
Разработать программу нахождения корней уравнения f(x) =0 на интервале с точностью e = 0,001 (интервал или подобрать самостоятельно). При...

Метод деления отрезка пополам для решения нелинейных уравнений (метод дихотомии) - C++
Здравствуйте. Помогите пожалуйста дописать программу. Вот что вымучал, но на сдаче завалили, типо нет вывода корней, не рассмотрены...

Производный класс: метод возведения в произвольную степень, и метод для вычисления логарифма числа - C++
Реализовать класс-оболочку Number для числового типа float. Реализовать методы сложения и деления. Создать производный класс Real, в...


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

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

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