On Sun, 22 Jun 2008 09:04:10 -0700 (PDT), JSH <jstevh@[EMAIL PROTECTED]
>
wrote:
>On Jun 22, 8:11 am, Chip Eastham <hardm...@[EMAIL PROTECTED]
> wrote:
>> On Jun 22, 10:26 am, JSH <jst...@[EMAIL PROTECTED]
> wrote:
>>
>> [snip]
>>
>> > 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. Checking is done by looking at k^2 mod p, to see if you get q.
>>
>> > Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.
>>
>> > Here T=21 does not work, but T = 55 = 5(11), so z = 8 and the answer
>> > then from
>>
>> > 3k = 2(8) mod 17, is k = 11 mod 17.
>>
>> > Is there any use for such a technique?
>>
>> > James Harris
>>
>> For primes p = 8n + 1, there is a probabilistic aspect
>> of the best methods for finding square roots mod p.
>> For primes with other residues mod 8, deterministic
>> methods are known.
>
>Well this technique would be probabilistic for p odd prime.
>
>So it's more general then, correct?
If you want a more general probabilistic algorithm, then yes. If you
want a deterministic algorithm then no. For myself I use the
deterministic algorithms (p mod 8 = 3, 5, 7) where possible and only
use the probabilistic algorithm (p mod 8 = 1) where I have to.
Crandall and Pomerance, algorithm 2.3.8 refers.
YMMV.
>
>> However the nondeterminism is limited to finding one
>> quadratic residue mod p. If only one square root mod
>> p is needed, then perhaps the analysis comes to the
>> same thing, but it is well known that half of all the
>> nonzero residues mod p are quadratic nonresidues, and
>> confirming one by Legendre symbol (efficiently found
>> by the generalization, the Jacobi symbol) chosen at
>> random clearly gives a 50% chance of success.
>
>Um, yeah.
>
>> The Wikipedia articles on "Quadratic residue" and
>
>Already read it.
>
>> "Shanks-Tonelli algorithm" would be nice starting
>
>Thanks! Just went by to check it out.
>
>> points if you wish know more.
>
>I think it interesting to me that what I call surrogate factoring
>leads to this way to solve for a quadratic residue by factoring. Note
>my idea involves factoring an odd T chosen such that T = 2q mod p,
>where q is the quadratic residue modulo p, and it should have a 50%
>chance of success with each factorization of T, if it's right.
>
>The math is easy but repeatedly I've thought one thing and been forced
>to back down later when experiments demonstrate that I'm wrong.
You should consider this observation well James.
rossum
>Still I find myself drawn in a bit on this subject so I'm reading
>material about it on the web and pondering the problem.
>
>
>___JSH
>
>
>
|
