home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 247_01 / brent.c < prev    next >
Text File  |  1989-04-19  |  2KB  |  77 lines
  1. /*
  2.  *   Program to factor big numbers using Brent-Pollard method.
  3.  *   See "An Improved Monte Carlo Factorization Algorithm"
  4.  *   by Richard Brent in BIT Vol. 20 1980 pp 176-184
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include "miracl.h"
  9.  
  10. #define min(a,b) ((a) < (b)? (a) : (b))
  11.  
  12. main()
  13. {  /*  factoring program using Brents method */
  14.     long k,r,i,m,iter;
  15.     big x,y,z,n,q,ys,c3;
  16.     mirsys(50,MAXBASE);
  17.     x=mirvar(0);
  18.     y=mirvar(0);
  19.     ys=mirvar(0);
  20.     z=mirvar(0);
  21.     n=mirvar(0);
  22.     q=mirvar(0);
  23.     c3=mirvar(3);
  24.     printf("input number to be factored\n");
  25.     cinnum(n,stdin);
  26.     if (prime(n))
  27.     {
  28.         printf("this number is prime!\n");
  29.         exit(0);
  30.     }
  31.     m=10;
  32.     r=1;
  33.     iter=0;
  34.     do
  35.     {
  36.         printf("iterations=%5ld",iter);
  37.         convert(1,q);
  38.         do
  39.         {
  40.             copy(y,x);
  41.             for (i=1;i<=r;i++)
  42.                 mad(y,y,c3,n,n,y);
  43.             k=0;
  44.             do
  45.             {
  46.                 iter++;
  47.                 if (iter%10==0) printf("\b\b\b\b\b%5ld",iter);
  48.                 copy(y,ys);
  49.                 for (i=1;i<=min(m,r-k);i++)
  50.                 {
  51.                     mad(y,y,c3,n,n,y);
  52.                     subtract(y,x,z);
  53.                     mad(z,q,q,n,n,q);
  54.                 }
  55.                 gcd(q,n,z);
  56.                 k+=m;
  57.             } while (k<r && size(z)==1);
  58.             r*=2;
  59.         } while (size(z)==1);
  60.         if (compare(z,n)==0) do 
  61.         { /* back-track */
  62.             mad(ys,ys,c3,n,n,ys);
  63.             subtract(ys,x,z);
  64.         } while (gcd(z,n,z)==1);
  65.         if (!prime(z))
  66.              printf("\ncomposite factor ");
  67.         else printf("\nprime factor     ");
  68.         cotnum(z,stdout);
  69.         if (compare(z,n)==0) exit(0);
  70.         divide(n,z,n);
  71.         divide(y,n,n);
  72.     } while (!prime(n));      
  73.     printf("prime factor     ");
  74.     cotnum(n,stdout);
  75. }
  76.  
  77.