**Condition on composite numbers easily factored with elliptic curve method**

*Masaaki Shirase*

**Abstract: **For a composite integer $N$ that we would like to factor, we consider a condition for the elliptic curve method using $N$ as a scalar value to succeed and show that if $N$ has a prime factor $p$ such that $p=(DV^2+1)/4,\ V \in {\mathbb Z},\ D\in \{$3, 11, 19, 35, 43, 51, 67, 91, 115, 123, 163, 187, 235, 267, 403, 427$\}$, we can find a non-trivial divisor of $N$ (multiple of $p$) in a short time. In the authors' implementation on PARI/GP, a 1024-bit $N$ was factored in a few seconds when $p$ was 512 bits.

**Category / Keywords: **foundations / factoring, number theory, RSA

**Date: **received 10 May 2017, last revised 14 May 2017

**Contact author: **shirase at fun ac jp

**Available format(s): **PDF | BibTeX Citation

**Note: **I knew a previous work by Cheng (ePrint 2002/10) from a reader.
Thus, I introduced and compared with Cheng's work.

**Version: **20170515:040518 (All versions of this report)

**Short URL: **ia.cr/2017/403

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]