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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Быстрое умножение длинных чисел. http://www.cyberforum.ru/cpp-beginners/thread158519.html
В общем вопрос стоит так: где можно найти красивый код на агоритм Карацубы. В часности - http://acm.tju.edu.cn/toj/vcontest/showp6506_I.html - это задача, на которой я все время получаю вронги, вот код: #include <iostream> #include <sstream> #include <string> #include <vector> #include <map> #include <set> #include <algorithm> #include <limits> #include <iomanip>
C++ Почему нет реакции от DllMain? Доброго времени суток! Начал изучать dll, и возникла такая проблема - библиотека загружается, функции экспортируются. А вот DLL_PROCESS_ATTACH не срабатывает, как и остальные(DLL_PROCESS_DETACH, DLL_THREAD_ATTACH...) BOOL APIENTRY DllMain (HINSTANCE hInst /* Library instance handle. */ , DWORD reason /* Reason this function is being called. */ , ... http://www.cyberforum.ru/cpp-beginners/thread158517.html
Как перевести double в char? C++
как перевести double в char?
есть массив char. есть строка string. как присвоить значению string-a значение char-a? C++
есть массив char. есть строка string. как присвоить значению string-a значение char-a?
C++ Открытие проекта в ERS 2010 http://www.cyberforum.ru/cpp-beginners/thread158475.html
Здравствуйте. Как сделать так, чтобы при открытии проекта (Ctrl+F11) открывались и исходники данного проекта? При открытии проекта так и остаюсь на "Welcome Page", после открытия нужно открывать каждый исходник по отдельности через Open. Что нужно настроить?
C++ Использование strcpy_s Добрый день. Словил странную проблему (компилятор MVS2010) #include<iostream> #include<cstring> using namespace std; class String { private: char *stroka; public: подробнее

Показать сообщение отдельно
fort-_-minor
6 / 6 / 2
Регистрация: 30.07.2010
Сообщений: 87

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

11.08.2010, 19:54. Просмотров 3461. Ответов 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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru