Galois groups and factoring polynomials over finite fields
Galois groups and factoring polynomials over finite fields
复制标题
有限域上的伽罗瓦群和因式分解多项式
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
Lajos Rónyai
中科院分区：
文献类型：
--
作者：
Lajos Rónyai
设 p 为素数，F 为具有整数系数的多项式。假设F的判别式不能被p整除，m表示F对Q的分裂域的程度，L表示F系数的最大大小。然后，假设广义黎曼假设（GRH），证明F模p的不可约因子可以在deg F、m、log p和L的确定性时间多项式中找到。作为应用，证明在GRH下可以求解 nP=R 形式的某些方程，其中 R 是给定的，P 是多项式时间内在 GF(p) 上定义的椭圆曲线的未知点（n 以一元计数）。证明了最近在有限域光滑乘法子群的帮助下获得的因式分解多项式结果的椭圆模拟。<<ETX>>
Let p be a prime and F be a polynomial with integer coefficients. Suppose that the discriminant of F is not divisible by p, and denote by m the degree of the splitting field of F over Q and by L the maximal size of the coefficients of F. Then, assuming the generalized Riemann hypothesis (GRH), it is shown that the irreducible factors of F modulo p can be found in deterministic time polynomial in deg F, m, log p, and L. As an application, it is shown that it is possible under GRH to solve certain equations of the form nP=R, where R is a given and P is an unknown point of an elliptic curve defined over GF(p) in polynomial time (n is counted in unary). An elliptic analog of results obtained recently about factoring polynomials with the help of smooth multiplicative subgroups of finite field is proved.<<ETX>>