On Jun 27, 8:09=A0pm, JSH <jst...@[EMAIL PROTECTED]
> wrote:
> 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
=
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
t=
he 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
quadrati=
c
> > > 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
First, I didn't do any searching. This was the first
thing I tried, picking p =3D 73 because it's a prime
congruent to 1 mod 8 (the only cases for which a fast
deterministic method is unknown, so potentially where
room for improvement in a probabilistic method exists).
Second, I don't see the benefit of finding T is a square.
Yes, this gives a square root mod p for 2q, but not for q.
Here 15^2 =3D 225 =3D 6 =3D 2q mod p for q =3D 3 and p =3D 73.73.
How would this help find a square root for 3 mod 73? It
reduces the problem to finding a square root for 2 mod 73.
You were "right" with the answer 21^2 =3D 441 =3D 3 mod 73,
but I assume (since you showed no work) this answer was
not obtained by the probabilistic method you outlined.
regards, chip
|
