Content deleted Content added
ינון גלעדי (talk | contribs) |
|||
Line 183:
which has ''r'' ≥ 2 irreducible factors each of degree ''d''
'''Output:''' The set of monic irreducible factors of ''f''.
Factors := {''f''};
'''while''' Size(Factors) < ''r'' '''do''',
Choose ''h'' in '''F'''<sub>''q''</sub>[''x''] with deg(''h'') < ''n'' at random;
<math>g:=h^{\frac{q^d-1}{2}}- 1 \pmod f</math>
'''for each''' ''u'' '''in''' Factors with deg(''u'') > ''d'' '''do'''
'''if''' gcd(''g'', ''u'') ≠ 1 and gcd(''g'', ''u'') ≠ ''u'', '''then'''
Factors:= Factors<math>\,\setminus\, \{u\}\cup\{(\gcd(g,u),u/\gcd(g,u))\}</math>;
'''endif
'''endwhile'''
'''return''' Factors
The correctness of this algorithm relies on the fact that the ring '''F'''<sub>''q''</sub>[''x'']/''f'' is a direct product of the fields '''F'''<sub>''q''</sub>[''x'']/''f<sub>i</sub>'' where ''f<sub>i</sub>'' runs on the irreducible factors of ''f''. As all these fields have ''q<sup>d</sup>'' elements, the component of ''g'' in any of these fields is zero with probability
| |||