For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Factorization of Square-Free Integers with High Bits Known
Bagus SANTOSO Noboru KUNIHIRO Naoki KANAYAMA Kazuo OHTA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
factorization, lattice, Coppersmith's method,
Full Text: PDF(332.9KB)>>
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.