Content deleted Content added
Undid revision 1289255299 by Sheddow (talk) overlinkinga; A reader who reaches this part of the article must know what is a lemma. Moreover, here, "lemma" could usefully replaced here with "theorem" Tag: Reverted |
Undid revision 1289259264 by D.Lazard (talk) I'm not linking to the wikipage of "lemma", I'm linking to the actual lemma used, which is buried somewhere five sections above this point. I don't think it's reasonable to expect readers to Ctrl-F for lemma to find it |
||
Line 124:
The correctness of the algorithm is based on the following:
<blockquote>{{Anchor|lemma}}'''Lemma.''' For ''i'' ≥ 1 the polynomial
: <math>x^{q^i}-x \in \mathbf{F}_q[x]</math>
is the product of all monic irreducible polynomials in '''F'''<sub>''q''</sub>[''x''] whose degree divides ''i''.</blockquote>
Line 230:
== Rabin's test of irreducibility ==
Like distinct-degree factorization algorithm, Rabin's algorithm<ref>{{cite journal |last1=Rabin |first1=Michael |year=1980 |title=Probabilistic algorithms in finite fields |journal=SIAM Journal on Computing |volume=9 |issue=2 |pages=273–280 |doi=10.1137/0209024 |citeseerx=10.1.1.17.5653 }}</ref> is based on the [[#lemma|lemma]] stated above. Distinct-degree factorization algorithm tests every ''d'' not greater than half the degree of the input polynomial. Rabin's algorithm takes advantage that the factors are not needed for considering fewer ''d''. Otherwise, it is similar to distinct-degree factorization algorithm. It is based on the following fact.
Let ''p''<sub>1</sub>, ..., ''p<sub>k</sub>'', be all the prime divisors of ''n'', and denote <math>n/p_i=n_i</math>, for 1 ≤ ''i'' ≤ ''k'' polynomial ''f'' in '''F'''<sub>''q''</sub>[''x''] of degree ''n'' is irreducible in '''F'''<sub>''q''</sub>[''x''] if and only if <math> \gcd \left (f,x^{q^{n_i}}-x \right )=1</math>, for 1 ≤ ''i'' ≤ ''k'', and ''f'' divides <math>x^{q^n}-x</math>. In fact, if ''f'' has a factor of degree not dividing ''n'', then ''f'' does not divide <math>x^{q^n}-x</math>; if ''f'' has a factor of degree dividing ''n'', then this factor divides at least one of the <math>x^{q^{n_i}}-x.</math>
| |||