Sunday, June 22, 2008
JSH: Probabilistic quadratic residue solving
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?
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?
# posted by James Harris @ 10:26 
