Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 20:12, 21 July 2006

Revision as of 09:47, 27 July 2006

Line 32:

===Algorithm===

The Cantor-Zassenhaus algorithm computes polynomials of the same type as <math>a(x)</math> above using the isomorphism discussed in the Background section. It proceeds as follows, in the case where the field <math>\mathbb{F}_q</math> is of odd-characteristic. The process can be generalised to characteristic 2 fields in a fairly straightforward way: Select a random polynomial <math>b(x) \in R</math> such that <math>b(x) \neq 0, \pm 1 </math>. Set <math>m=(q^d-1)/2</math> and compute <msthmath>b(x)^m</math>. Since <math>\phi</math> is an isomorphism, we have (using our now-established notation):

:<math>\phi(b(x)^m) = (b_1^m(x) + \langle p_1(x) \rangle, \ldots, g^m_s(x) + \langle p_s(x) \rangle,)</math>.