rhopollard

/*
    @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;
}