On Jun 22, 8:11=A0am, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
> 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
a=
nswer
> > 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.
Well this technique would be probabilistic for p odd prime.
So it's more general then, correct?
> However the nondeterminism is limited to finding one
> quadratic residue mod p. =A0If 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.
Um, yeah.
> The Wikipedia articles on "Quadratic residue" and
Already read it.
> "Shanks-Tonelli algorithm" would be nice starting
Thanks! Just went by to check it out.
> points if you wish know more.
I think it interesting to me that what I call surrogate factoring
leads to this way to solve for a quadratic residue by factoring. Note
my idea involves factoring an odd T chosen such that T =3D 2q mod p,
where q is the quadratic residue modulo p, and it should have a 50%
chance of success with each factorization of T, if it's right.
The math is easy but repeatedly I've thought one thing and been forced
to back down later when experiments demonstrate that I'm wrong. Still
I find myself drawn in a bit on this subject so I'm reading material
about it on the web and pondering the problem.
___JSH
|
