# zbMATH — the first resource for mathematics

On some subgroups of the multiplicative group of finite rings. (English) Zbl 1078.11069
Let $$S$$ be a subset of the finite field $$\mathbb F_q$$ of $$q$$ elements and $$h$$ a polynomial over $$\mathbb F_q$$ of degree at least $$2$$ with no roots in $$S$$. The author proves several lower bounds on the size of the group $$G$$ generated by the image of $$\{x-s:s \in S \}$$ in the group of units of the ring $$\mathbb F_q[X]/(h)$$. These bounds are needed in the analysis of the running time of the recent polynomial time primality testing algorithm of M. Agrawal, N. Kayal and N. Saxena [“PRIMES is in $$P$$”. Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)].

##### MSC:
 11T55 Arithmetic theory of polynomial rings over finite fields 11Y11 Primality
##### Keywords:
polynomial rings; linear polynomials; primality testing
Full Text:
##### References:
 [1] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P. . [2] D. Bernstein, Proving primality after Agrawal-Kayal-Saxena. . [3] D. Bernstein, Sharper ABC-based bounds for congruent polynomials. . · Zbl 1093.11019 [4] F. Chung, Diameters and Eigenvalues. JAMS 2 (1989), 187-196. · Zbl 0678.05037 [5] S.D. Cohen, Polynomial factorisation and an application to regular directed graphs. Finite Fields and Appl. 4 (1998), 316-346. · Zbl 0957.11049 [6] G. Frey, M. Perret, H. Stichtenoth, On the different of abelian extensions of global fields. Coding theory and algebraic geometry (Luminy, 1991), Lecture Notes in Math. 1518, 26-32. Springer, Berlin, 1992. · Zbl 0776.11067 [7] N.M. Katz, Factoring polynomials in finite fields: An application of Lang-Weil to a problem of graph theory. Math. Annalen 286 (1990), 625-637. · Zbl 0708.05029 [8] H.W. Lenstra Jr., Primality testing with cyclotomic rings. · Zbl 1429.11221 [9] W.F. Lunnon, P.A.B. Pleasants, N.M. Stephens, Arithmetic properties of Bell numbers to a composite modulus I. Acta Arith. 35 (1979), 1-16. · Zbl 0408.10006 [10] I. Shparlinski, The number of different prime divisors of recurrent sequences. Mat. Zametki 42 (1987), 494-507. · Zbl 0635.10006 [11] J.F. Voloch, Jacobians of curves over finite fields. Rocky Mountain Journal of Math. 30 (2000), 755-759. · Zbl 1016.11023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.