### Prime pairing in algorithms searching for smooth group order

Pavel Atnashev and George Woltman

##### Abstract

Factorization methods like P−1, P+1, ECM have a stage which deals with primes of $a ± b$ form, where $a + b$ and $a − b$ are processed by a single operation. Selecting $a$ and $b$ such that both $a + b$ and $a − b$ are prime is called prime pairing and can significantly improve performance of the stage. This paper introduces new methods of pairing, which in some cases find pairs for up to 99.9% of primes in a range. A practical algorithm and its implementations are presented.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
factoring
Contact author(s)
patnashev @ gmail com
History
Short URL
https://ia.cr/2021/1462

CC BY

BibTeX

@misc{cryptoeprint:2021/1462,
author = {Pavel Atnashev and George Woltman},
title = {Prime pairing in algorithms searching for smooth group order},
howpublished = {Cryptology ePrint Archive, Paper 2021/1462},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1462}},
url = {https://eprint.iacr.org/2021/1462}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.