Sharper ABC-based bounds for congruent polynomials

Daniel J. Bernstein

doi:10.5802/jtnb.515

Daniel J. Bernstein

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}$ .

Publié le : 2009-03-16

MR 2212120 | Zbl 05016582

DOI : https://doi.org/10.5802/jtnb.515

@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/

Bibliographie

[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