Cantor-Zassenhaus Algorithm
 

I've read that the Cantor-Zassenhaus algorithm can be used to find modular square roots.

I don't understand how the algorithm is supposed to work, could someone give an example of say: [TEX]x^{2}\equiv 61063\ \textrm{(mod 127)}[/TEX]

How much more difficult would the Tonelli-Shanks algorithm be to program than Cantor-Zassnehaus?

[QUOTE=Sam Kennedy;322465]I've read that the Cantor-Zassenhaus algorithm can be used to find modular square roots.

I don't understand how the algorithm is supposed to work, could someone give an example of say: [TEX]x^{2}\equiv 61063\ \textrm{(mod 127)}[/TEX]

How much more difficult would the Tonelli-Shanks algorithm be to program than Cantor-Zassnehaus?[/QUOTE]

I don't know anything about the Cantor-Zassenhous algorithm, but the Shanks-Tonelli algorithm is relatively easy to implement and fast. Search for a paper by Ezra Brown on the Shanks-Tonelli algorithm. There is also an implementation in YAFU if you want a programmatic reference.

[TEX]x = 61063^{\frac{127+1}{4}} \ mod \ 127[/TEX]

[QUOTE=Raman;322469][TEX]x = 61063^{\frac{127+1}{4}} \ mod \ 127[/TEX][/QUOTE]

[code]>>> pow(61063, 128//4, 127) == 61063 % 27
False[/code]

[QUOTE=Dubslow;322471][code]>>> pow(61063, 128//4, 127) == 61063 % 27
False[/code][/QUOTE]
[strike]Something is wrong with your pow function, because 127=3 (mod 4) therefore the formula is right, with solutions 22 and 105.[/strike] edit: scratch that, you have a typo %27 instead %127.

[QUOTE=LaurV;322478][strike]Something is wrong with your pow function, because 127=3 (mod 4) therefore the formula is right, with solutions 22 and 105.[/strike] edit: scratch that, you have a typo %27 instead %127.[/QUOTE]
Yes, that was a typo, but I maintain those aren't solutions.
[code]>>> pow(61063, 128//4, 127) == 61063 % 127
False
>>> pow(61063, 128//4, 127)
22
>>> 61063 % 127
103[/code]

[QUOTE=Dubslow;322481]Yes, that was a typo, but I maintain those aren't solutions.
[code]>>> pow(61063, 128//4, 127) == 61063 % 127
False
>>> pow(61063, 128//4, 127)
22
>>> 61063 % 127
103[/code][/QUOTE]
Grr man!
x can not be equal to x^2.
your left side is x
your right side is x^2.
22^2=103
105^2=103
mod 127.

The formula gives you x, not x^2. You have to square it. Too much (..!? what are people drinking there usually for xmas?) already, or what?

[QUOTE=LaurV;322482]Grr man!
x can not be equal to x^2.
your left side is x
your right side is x^2.
22^2=103
105^2=103
mod 127.

The formula gives you x, not x^2. You have to square it. Too much (..!? what are people drinking there usually for xmas?) already, or what?[/QUOTE]

:doh!: :blush:

Tonelli-Shanks is specialized to find modular square roots; Cantor-Zassenhaus finds the roots of general polynomials mod p. Basically you solve x^2-a=0 for x, with all quantities mod p.

I don't think you want to get into the details of how Cantor-Zassenhaus actually works, and Ben is correct that it's overkill for this application. Crandall and Pomerance have a nice description for a modular square root algorithm that is straightforward to implement.

I've decided to go for the Shanks-Tonelli algorithm. I think I understand how it works, there's just one thing I'm unsure of:

After you have removed all the powers of 2 from (p - 1), so that p - 1 = q * 2^s, will q always be odd, or do you need to find a solution where it's odd?

[QUOTE=Sam Kennedy;322510]I've decided to go for the Shanks-Tonelli algorithm. I think I understand how it works, there's just one thing I'm unsure of:

After you have removed all the powers of 2 from (p - 1), so that p - 1 = q * 2^s, will q always be odd, or do you need to find a solution where it's odd?[/QUOTE]

An even number is by definition a multiple of 2, so if all of the multiples of 2 are removed.... :unsure: