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 = {Daniel J. Bernstein},
     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 = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.515/}
}
Daniel J. Bernstein. 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. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.515/

[1] Daniel J. Bernstein, Proving primality in essentially quartic random time. Mathematics of Computation, to appear. | MR 2261028 | Zbl 05120673

[2] Noah Snyder, An alternate proof of Mason’s theorem. Elemente der Mathematik 55 (2000), 93–94. | 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. | Numdam | MR 2145584 | Zbl 1078.11069