Paper 2025/150 Original: eprint.iacr.org/2025/150 ↗
On pairs of primes with small order reciprocity
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.
- History
- 2025-08-07: last updated
- 2025-01-31: published
- Short URL
- https://ia.cr/2025/150
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}