On pairs of primes with small order reciprocity

Craig Costello; Gaurish Korpal

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: 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}
}