/*
@Author : Joel Fernandez
@web : Codebotic.blogspot.com
@Fecha : 30/06/2015
@Tema : Implementacion del Algoritmo Rho Pollard
(Factorizacion de numeros enteros)
*/
#include<iostream>
#include<cstdlib>
using namespace std;
/* Funcion que saca el valor absoluto a
un numero */
long long int absoluto( long long int n)
{
if(n>=0)
{
return n;
}
else
{
n = -n;
return n;
}
}
/* Funcion que saca el Maximo Comun
Divisor por Euclides a un numero */
long long int mcd(long long int a,long long int b )
{
if(b==0)
return a;
else
mcd(b,a%b);
}
/* Algoritmo Rho Pollard */
int rho_pollard(int n)
{
long long int a,b,d,e;
int i;
bool band;
a=2;
b=2;
i = 1;
band= false;
while(band==false)
{
a = (a*a+1)%n;
b = (b*b+1)%n;
b = (b*b+1)%n;
e=absoluto(a-b);
d= mcd(e,n);
cout<<"\\n\\t i = "<<i;
cout<<"\\n\\t\\t a: "<<a;
cout<<"\\n\\t\\t b: "<<b;
cout<<"\\n\\t\\t d = mcd("<<e<<","<<n<<"):"<<d;
if(1<d&&d<n)
{
band = true;
return d;
}
if(d>=n)
{
band = true;
return -1;
}
i++;
}
}
int main(void)
{
system("color 0a");
int x,n;
cout<<"\\t ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»"<<endl;
cout<<"\\t º º"<<endl;
cout<<"\\t º Algoritmo Rho de Pollard º"<<endl;
cout<<"\\t º º"<<endl;
cout<<"\\t ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ "<<endl;
cout<<endl<<endl;
cout<<"\\n\\tIngrese un numero: ";
cin>>n;
x = rho_pollard(n);
if(x!=-1)
{
cout<<"\\n\\n\\t El Primer Factor es: "<<x;
cout<<"\\n\\t El Segundo Factor es:"<<n/x;
cout<<endl;
}
else
{
cout<<"\\n\\tNumero no Factorizable...";
cout<<endl;
}
return 0;
}