Sharper ABC-based bounds for congruent polynomials
Journal de Théorie des Nombres de Bordeaux, Tome 17 (2005) no. 3, pp. 721-725.

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.2degh-0.2degradABC 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.2degh-0.2degradABC en 2degh-degradABC. La deuxième amélioration est une généralisation à A 1 ,,A m de degré au plus ((3m-5)/(3m-7))degh-(6/(3m-7)m)degradA 1 A m , avec m3.

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.2degh-0.2degradABC 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 2degh-degradABC. The second improvement generalizes to m3 polynomials A 1 ,,A m of degree at most ((3m-5)/(3m-7))degh-(6/(3m-7)m)degradA 1 A m .

@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},
     mrnumber = {2212120},
     zbl = {05016582},
     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
DA  - 2005///
SP  - 721
EP  - 725
VL  - 17
IS  - 3
PB  - Université Bordeaux 1
UR  - http://www.numdam.org/articles/10.5802/jtnb.515/
UR  - https://www.ams.org/mathscinet-getitem?mr=2212120
UR  - https://zbmath.org/?q=an%3A05016582
UR  - https://doi.org/10.5802/jtnb.515
DO  - 10.5802/jtnb.515
LA  - en
ID  - JTNB_2005__17_3_721_0
ER  - 
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/

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

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

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

Cité par Sources :