整数系数多项式的分解是有算法的,最原始的算法称为Kronecker方法:设整系数多项式 那么对于整数 一定整除 在已知 的情况下, 是已知的,此时 只有有限种选择。分别取 那么 维向量 必然在有限集合 内。对 的每个元素,用待定系数法可以求出一个不超过 次的多项式,在其中找到整除 的即可。