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