Paper 2025/150

On pairs of primes with small order reciprocity

Craig Costello, Queensland University of Technology
Gaurish Korpal, University of Arizona
Abstract

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, with the exception of 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Contact author(s)
craig costello @ qut edu au
gkorpal @ arizona edu
History
2025-02-01: approved
2025-01-31: received
See all versions
Short URL
https://ia.cr/2025/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/150,
      author = {Craig Costello and Gaurish Korpal},
      title = {On pairs of primes with small order reciprocity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/150},
      year = {2025},
      url = {https://eprint.iacr.org/2025/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.