On Jun 22, 10:26=A0am, JSH <jst...@[EMAIL PROTECTED]
> wrote:
[snip]
> 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. =A0Checking is done by looking at k^2 mod p, to see if you get q.
>
> Example: Let q=3D2, p=3D17 so T =3D 2(2) mod 17 =3D 4 mod 17.
>
> Here T=3D21 does not work, but T =3D 55 =3D 5(11), so z =3D 8 and the
ans=
wer
> then from
>
> 3k =3D 2(8) mod 17, is k =3D 11 mod 17.
>
> Is there any use for such a technique?
>
> James Harris
For primes p =3D 8n + 1, there is a probabilistic aspect
of the best methods for finding square roots mod p.
For primes with other residues mod 8, deterministic
methods are known.
However the nondeterminism is limited to finding one
quadratic residue mod p. If only one square root mod
p is needed, then perhaps the analysis comes to the
same thing, but it is well known that half of all the
nonzero residues mod p are quadratic nonresidues, and
confirming one by Legendre symbol (efficiently found
by the generalization, the Jacobi symbol) chosen at
random clearly gives a 50% chance of success.
The Wikipedia articles on "Quadratic residue" and
"Shanks-Tonelli algorithm" would be nice starting
points if you wish know more.
regards, chip
|
