**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

[ Cryptology ePrint archive ]