From: bobs@rsa.com Newsgroups: sci.math.symbolic Subject: Re: Berlekamp/distinct degree Date: Thu, 03 Dec 1998 16:51:06 GMT In article , igor@txc.com wrote: > Hi, I'm interested in short yet comprehensive side-by-side > comparison of 2 main method's of modulo polynomial factorization, > Berlekamp against direct degree+Cantor-Zassenhaus. I'd be > interested at looking at some family of polynomials which represent > worst-case scenario for one method and average/best-case scenatio > for the other, and vice versa. > > I'll appreciate any help on this subject. Hi, Are you looking at time complexity only? Because the space requirements for the two methods are greatly different. Berlekamp's method requires solving what can be a large matrix. Cantor-Zassenhaus take space bounded by a constant multiple of the degree of the polynomial. If d is the degree and p is the characteristic, Berlekamp's takes O(d^2 log p) space while C-Z takes O(d log p). My experience is that Cantor-Zassenhaus is almost uniformly faster unless the characteristic is very small. (and I have a great deal of experience in factoring polynomials over finite fields from my work on the Number Field Sieve) -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: Igor Schein Newsgroups: sci.math.symbolic Subject: Re: Berlekamp/distinct degree Date: 3 Dec 1998 22:23:11 GMT bobs@rsa.com wrote: > In article , > igor@txc.com wrote: >> Hi, I'm interested in short yet comprehensive side-by-side >> comparison of 2 main method's of modulo polynomial factorization, >> Berlekamp against direct degree+Cantor-Zassenhaus. I'd be >> interested at looking at some family of polynomials which represent >> worst-case scenario for one method and average/best-case scenatio >> for the other, and vice versa. >> >> I'll appreciate any help on this subject. > Hi, > Are you looking at time complexity only? Because the space requirements for > the two methods are greatly different. Berlekamp's method requires solving > what can be a large matrix. Cantor-Zassenhaus take space bounded by a > constant multiple of the degree of the polynomial. If d is the degree and p > is the characteristic, Berlekamp's takes O(d^2 log p) space while C-Z takes > O(d log p). > My experience is that Cantor-Zassenhaus is almost uniformly faster unless the > characteristic is very small. (and I have a great deal of experience in > factoring polynomials over finite fields from my work on the Number Field > Sieve) Hi, Bob. I was talking about time complexity. I noticed that C-Z has much more moderate memory requirement. PARI has implementation of both, and the user's guide claims that "Note that the factormod algorithm is usually faster than factorcantor", If you never used pari, factormod is Berlekamp, and factorcantor is self-explanatory. And indeed I found that Berlekamp is sometimes slightly, sometimes significantly faster than C-Z. I found only 1 family of of polynomials where it's the other way around, namely x^2^k+x Mod 2 for integer k. So I was wondering why that may be. Thanks Igor