Friday, February 25, 2011

Crypto codes: Pollard’s p − 1 factorization algorithm

Code here
It uses prime factor code from square root

Output shows the steps of the algorithm with results:
Find prime factors of 48356747:
2^19! -1 = 13944673 (mod 48356747)
gcd(2^19!-1,48356747) = 6917
factors of 48356747, p=6917, and q=48356747/6917=6991
The prime factorization of 6916 is: 2, 2, 7, 13, 19

The prime factorization of 6990 is: 2, 3, 5, 233

Thursday, February 24, 2011

Sunday, February 13, 2011

Monday, February 07, 2011

Crypto codes (3)

Download from here
For the inverse and fast squaring code, see Crypto codes: 1

Finds eth root modulo p:

public class RSA {

 //find x from x^e = c (mod p)
  public static long findRoot(long e, long c, long p)
  {
   long x = 0;
   
   //find e^-1 (mod p-1)
   long eInverse = crypto.inverse(p-1, e);
   
   //x = c^d (mod p)
   x = crypto.fastSq(p, c, eInverse);
   
   return x;
  }
       //test: answer = 6059
  public static void main(String[] args) {
   
      long e = 1583;
      long c = 4714;
      long p = 7919;
      
   long x = RSA.findRoot(e,c, p);
   System.out.println("Solution to x^"+e+" = "+c+" (mod "+p+"): x= "+x);
  }

}

This test will return:
Solution to x^1583 = 4714 (mod 7919): x= 6059

Matlab codes: http://www-users.math.umd.edu/~lcw/MatlabCode/

Wednesday, February 02, 2011

Crypto codes: Chinese remainder theorem

For gcd and inverse code, see Crypto codes

Java implementation of Chinese remainder theorem, download from here
Matlab code here

For this particular example, output will look like the following:

Step:0->x=2+3*5=17
Step:1->x=17+21*7=164
Solution:164