rabin_encryption_method.sf

#!/usr/bin/ruby

/*
Rabin's protocol is equivalent to factoring:  Suppose you have a procedure P
which, given a quadratic residue, gives one of its square roots mod pq.  The
four nsquare roots of a quadratic residue y=x^2 mod pq is -x, x, -gamma x,
gamma x, where gamma is the nontrivial square root of unity mod pq.

Aside:  you can find gamma if you know p and q by using the Chinese
Remainder Theorem (CRT) and solving the system of equations

x = -1 mod p
x = 1 mod q

[ You can see where the other square roots of unity comes from:  they are the
other possible patterns of signs on the 1's in the system of eqns for CRT. ]

Now, given P, you choose a random r between 1 and pq-1 inclusive and compute
y = P(r^2).  With 1/2 probability, y = +/- gamma r.  Since you knew r, you
can find g = y/r = +/- gamma.  Now, since g-1 is either 0 mod q or 0 mod p,
so GCD(g-1,pq) will give you p or q.

[ To find 1/r mod pq, use EGCD:  The extended Euclidean algorithm, given
m,n, will find GCD(m,n) as well as the pair a,b such that am+bn=GCD(m,n).
When GCD(m,n)=1, we have a=1/m mod n. ]

Note that this can be simplfied a little, since with very high probability r
does not divide pq:  r(g-1) = r(y/r - 1) = y - r, so GCD(y-r,pq) will work
just as well.  If r divides pq, you've already (accidentally) factored the
modulus.
*/

# See also:
#   https://ratthing.com/files/textfiles.com/programming/CRYPTOGRAPHY/rabin-al.txt

# TODO: implement it