Sharper ABC-based bounds for congruent polynomials

Bernstein, Daniel J.

doi:10.5802/jtnb.515

Bernstein, Daniel J.¹

¹ Department of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago Chicago, IL 60607–7045

Journal de théorie des nombres de Bordeaux, Tome 17 (2005) no. 3, pp. 721-725.

Résumé
Abstract

Agrawal, Kayal, et Saxena ont récemment introduit une nouvelle méthode pour montrer qu’un entier est premier. La vitesse de cette méthode dépend des minorations prouvées pour la taille du semi-groupe multiplicatif engendré par plusieurs polynômes modulo un autre polynôme $h$ . Voloch a trouvé une application du théoreme ABC de Stothers et Mason dans ce contexte : sous de petites hypothèses, des polynômes distincts $A, B, C$ de degré au plus $1.2 deg h - 0.2 deg rad A B C$ ne peuvent pas être tous congrus modulo $h$ . Nous présentons deux améliorations de la partie combinatoire de l’argument de Voloch. La première amélioration augmente $1.2 deg h - 0.2 deg rad A B C$ en $2 deg h - deg rad A B C$ . La deuxième amélioration est une généralisation à $A_{1}, \dots, A_{m}$ de degré au plus $((3 m - 5) / (3 m - 7)) deg h - (6 / (3 m - 7) m) deg rad A_{1} \dots A_{m}$ , avec $m \geq 3$ .

Agrawal, Kayal, and Saxena recently introduced a new method of proving that an integer is prime. The speed of the Agrawal-Kayal-Saxena method depends on proven lower bounds for the size of the multiplicative semigroup generated by several polynomials modulo another polynomial $h$ . Voloch pointed out an application of the Stothers-Mason ABC theorem in this context: under mild assumptions, distinct polynomials $A, B, C$ of degree at most $1.2 deg h - 0.2 deg rad A B C$ cannot all be congruent modulo $h$ . This paper presents two improvements in the combinatorial part of Voloch’s argument. The first improvement moves the degree bound up to $2 deg h - deg rad A B C$ . The second improvement generalizes to $m \geq 3$ polynomials $A_{1}, \dots, A_{m}$ of degree at most $((3 m - 5) / (3 m - 7)) deg h - (6 / (3 m - 7) m) deg rad A_{1} \dots A_{m}$ .

MR Zbl

DOI : 10.5802/jtnb.515

Affiliations des auteurs :

Bernstein, Daniel J. ¹

¹ Department of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago Chicago, IL 60607–7045

@article{JTNB_2005__17_3_721_0,
     author = {Bernstein, Daniel J.},
     title = {Sharper {ABC-based} bounds for congruent polynomials},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {721--725},
     publisher = {Universit\'e Bordeaux 1},
     volume = {17},
     number = {3},
     year = {2005},
     doi = {10.5802/jtnb.515},
     zbl = {05016582},
     mrnumber = {2212120},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.515/}
}

TY  - JOUR
AU  - Bernstein, Daniel J.
TI  - Sharper ABC-based bounds for congruent polynomials
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2005
SP  - 721
EP  - 725
VL  - 17
IS  - 3
PB  - Université Bordeaux 1
UR  - http://www.numdam.org/articles/10.5802/jtnb.515/
DO  - 10.5802/jtnb.515
LA  - en
ID  - JTNB_2005__17_3_721_0
ER  -

%0 Journal Article
%A Bernstein, Daniel J.
%T Sharper ABC-based bounds for congruent polynomials
%J Journal de théorie des nombres de Bordeaux
%D 2005
%P 721-725
%V 17
%N 3
%I Université Bordeaux 1
%U http://www.numdam.org/articles/10.5802/jtnb.515/
%R 10.5802/jtnb.515
%G en
%F JTNB_2005__17_3_721_0

Bernstein, Daniel J. Sharper ABC-based bounds for congruent polynomials. Journal de théorie des nombres de Bordeaux, Tome 17 (2005) no. 3, pp. 721-725. doi : 10.5802/jtnb.515. http://www.numdam.org/articles/10.5802/jtnb.515/

Bibliographie
Cité par

[1] Daniel J. Bernstein, Proving primality in essentially quartic random time. Mathematics of Computation, to appear. http://cr.yp.to/papers.html#quartic | MR | Zbl

[2] Noah Snyder, An alternate proof of Mason’s theorem. Elemente der Mathematik 55 (2000), 93–94. http://www.springerlink.com/openurl.asp?genre=article&issn=0013-6018&volume=55&issue=3&spage=93 | MR | Zbl

[3] José Felipe Voloch, On some subgroups of the multiplicative group of finite rings. Journal de Théorie des Nombres de Bordeaux 16 (2004), 1246–7405. http://www.ma.utexas.edu/users/voloch/preprint.html | Numdam | MR | Zbl

Cité par Sources :