Factorization of Square-Free Integers with High Bits Known

Bagus SANTOSO; Noboru KUNIHIRO; Naoki KANAYAMA; Kazuo OHTA

doi:10.1093/ietfec/e91-a.1.306

Factorization of Square-Free Integers with High Bits Known

Bagus SANTOSO, Noboru KUNIHIRO, Naoki KANAYAMA, Kazuo OHTA

Full Text Views

0

Share
Cite this

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 ()log₂ N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log₂ 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.1 pp.306-315

Publication Date: 2008/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.1.306

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Cryptanalysis

Cite this

Copy

Bagus SANTOSO, Noboru KUNIHIRO, Naoki KANAYAMA, Kazuo OHTA, "Factorization of Square-Free Integers with High Bits Known" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 1, pp. 306-315, January 2008, doi: 10.1093/ietfec/e91-a.1.306.
Abstract: 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 ()log₂ N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log₂ 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.1.306/_p

Copy

@ARTICLE{e91-a_1_306,
author={Bagus SANTOSO, Noboru KUNIHIRO, Naoki KANAYAMA, Kazuo OHTA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Factorization of Square-Free Integers with High Bits Known},
year={2008},
volume={E91-A},
number={1},
pages={306-315},
abstract={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 ()log₂ N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log₂ 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.},
keywords={},
doi={10.1093/ietfec/e91-a.1.306},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Factorization of Square-Free Integers with High Bits Known
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 306
EP - 315
AU - Bagus SANTOSO
AU - Noboru KUNIHIRO
AU - Naoki KANAYAMA
AU - Kazuo OHTA
PY - 2008
DO - 10.1093/ietfec/e91-a.1.306
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2008
AB - 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 ()log₂ N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log₂ 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.
ER -