Cantor-Zassenhaus Algorithm

Sam Kennedy · 2012-12-24, 03:53

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: $x^{2}\equiv 61063\ \textrm{(mod 127)}$

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

bsquared · 2012-12-24, 04:33

Quote:

Originally Posted by Sam Kennedy

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: $x^{2}\equiv 61063\ \textrm{(mod 127)}$

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

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.

Raman · 2012-12-24, 04:48

$x = 61063^{\frac{127+1}{4}} \ mod \ 127$

Dubslow · 2012-12-24, 05:24

Quote:

Originally Posted by Raman

$x = 61063^{\frac{127+1}{4}} \ mod \ 127$

Code:

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

LaurV · 2012-12-24, 06:06

Quote:

Originally Posted by Dubslow

Code:

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

~~Something is wrong with your pow function, because 127=3 (mod 4) therefore the formula is right, with solutions 22 and 105.~~ edit: scratch that, you have a typo %27 instead %127.

Dubslow · 2012-12-24, 06:10

Quote:

Originally Posted by LaurV

~~Something is wrong with your pow function, because 127=3 (mod 4) therefore the formula is right, with solutions 22 and 105.~~ edit: scratch that, you have a typo %27 instead %127.

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

LaurV · 2012-12-24, 06:15

Quote:

Originally Posted by Dubslow

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

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?

Dubslow · 2012-12-24, 06:19

Quote:

Originally Posted by LaurV

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?

jasonp · 2012-12-24, 14:02

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.

Sam Kennedy · 2012-12-24, 15:29

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?

bsquared · 2012-12-24, 15:45

Quote:

Originally Posted by Sam Kennedy

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?

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

2012-12-24, 03:53	#1
Sam Kennedy Oct 2012 2×41 Posts	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: $x^{2}\equiv 61063\ \textrm{(mod 127)}$ How much more difficult would the Tonelli-Shanks algorithm be to program than Cantor-Zassnehaus?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
new factorization algorithm	jasonp	Math	2	2012-06-17 20:04
TF algorithm(s)	davieddy	Miscellaneous Math	61	2011-07-06 20:13
Is there an algorithm which solves this?	Unregistered	Homework Help	0	2007-08-09 17:40
Maybe new sieving algorithm	nuggetprime	Riesel Prime Search	5	2007-04-20 04:19
Prime95's FFT Algorithm	Angular	Math	6	2002-09-26 00:13

2012-12-24, 04:48	#3
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	$x = 61063^{\frac{127+1}{4}} \ mod \ 127$

2012-12-24, 14:02	#9
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	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.

2012-12-24, 15:29	#10
Sam Kennedy Oct 2012 2×41 Posts	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?