Cantor–Zassenhaus algorithm: Difference between revisions

Revision as of 10:46, 28 September 2018

Revision as of 00:23, 17 April 2019

Line 48:

===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(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 <math>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, b^m_s(x) + \langle p_s(x) \rangle).</math>