Harristotelian Logic

Given a quadratic residue q modulo p where p is an odd prime and not 3, where you wish to find k, where

k^2 = q mod p.

you start with

T = 2q mod p

where T cannot equal 2q, so you'd start with T = 2q+p or T = 2q - p, and next you have to factor it:

With f_1 and f_2 where f_1*f_2 = T,

you get k from

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

with a 50% probability that you will get the correct k.

Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.

I tried T = 21 and that didn't give me a positive k, and nothing did until T = 55, then f_1=5, f_2=11 gives

3k = 16 mod 17, so k = 11.

11^2 = 2 mod 17.

Here's another example, let q=5, p=19, then T = 10 mod 19, and T = 29, works with f_1=29 and f_2 = 1, giving

3k = 30 mod 19, and k=10.

10^2 = 5 mod 19.

So there can be something of a search but it is a smaller search than looping through squaring each residue and checking directly.

And these equations connect solving a quadratic residue modulo p squarely to integer factorization.