Browse Groups

• ... In general, finding a square root modulo a composite, m, is as difficult as factorizing m. If someone could do one of these things in polynomial time, they
Message 1 of 4 , Oct 1, 2006
View Source
--- In primeform@yahoogroups.com, Kermit Rose <kermit@...> wrote:

> It doesn't matter whether the modulus is prime or not.

In general, finding a square root modulo a composite, m,
is as difficult as factorizing m.

If someone could do one of these things in polynomial
time, they could do the other in polynomial time.
[C+P Exercise 6.5]

David
• That would conventionally be modular , not modulus . Posted by: Kermit Rose kermit@polaris.net kermit1941 ... No matter what algorithm you use (it s
Message 1 of 4 , Oct 1, 2006
View Source
That would conventionally be "modular", not "modulus".

Posted by: "Kermit Rose" kermit@... kermit1941
>
> I wrote the following code to find the square root of a number in a
> given modulus.
> Sometimes it fails due to infinite loop in the sequence. I inserted
> code to detect the
> loop.
>
> It doesn't matter whether the modulus is prime or not.

No matter what algorithm you use (it's exceptionally true for naive algorithms,
and simply true for advanced algorithms), for arbitrary composite bases your
best bet is to find the factorisation of the modulus, and combine partial

If your problem is looping, then you'd fall into the 'exceptionally' case.

> I expect that some of you know much faster algorithms.

Once factored, use a^((p+1)/2) if you can, else use Tonelli-Shanks' method if
p-1 doesn't have too many powers of 2, else use Cantor-Zassenhaus.

There are lucas sequence techniques which can replace Cantor-Zassenhaus, most
are effectively identical in efficiency. I seem to remember Bernstein doing a
compare and contrast between them. Alas that was in an even briefer style than
his usual papers.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... I translated it to GP. Here is a typical random run with a small composite modulus: No sqrt of Mod(2437846,10097063) because of loop. No sqrt of
Message 1 of 4 , Oct 1, 2006
View Source
--- In primeform@yahoogroups.com, Kermit Rose <kermit@...> wrote:

> Sometimes it fails due to infinite loop in the sequence.

I translated it to GP. Here is a typical random
run with a small composite modulus:

No sqrt of Mod(2437846,10097063) because of loop.
No sqrt of Mod(4159348,10097063) because of loop.
No sqrt of Mod(1605238,10097063) because of loop.
No sqrt of Mod(2684385,10097063) because of loop.
No sqrt of Mod(6854352,10097063) because of loop.
No sqrt of Mod(6580110,10097063) because of loop.
No sqrt of Mod(1620247,10097063) because of loop.
Mod(1375880, 10097063)^2=Mod(8014908, 10097063) in 969 steps
Mod(2198754, 10097063)^2=Mod(4999864, 10097063) in 2813 steps
No sqrt of Mod(8398488,10097063) because of loop.
Mod(3517308, 10097063)^2=Mod(8931988, 10097063) in 931 steps
No sqrt of Mod(4074075,10097063) because of loop.
No sqrt of Mod(5459872,10097063) because of loop.
Mod(4029863, 10097063)^2=Mod(2775585, 10097063) in 1724 steps
Mod(4011706, 10097063)^2=Mod(5635295, 10097063) in 3335 steps
Mod(2918827, 10097063)^2=Mod(2693734, 10097063) in 598 steps
Mod(804634, 10097063)^2=Mod(2097333, 10097063) in 1539 steps
No sqrt of Mod(7355577,10097063) because of loop.
Mod(5892961, 10097063)^2=Mod(9115676, 10097063) in 1691 steps
No sqrt of Mod(8162051,10097063) because of loop.

David
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.