View Single Post
Old 2007-12-15, 12:50   #3
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

Ok I commented the code.

Code:
import java.math.BigInteger;//imports
import java.util.ArrayList;
import java.util.Random;

public class Main {
    //global vars
    public static BigInteger zero=BigInteger.valueOf(0);
    public static BigInteger one=BigInteger.valueOf(1);    
    public static Random rnd=new Random();//randomizer

public static void main(String[] args) {

   ArrayList<BigInteger>primes=new ArrayList<BigInteger>();//list of primes
   ArrayList<BigInteger>resedues=new ArrayList<BigInteger>();//list of resedues
   ArrayList<BigInteger>moduli=new ArrayList<BigInteger>();//list of modulus primes
  //this generates and stores primes
   for(int i=2;i<100000;i++){
       if(BigInteger.valueOf(i).isProbablePrime(30)){
           primes.add(BigInteger.valueOf(i));
       }
   }
 
//this part generates 2 large random bigintegers
   BigInteger number1=BigInteger.probablePrime(20,rnd);
   for(int i=0;i<1000;i++){
       number1=number1.multiply(BigInteger.probablePrime(20,rnd));
   }
   BigInteger number2=BigInteger.probablePrime(20,rnd);
   for(int i=0;i<1000;i++){
       number2=number2.multiply(BigInteger.probablePrime(20,rnd));
   }
   
   //multiplication is made using standard java method and analyzed
   long start=System.nanoTime();
   BigInteger temp=number1.multiply(number2);
   long end=System.nanoTime()-start;
   System.out.println("slow multiplication time: "+end+"ns");
   System.out.println("slow multiplication time: "+temp);
   System.out.println("bitlength: "+temp.bitLength());  

   
   BigInteger compositemod=one;//initialized modulus
   int totallength=number1.bitLength()+number2.bitLength()+1;//calculate limit of modulus size at which to stop iterating
   start=System.nanoTime();//start times
   
   for(int i=0;i<primes.size();i++){
        BigInteger prime1=primes.get(i);//get prime from prime list
        if(number1.gcd(prime1).equals(one)){//check that prime is not a
            if(number2.gcd(prime1).equals(one)){//factor of either numbers
            BigInteger resedue1=number1.mod(prime1);//mod first multiplicand by the prime
            BigInteger resedue2=number2.mod(prime1);//mod second multiplicand by the prime
            BigInteger reseduetotal=resedue1.multiply(resedue2).mod(prime1);
//multiply resedue together and mod them to the prime
            //System.out.println("resedue: "+reseduetotal+" mod "+prime1);//debug
            resedues.add(reseduetotal);//store product resedue in resedue list
            moduli.add(prime1);//add used prime to moduli list
            compositemod=compositemod.multiply(prime1);
            if(compositemod.bitLength()>totallength){//check whether to end the loop
                i=primes.size();
            }
            }
        }
   }
   
   BigInteger x=zero;//initialize product variable
  //this part multiplies/solves all of the product congruences together
   for(int i=0;i<resedues.size();i++){
       BigInteger partinverse=compositemod.divide(moduli.get(i));
       BigInteger inverseb=partinverse.modInverse(moduli.get(i));
       BigInteger solutioni=partinverse.multiply(inverseb).multiply(resedues.get(i));
       x=x.add(solutioni);       
   }
   x=x.mod(compositemod);//x is the product

   //this is the analysis part
   end=System.nanoTime()-start;
   System.out.println("fast multpliction time: "+end+"ns");
   System.out.println("fast multiplication: "+x);
   System.out.println("bitlength: "+x.bitLength());

}
}
vector is offline   Reply With Quote