On some subgroups of the multiplicative group of finite rings
Journal de Théorie des Nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 233-239.

Soit S un sous-ensemble de F q , le corps à q éléments et hF q [x] un polynôme de degré d>1 sans racines dans S. On considère le groupe généré par l’image de {x-ssS} dans le groupe des unités de l’anneau F q [x]/(h). Dans cet article nous présentons les bornes inférieures pour le cardinal de ce groupe. Notre motivation principale est une application au nouvel algorithme polynomial pour tester la primalité [AKS]. Ces bornes ont également des applications à la théorie des graphes et pour majorer le nombre de points rationnels sur les revètement abeliens de la droite projective sur les corps finis.

Let S be a subset of F q , the field of q elements and hF q [x] a polynomial of degree d>1 with no roots in S. Consider the group generated by the image of {x-ssS} in the group of units of the ring F q [x]/(h). In this paper we present a number of lower bounds for the size of this group. Our main motivation is an application to the recent polynomial time primality testing algorithm [AKS]. The bounds have also applications to graph theory and to the bounding of the number of rational points on abelian covers of the projective line over finite fields.

@article{JTNB_2004__16_1_233_0,
     author = {Jos\'e Felipe Voloch},
     title = {On some subgroups of the multiplicative group of finite rings},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {233--239},
     publisher = {Universit\'e Bordeaux 1},
     volume = {16},
     number = {1},
     year = {2004},
     doi = {10.5802/jtnb.445},
     zbl = {1078.11069},
     mrnumber = {2145584},
     language = {en},
     url = {jtnb.centre-mersenne.org/item/JTNB_2004__16_1_233_0/}
}
José Felipe Voloch. On some subgroups of the multiplicative group of finite rings. Journal de Théorie des Nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 233-239. doi : 10.5802/jtnb.445. https://jtnb.centre-mersenne.org/item/JTNB_2004__16_1_233_0/

[AKS] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P. .

[B2] D.  Bernstein, Sharper ABC-based bounds for congruent polynomials. .

[B] D. Bernstein, Proving primality after Agrawal-Kayal-Saxena. .

[C] F. Chung, Diameters and Eigenvalues. JAMS 2 (1989), 187–196. | MR 965008 | Zbl 0678.05037

[Co] S.D. Cohen, Polynomial factorisation and an application to regular directed graphs. Finite Fields and Appl. 4 (1998), 316–346. | MR 1648561 | Zbl 0957.11049

[FPS] 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. | MR 1186413 | Zbl 0776.11067

[K] 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. | MR 1045392 | Zbl 0708.05029

[L] H.W. Lenstra Jr., Primality testing with cyclotomic rings.

[LPS] 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. | MR 536875 | Zbl 0408.10006

[S] I. Shparlinski, The number of different prime divisors of recurrent sequences. Mat. Zametki 42 (1987), 494–507. | MR 917803 | Zbl 0635.10006

[V] J.F. Voloch, Jacobians of curves over finite fields. Rocky Mountain Journal of Math. 30 (2000), 755–759. | MR 1787011 | Zbl 1016.11023