Voloch, José Felipe On some subgroups of the multiplicative group of finite rings. (English) Zbl 1078.11069 J. Théor. Nombres Bordx. 16, No. 1, 233-239 (2004). 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)]. Reviewer: Arne Winterhof (Linz) Cited in 8 Documents MSC: 11T55 Arithmetic theory of polynomial rings over finite fields 11Y11 Primality Keywords:polynomial rings; linear polynomials; primality testing PDF BibTeX XML Cite \textit{J. F. Voloch}, J. Théor. Nombres Bordx. 16, No. 1, 233--239 (2004; Zbl 1078.11069) Full Text: DOI Numdam EuDML 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.