An off-shoot of my surrogate factoring research is a probabilistic
method to solve quadratic residues, as given
k^2 = q mod p
when p is an odd prime, and q is a quadratic residue modulo p, you
find k.
The technique requires introduction of a few additional variables
starting with T, where
T = 2q + np
where n is an odd natural number so you have T = 2q mod p, but T - 2q
is also forced to have p as a factor.
Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
= T:
z = (f_1 + f_2)/2
and now finally you try for an answer for k, with
k = 3^{-1}(2z) mod p.
The method is probabilistic because if I've got the analysis right you
have a 50% probability of getting the right k, for each z that you
try. Checking is done by looking at k^2 mod p, to see if you get q.
Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
then from
3k = 2(8) mod 17, is k = 11 mod 17.
Is there any use for such a technique?
James Harris
|
