Let be a subset of , the field of elements and a polynomial of degree with no roots in . Consider the group generated by the image of in the group of units of the ring . 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.
Soit un sous-ensemble de , le corps à éléments et un polynôme de degré sans racines dans . On considère le groupe généré par l’image de dans le groupe des unités de l’anneau . 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.
@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}, mrnumber = {2145584}, zbl = {1078.11069}, language = {en}, url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.445/} }
TY - JOUR AU - José Felipe Voloch TI - On some subgroups of the multiplicative group of finite rings JO - Journal de théorie des nombres de Bordeaux PY - 2004 SP - 233 EP - 239 VL - 16 IS - 1 PB - Université Bordeaux 1 UR - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.445/ DO - 10.5802/jtnb.445 LA - en ID - JTNB_2004__16_1_233_0 ER -
%0 Journal Article %A José Felipe Voloch %T On some subgroups of the multiplicative group of finite rings %J Journal de théorie des nombres de Bordeaux %D 2004 %P 233-239 %V 16 %N 1 %I Université Bordeaux 1 %U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.445/ %R 10.5802/jtnb.445 %G en %F 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, Volume 16 (2004) no. 1, pp. 233-239. doi : 10.5802/jtnb.445. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.445/
[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
Cited by Sources: