2026/08/04 by Craig Costello, Gaurish Korpal
Mathematics · #math.NT #msc:11A07 #msc:11T22 #msc:11T71 #msc:11A15 #msc:11Y16
paper · pdf · doi:10.1090/conm/840/16821
published as C. Costello and G. Korpal, On pairs of primes with small order reciprocity, in LuCaNT: Databases, Algorithms, and Computational Number Theory, 285--291, Contemp. Math., 840, Amer. Math. Soc., RI, 2026 · 6 pages, LuCaNT 2025
arxiv created 2026/08/04 · arxiv updated 2026/08/05
We give a sieving algorithm for finding pairs of primes with small multiplicative orders modulo each other. This problem is a necessary condition for obtaining constructions of 2-cycles of pairing-friendly curves, which have found use in cryptographic applications. Our database of examples suggests that, except for a well-known infinite family of such primes, instances become increasingly rare as the size of the primes increase. This leads to some interesting open questions for which we hope our database prompts further investigation.