Tuesday, February 09, 2010


JSH: Quadratic residues and factoring idea

Solving quadratic residues is simply related to factoring.

If you assume f_1 = ak mod p, and f_2 = bk mod p

then easily enough:

k = (a+b)^{-1}(f_1 + f_2) mod p

so if you also have T = f_1*f_2 = abk^2 = abq mod p

you can factor T, when

T = abq mod p, to get f_1 and f_2 and possibly solve for k,

if k^2 = q mod p.

Here also ab and a+b are unique.

<< Home

This page is powered by Blogger. Isn't yours?