On Jun 22, 7:26=A0am, JSH <jst...@[EMAIL PROTECTED]
> wrote:
> An off-shoot of my surrogate factoring research is a probabilistic
> method to solve quadratic residues, as given
>
> k^2 =3D 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 =3D 2q + np
>
> where n is an odd natural number so you have T =3D 2q mod p, but T - 2q
> is also forced to have p as a factor.
>
Also as pointed out by an example from Chip Eastham in this thread, if
T is a perfect square, then you are, of course, done, as you can
simply take its square root!
So you continue only if T is not a perfect square.
> Next you find z, where with integer factors f_1 and f_2 where f_1*f_2
> =3D T:
>
> z =3D (f_1 + f_2)/2
>
> and now finally you try for an answer for k, with
>
> k =3D 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. =A0Checking is done by looking at k^2 mod p, to see if you get q.
Which is why it's a super advance on just finding T a square which is
the old tech.
The new tech is this kind of a trick that can greatly speed up the
process.
>
> 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?
I'd think there should be for anyone who likes SPEED and wants to
solve a quadratic residue.
But maybe none of you do, or maybe mathematicians are not into the
best techniques--if one of their own doesn't find them.
As I've noted many times about a field that can't be the best so it
ignores the best.
James Harris
|
