On Jun 22, 10: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.
>
> 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.
>
> 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
/* notes on JSH's "probabilistic square root mod p" */
Given prime p and quadratic residue q modulo p,
we seek k s.t. k^2 =3D q mod p.
JSH claims that the following procedure has 50%
chance of success:
Choose odd multiplier n to get T =3D 2q + np.
Factor T: f_1 * f_2 =3D 2q + np
[Here I simplify JSH's formulation, in that he
refers to the sum of factors f_1 + f_2 as 2z.]
Define z =3D f_1 + f_2 and k =3D z/3 mod p.
What has this to do with a square root of q?
Well, for k^2 =3D q mod p, it would require:
k^2 =3D (f_1^2 + 2 f_1*f_2 + f_2^2)/9 mod p
=3D (f_1^2 + 4 q + f_2^2)/9 mod p
5q =3D f_1^2 + f_2^2 mod p
A priori I can see no reason this should be
likely.
/* Example: Find k^2 =3D 3 mod 73 */
Since 3 is a quadratic residue mod 73 if and only if 73 is a quadratic
residue mod 3 (by quadratic reciprocity), and 73 =3D 1 mod 3, then 3 is
a quadratic residue mod 73. Also, 5q =3D 15.
Now taking:
n =3D 1: T =3D 6 + 73 =3D 79 prime
(1 + 79^2) mod 73 =3D 37
n =3D 3: T =3D 6 + 219 =3D 225 =3D 3*75 =3D 5*45 =3D 9*25 =3D 15 * 15
(1 + 225^2) mod 73 =3D 37
(9 + 75^2) mod 73 =3D 13
(25 + 45^2) mod 73 =3D 6
(81 + 25^2) mod 73 =3D 49
450 mod 73 =3D 12
n =3D 5: T =3D 6 + 365 =3D 371 =3D 7 * 53
(1 + 371^2) mod 73 =3D 37
(49 + 53^2) mod 73 =3D 11
n =3D 7: T =3D 6 + 511 =3D 517 =3D 11 * 47
(1 + 517^2) mod 73 =3D 37
(11^2 + 47^2) mod 73 =3D 67
n =3D 9: T =3D 6 + 657 =3D 663 =3D 3*13*17
(1 + 663^2) mod 73 =3D 37
(9 + 221^2) mod 73 =3D 13
(13^2 + 51^2) mod 73 =3D 69
(17^2 + 39^2) mod 73 =3D 58
n =3D 11: T =3D 6 + 803 =3D 809 prime
(1 + 809^2) mod 73 =3D 37
None of the smallish multipliers n =3D 1 to 11
gives a factorization T =3D f_1 * f_2 that
produces k such that k^2 =3D 3 mod 73.
regards, chip
|
