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

[fort-_-minor]

Здравствуйте. Задание такое: Реализовать Ро-метод факторизации целых чисел Полларда на примере 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 − λ

Спасибо.

[Tema_Crazzzy]

Сообщение от fort-_-minor

Есть давно написаный код на Паскале

Так в чем проблема то??? Берете отдельные блоки программы на Паскале и переписываете используя команды Си. Если знаний по командам не хватает спрашиваем гугл или качаем справочник по командам Си++

[fort-_-minor]

Как бы тебе по вежливей обьяснить Тема_Крэйзи. Если ты считаешь что самоутвердишься перед кем то если набьеш n-ое количество постов я тебя огорчу кроме твоего еб..анс..ва это ничего не доказывает. По поводу твоего ценного совета - неужели ты думаешь что я ничего не читал по этой теме и тд? Это тема моего курсового, а до этого я никогда не писал на с++ щас вот слава Богу начинаю разбираться понемногу. Ты вот попробуй перевести текст с немецкого на английский с помощью словаря скажем страницы 3 для начала с помощью словаря. Так вот не зная структуры языка ты этого никогда не сделаешь правильно как бы ты не пытался. А в программировании помимо символов прибавляется высшая математика, математический анализ, теория чисел групп и колец и так далее, которые сидишь по 8 часов в день разбираешь а потом понимаешь понимать хоть немного. Ну да ладно я твой совет буду считать неудачной шуткой. Хм еще поставлю такой же дебильный смайлик может дойду до уровня просветительства как у тебя

[Tema_Crazzzy]

Студент!!!! Курсовая!!!! Понимаю)))) Твое сообщение тоже буду считать НАИГЛУПЕЙШЕЙ шуткой))) Если че стучись в аську - помогу чем смогу! За личку сори - тож погорячился)

[fort-_-minor]

Вот такой код получается но что то в нем неправильно. Если кому не трудно распишите пожалуйста алгорит действия и что программа должна на экран выводить как резалт:

#include <stdafx.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define abs(a) ((a) > 0? (a):-(a))
#define min(a,b) ((a)<(b)? (a):(b))
#define max(a,b) ((a)>(b)? (a):(b))
#define sqr(a) ((a)*(a))

typedef long long LL;
typedef unsigned long long uint64;
typedef long double ldbl;

LL gcd(LL a,LL b)
{
	while(b)
	{
		LL d = a/b;
		LL tmp = b;
		b = a - b*d;
		a = tmp;
	}
	return a;
}

LL s(LL a)
{
	LL ans = 0;
	while(a)
	{
		a/=2;
		ans++;
	}
	return ans;
}

LL modular_exponentation(LL a,LL b,LL n)
{
	LL c=0;
	LL d=1;
	for(int i=s(b)-1;i>=0;--i)
	{
		c*=2;
		d=((LL)(d*d))%n;
		if((b>>i)&1)
		{
			c++;
			d=((LL)(d*a))%n;
		}
	}
	return d;
}

void Pollard_Rho(LL n)
{
	LL RANGE_MIN = 0;
    LL RANGE_MAX = n-1;
	LL i = 1;
	LL x = (((double) rand() / 
                         (double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
	LL y = x;
	LL k = 2;
	while(1)
	{
		i++;
		//x = modular_exponentation(x,2,n);
		x = (x*x-1)%n;
		LL d = gcd(y - x,n);
		d = abs(d);
		if(d!=1&&d!=n)
			printf("%d\n",d);
		if(i==k)
		{
			y = x;
			k<<=1;
		}
	}

}

int main()
{
	srand(time(NULL));
	LL t = (LL)2*3*5*7*11*13*17*19*23*29*31*37*41*43;
	Pollard_Rho(t);


	return 0;
}

Заранее большое спасибо.

[fort-_-minor]

up!

[fort-_-minor]

up