A new modular algorithm for computation of algebraic number polynomial gcds
A new modular algorithm for computation of algebraic number polynomial gcds
复制标题
一种计算代数多项式gcd的新模块化算法
DOI：
10.1145/74540.74552
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Trevor J. Smedley
中科院分区：
文献类型：
--
作者：
Trevor J. Smedley
2.算法设Q上的Q是代数的，p（z）是定义Q上a的最小多项式。不失一般性，假设pc Z [z]（否则我们可以选择定义相同字段的不同CY）。因此p是躁狂的，在Z上是不可约的，p（e）= 0，且令k= degree（p）。设u，vc Q（a）[x]是我们要计算的gcd的多项式，设g-gcd（u，v）。假设u，ve Z [cr][x]，并且它们的前导系数是整数，否则将它们乘以适当的因子。该算法由以下步骤组成：1）计算dc Z，使得dg E Z [a][x]。见[l]计算这样的整数的方法。2)选择m，IZ 6 Z，使得p（n）E0 mod m（即mb（n）），并且m与lcoeff（u），Icoeff（v）和d互质。
2. The Algorithm Let QI be algebraic over Q and p (z) be the minimal polynomial defining a over Q. Without loss of generality, assume pc Z [z](otherwise we can choose a different CY which defines the same field.) Thus p is manic, is irreducible over Z, p (e)= 0, and let k= degree (p). Let u, vc Q (a)[x] be the polynomials we want to compute the gcd of and let g-gcd (u, v). Assume that u, ve Z [cr][x], and that their leading coefficients are integers, otherwise multiply them by an appropriate factor. The algorithm consists of the following steps: 1) Compute d c Z such that dg E Z [a][x]. See [l] for methods of calculating such an integer. 2) Choose m, IZ 6 Z such that p (n) E 0 mod m (ie mb (n)), and m is relatively prime to lcoeff (u), Icoeff (v) and d.