On Jun 23, 7:46=A0pm, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
> 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
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
>
> /* 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
>
> =A0 =A0 =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: =A0Find 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. =A0Also, 5q =3D 15.
>
> Now taking:
>
> n =3D 1: T =3D 6 + 73 =3D 79 prime
>
> =A0(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
>
> =A0(1 + 225^2) mod 73 =3D 37
> =A0(9 + 75^2) mod 73 =3D 13
> =A0(25 + 45^2) mod 73 =3D 6
> =A0(81 + 25^2) mod 73 =3D 49
> =A0 450 mod 73 =3D 12
>
> n =3D 5: T =3D 6 + 365 =3D 371 =3D 7 * 53
>
> =A0(1 + 371^2) mod 73 =3D 37
> =A0(49 + 53^2) mod 73 =3D 11
>
> n =3D 7: T =3D 6 + 511 =3D 517 =3D 11 * 47
>
> =A0(1 + 517^2) mod 73 =3D 37
> =A0(11^2 + 47^2) mod 73 =3D 67
>
> n =3D 9: T =3D 6 + 657 =3D 663 =3D 3*13*17
>
> =A0(1 + 663^2) mod 73 =3D 37
> =A0(9 + 221^2) mod 73 =3D 13
> =A0(13^2 + 51^2) mod 73 =3D 69
> =A0(17^2 + 39^2) mod 73 =3D 58
>
> n =3D 11: T =3D 6 + 803 =3D 809 prime
>
> =A0(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
k =3D 21, so maybe k has to be coprime to q? But if so, why?
Did you try that at random or find it? Searching for a case that
wouldn't work?
___JSH
|
