On some subgroups of the multiplicative group of finite rings

Voloch, José Felipe

Journal de théorie des nombres de Bordeaux, Tome 16 (2004) no. 1, pp. 233-239.

Soit $S$ un sous-ensemble de ${\mathbf{F}}_q$, le corps à $q$ éléments et $h\in {\mathbf{F}}_q\left[x\right]$ un polynôme de degré $d>1$ sans racines dans $S$. On considère le groupe généré par l’image de $\{x-s\mid s\in S\}$ dans le groupe des unités de l’anneau ${\mathbf{F}}_q\left[x\right]/\left(h\right)$. 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 ${\mathbf{F}}_q$, the field of $q$ elements and $h\in {\mathbf{F}}_q\left[x\right]$ a polynomial of degree $d>1$ with no roots in $S$. Consider the group generated by the image of $\{x-s\mid s\in S\}$ in the group of units of the ring ${\mathbf{F}}_q\left[x\right]/\left(h\right)$. 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.

[AKS] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P. http://www.cse.iitk.ac.in/news/primality.html.

[B] D. Bernstein, Proving primality after Agrawal-Kayal-Saxena. http://cr.yp.to/papers.html.

[B2] D.  Bernstein, Sharper ABC-based bounds for congruent polynomials. http://cr.yp.to/ntheory.html.

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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