A study of the well known factoring algorithm over the rationals leads to a generic algorithm for general fields F which are quotient rings of suitable subrings R. The essential step consists of lifting a factorisation modulo a sufficiently large power of a maximal ideal of R to one over R itself. It is shown that this step can be made efficient for algebraic number fields and algebraic function fields over finite fields.
プログラムに戻る