www.pudn.com > miracl.zip > BRENT_MT.C

/* 
 *   Program to factor big numbers using Brent-Pollard method. 
 *   See "An Improved Monte Carlo Factorization Algorithm" 
 *   by Richard Brent in BIT Vol. 20 1980 pp 176-184 
 * 
 *   Copyright (c) 1988-1997 Shamus Software Ltd. 
 */ 
 
#include  
#include  
 
#define mr_min(a,b) ((a) < (b)? (a) : (b)) 
 
int main() 
{  /*  factoring program using Brents method */ 
    long k,r,i,m,iter; 
    big x,y,z,n,q,ys,c3; 
    miracl *mip=mirsys(50,0); 
    x=mirvar(mip,0); 
    y=mirvar(mip,0); 
    ys=mirvar(mip,0); 
    z=mirvar(mip,0); 
    n=mirvar(mip,0); 
    q=mirvar(mip,0); 
    c3=mirvar(mip,3); 
    printf("input number to be factored\n"); 
    cinnum(mip,n,stdin); 
    if (isprime(mip,n)) 
    { 
        printf("this number is prime!\n"); 
        return 0; 
    } 
    m=10L; 
    r=1L; 
    iter=0L; 
    do 
    { 
        printf("iterations=%5ld",iter); 
        convert(mip,1,q); 
        do 
        { 
            copy(y,x); 
            for (i=1L;i<=r;i++) 
                mad(mip,y,y,c3,n,n,y); 
            k=0; 
            do 
            { 
                iter++; 
                if (iter%10==0) printf("\b\b\b\b\b%5ld",iter); 
                fflush(stdout);   
                copy(y,ys); 
                for (i=1L;i<=mr_min(m,r-k);i++) 
                { 
                    mad(mip,y,y,c3,n,n,y); 
                    subtract(mip,y,x,z); 
                    mad(mip,z,q,q,n,n,q); 
                } 
                egcd(mip,q,n,z); 
                k+=m; 
            } while (k