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 (1/k+2 + e/k-1)log2N high-order bits of each prime factor are given. For a fixed e, the running time of our algorithm is heuristic polynomial in (log2N). 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.
['Bagus Santoso', 'Noboru Kunihiro', 'Naoki Kanayama', 'Kazuo Ohta']
Factorization of Square-Free Integers with High Bits Known