Алгоритм факторизация числа (ρ-метод Полларда )

C++   7 января 2012  Автор статьи:  

P-метод Полларда служит для факторизации целых чисел.Факторизация-разложение числа в его простые множители.

Входные данные:

Вводится только начальное число,которое надо разложить.

Выходные данные:

На выводе будут показаны числа-разложение числа по простым множителям.

Реализация решения

Теоретическая база алгоритма такова

Пусть надо разложить на множители число 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. [cc lang="cpp" lines="-1"] #include

#include

#include

#include

#include

using namespace std;

bool prostota(int a)

{int k=0;

for(int i=1;i<=a;i++) if((a%i==0)) k++; if (k==2) return true; else return false; } unsigned int fun(int a,int n) { return (((a*a)+1)%n); } bool finduniq(int a[101],int b) { int k=0; for(int i=0;i<101;i++) if(a[i]==b) k++; if (k>1) return false;

else return true;

}

int NOD(int a,int b)//ищем нод

{int bol,men;

if (a>=b){bol=a;men=b;}

else {bol=b;men=a;}

int ostatok=0;

while ((bol!=0)&amp;&amp;(men!=0))

{if (bol>=men) {ostatok=bol;bol=bol-men;}

if(men>bol) {ostatok=men;men=men-bol;}

}

return ostatok;

}

int find_uniqrazlog(int b[90],int osn)

{

srand(time(0));

int kolvo=0;

int posl[101];

for(int i=0;i<101;i++) posl[i]=0; posl[0]=rand() % osn; int i=1,j=1; posl[i]=fun(posl[i-1],osn); while ((j<25)&amp;&amp;(kolvo!=4)) { posl[j]=(fun(posl[j-1],osn)); if (finduniq(posl,posl[j-1])){b[i]=posl[j-1]; i++;} else kolvo++; j++;} return i-1;} int osnov_nod(int m[90],int os,int k) { int raz; for(int i=0;i>osnov;

int k=0;

int tmp=0;

int gh=0;

int mnog[100];

int uniq[90];

int razlog[500];

for(int i=0;i<500;i++)razlog[i]=0; int posled[101]; for(int i=0;i<90;i++) {mnog[i]=0;uniq[i]=0;posled[i]=0;} while(prostota(osnov)!=1) { int kolvouniq; kolvouniq=find_uniqrazlog(uniq,osnov); mnog[tmp]=osnov_nod(uniq,osnov,kolvouniq); if(((mnog[tmp])!=1)&amp;&amp;((mnog[tmp]!=0))){razlog[k]=mnog[tmp];k++; gh=mnog[tmp]; osnov=osnov/gh; tmp++;} } for(int i=0;i

Научиться программировать

  • на Delphi

  • на Java

  • на C++