User:DevastatorIIC/RSA Factorization Program

From Wikipedia, the free encyclopedia

Programmed by Paul, Nov. 2005

Features:

• Timer
• random RSA# generator
• user inputs # of RSA#s to be generated and factored
• Primegen 2 (30% faster)

---

#include <iostream>

#include <ctime>

using namespace std;

int factor( unsigned int );

int getPrime( int );

unsigned int makeRSA( void );

int main() {

   srand( time( 0 ) );
   cout << "Enter number of iterations: ";
   int a;
   cin >> a;
   int *RSAs = new int[ a ];
   for ( int i = 0; i < a; i++ ) 
   {
       RSAs[i] = makeRSA();
   }    
   
   int s = time(0);                             //start timer
   for ( int j = 0; j < a; j++ )
       factor(RSAs[j]);
   int e = time(0);                             //end timer
   
   cout << "It took " << e-s << " seconds to factor " << a << " products over 1 billion of two primes!\n";
   
   system("pause");
   return 0;

}

int factor( unsigned int RSA ){

   int divisor = (int)sqrt( (double)RSA );      //first value is sqrt(RSA)
   while ( 1 ){                                 //loop until something is returned
       divisor = getPrime( divisor - 1 );       //find the first prime lower than sqrt(RSA)
       if ( RSA % divisor == 0 )               //if evenly divisible by said prime
               return divisor;                  //return original prime
   } 

}

int getPrime( int a ){

   int sqr, notprime, k, m;
   while ( a != 0 ){                            //while a isn't zero
       if ( a % 2 != 0 && a % 3 != 0 || a == 2 || a == 3 )
       {
           sqr = (int)sqrt( (double)a );
           notprime = 0;
           
           k = 1;
           m = 6*k; 
           while ( (m-1) <= sqr )
           {    
               if ( (a % (m-1) == 0) || (a % (m+1) == 0) )
               {
                    notprime = 1;
                    break;
               }
               k++;
               m = 6*k;  
           }    
           
           if ( notprime == 0 )
           {
              return a; 
           }    
                
       }   
       a--;                                     //decrement a
   }   
   cerr << "Error: No prime found.\n";
   exit(1);

}

unsigned int makeRSA() {

   int a = 31623 + rand() % 33914;              //Get random number between sqrt 1 billion and 2^16
   a = getPrime(a);                             //find prime close to it
   int b = 31623 + rand() % 33914;
   b = getPrime(b);
   return a*b;                                  //return product

}