## Cryptology ePrint Archive: Report 2021/1462

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.

Category / Keywords: factoring