Faster Factoring of Integers of a Special Form

Rene PERALTA  Eiji OKAMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A    No.4    pp.489-493
Publication Date: 1996/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
factoring,  computational number theory,  cryptography, ESIGN,  

Full Text: PDF(404.2KB)>>
Buy this Article


Summary: 
A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ2, where P is a prime sufficiently smaller than Q. The result is of interest to cryptographers, since integers with secret factorization of this form are being used in digital signatures. The algorithm makes use of what we call Jacobi signatures. We believe these to be of independent interest.