On Jun 26, 10:01=A0pm, JSH <jst...@[EMAIL PROTECTED]
> wrote:
> 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
yo=
u
> > > 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=
answer
> > > 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? =A0But if so, why?
Correction: k =3D 15.
> Did you try that at random or find it? =A0Searching for a case that
> wouldn't work?
I figured it out, as if T is a square then, of course, you can simply
take its square root to get k.
So you have to check if T is a square, which isn't a terrible thing as
if it is, then, of course, you're done anyway and that's not new.
What is new is a short-cut which can give you an answer much, much,
much faster in general then simply looking for a perfect square.
James Harris
|
