### 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?