Shor's Algorithm Playground

Note: for large values of p and q, this page may run extremely slowly.

RSA Setup

Multiplicative Group Modulus
Select 2 prime values p and q
p=
p must be prime. If this condition is not met, the rest of this program may not work properly.
q=
q must be prime and different from p. If this condition is not met, the rest of this program may not work properly.
The group modulus is the product of p and q
N=p*q
Key Selection
The totient function finds the number of integers coprime with the modulus. For RSA, φ(N) = (p-1)(q-1)
φ(N)=
Select a short key to use for encryption. It must be between 1 and φ(N) and coprime with φ(N), and should be small.
e=
e must be greater than 1 and less than φ(N) and e must be coprime with φ(N)
The decryption key will be the modular multiplicative inverse of the encryption key.
d ≡ e-1 (mod N)
Sending Messages
Select a message to send. (Must be between 1 and N)
m=
m must be between 1 and N.
The message is encrypted.
c ≡ me (mod N)
Sanity check: decrypting the message should get back to the original.
m ≡? cd (mod N)

Breaking RSA

Finding the Order of an Element
Select a value to test. (Must be between 2 and N-1)
a=
a must be between 2 and N-1.
Check the GCD of a and N, a lucky guess gives a factor.
Recall that finding the GCD of 2 numbers is polynomial time (fast).
K=gcd(a, N)
We compute the order. Classically, this is exponentially slow, but this can be done quickly on a quantum computer.
WARNING: If the chosen modulus above is too large, this step will take extremely long and may abort.
r=
r was not able to be calculated. This may indicate that `a` shares a factor with N (in which case you're done factoring) or it may indicate that the operation was aborted due to time constraints.
Using r to Find p and q
For the following steps, `r` needs to be even. If it is not, try a different value of `a`.
Test the suspected values
v1= ar/2+1
v2= ar/2-1
Cannot compute using odd or non-existent value for `r`
Next, we compute the GCDs of v1 and v2 with N
g1= gcd(v1, N)
g2= gcd(v2, N)
Cannot compute using odd or non-existent value for `r`

If g1 or g2 are not trivial (1 or N), they should be either `p` or `q`. Try different values of `a` until you can find one, the likelihood is pretty high in practice.