Paper 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.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
factoringnumber theoryRSA
Contact author(s)
shirase @ fun ac jp
History
2017-05-15: last of 2 revisions
2017-05-11: received
See all versions
Short URL
https://ia.cr/2017/403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/403,
      author = {Masaaki Shirase},
      title = {Condition on composite numbers easily factored with elliptic curve method},
      howpublished = {Cryptology ePrint Archive, Paper 2017/403},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/403}},
      url = {https://eprint.iacr.org/2017/403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.