On Jun 27, 7:45=A0pm, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
> 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
probabilisti=
c
> > > > > 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,
yo=
u
> > > > > 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
righ=
t you
> > > > > have a 50% probability of getting the right k, for each z that
yo=
u
> > > > > try. =A0Checking is done by looking at k^2 mod p, to see if you
g=
et 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
quadra=
tic
> > > > 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. =A0This 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).
That's no the problem. q=3D3 was.
> 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? =A0It
> 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
Nope, I went and looked for it. The problem is 3. Try another q with
p=3D73 that is a quadratic residue that is not divisible by 3 and see
what happens. Oh yeah, it took two things: p mod 3 =3D 1 and q=3D3 for
big problems to arise so you had a lucky set of choices, which isn't a
bad thing. I find the issue curious.
I am puzzling over why it's such a big deal.
___JSH
|
