Content deleted Content added
Algebraist (talk | contribs) m hypens to dashes |
fix typos in formula |
||
Line 50:
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 <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,
Now, each <math>b_i(x) + \langle p_i(x)\rangle</math> is an element of a field of order <math>q^d</math>, as noted earlier. The multiplicative subgroup of this field has order <math>q^d-1</math> and so, unless <math>b_i(x)=0</math>, we have <math>b_i(x)^{q^d-1}=1</math> for each <math>i</math> and hence <math>b_i(x)^m = \pm 1</math> for each <math>i</math>. If <math>b_i(x)=0</math>, then of course <math>b_i(x)^m=0</math>. Hence <math>b(x)^m</math> is a polynomial of the same type as <math>a(x)</math> above. Further, since <math>b(x) \neq 0, \pm1</math>, at least two of the sets <math>A,B</math> and <math>C</math> are non-empty and by computing the above GCDs we may obtain non-trivial factors. Since the ring of polynomials over a field is a [[Euclidean ___domain]], we may compute these GCDs using the [[Euclidean algorithm]].
| |||