Factorizing Integers with the Rho Method

I start with a statement … “Integer factorization is not in NP-Complete!”. So why is it the source of many public key methods, such as RSA? Well, it is a hard problem at the current time, but with the advent of quantum computers, it will not be.

Cracking RSA

Many of our public key methods involve the multiplication of prime numbers. For example the security of RSA is based on the multiplication of two prime numbers (P and Q) to give the modulus value (N). If we can crack the N value, we will crack the decryption key. Overall every integer — which is not prime — can be created as a multiplication of prime numbers.

For RSA, here is an example of the encryption key, the value of N, and the cipher, [here]:

Encryption parameters
e:	65537
N:	1034776851837418228051242693253376923
Cipher:	582984697800119976959378162843817868
We are using  60 bit primes

Now we have to crack N by finding the primes that make up the value.

If we use this [link], we get:

Factors
-------
1,034,776,851,837,418,228,051,242,693,253,376,923 = 1,086,027,579,223,696,553 x 952,809,000,096,560,291

p=1,086,027,579,223,696,553 q=952,809,000,096,560,291

Now we work out PHI, which is equal to (p−1)×(q−1):

>>>p=1086027579223696553
>>>q=952809000096560291
>>> print (p-1)*(q-1)
1034776851837418226012406113933120080