Factorization of Square-Free Integers with High Bits Known

Bagus SANTOSO  Noboru KUNIHIRO  Naoki KANAYAMA  Kazuo OHTA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.1   pp.306-315
Publication Date: 2008/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.1.306
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Cryptanalysis
Keyword: 
factorization,  lattice,  Coppersmith's method,  

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




Summary: 
In this paper we propose an algorithm of factoring any integer N which has k different prime factors with the same bit-length, when about ()log2 N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log2 N). Our factoring algorithm is based on a lattice-based algorithm of solving any k-variate polynomial equation over Z, which might be an independent interest.