Cryptology ePrint Archive: Report 2017/403

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:

[ Cryptology ePrint archive ]