Cryptology ePrint Archive: Report 2002/109

A New Class of Unsafe Primes

Qi Cheng

Abstract: In this paper, a new special-purpose factorization algorithm is presented, which finds a prime factor $p$ of an integer $n $ in polynomial time, if $4p-1$ has the form $d b^2$ where $d \in \{3, 11, 19, 43, 67, 163\}$ and $b$ is an integer. Hence such primes should be avoided when we select the RSA secret keys. Some generalizations of the algorithm are discussed in the paper as well.

Category / Keywords: public-key cryptography / RSA, integer factoring, elliptic curve factorization

Date: received 3 Aug 2002

Contact author: qcheng at cs ou edu

Available format(s): PDF | BibTeX Citation

Version: 20020804:215732 (All versions of this report)

Short URL: ia.cr/2002/109

Discussion forum: Show discussion | Start new discussion