Factorization of Square-Free Integers with High Bits Known

スポンサーリンク

概要

• 論文の詳細を見る

• 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+ε/k-1)log2N high-order bits of each prime factor are given. For a fixed ε, 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.

• （社）電子情報通信学会の論文
• 2008-01-01

著者

• OHTA Kazuo

  Dept. of Informatics, The University of Electro-Communications

• Santoso Bagus

  Dept. Of Information-communications Engineering The University Of Electro-communications

• Santoso Bagus

  Dept. Of Information-communications Engineering University Of Electro-communications

• KUNIHIRO Noboru

  Dept. of Information-Communications Engineering, University of Electro-Communications

• KANAYAMA Naoki

  Dept. of Risk Engineering, Faculty of Systems and Information Engineering, University of Tsukuba

• Kanayama Naoki

  Dept. Of Risk Engineering Faculty Of Systems And Information Engineering University Of Tsukuba

• Kunihiro Noboru

  Dept. Of Information-communications Engineering University Of Electro-communications

• Ohta Kazuo

  Dept. Of Information-communications Engineering University Of Electro-communications

• Ohta Kazuo

  Dept. Of Informatics The University Of Electro-communications

関連論文

• An Efficient Authentication for Lightweight Devices by Perfecting Zero-Knowledgeness
• Factorization of Square-Free Integers with High Bits Known
• A New 'On the Fly' Identification Scheme : An Asymptoticity Trade-Off between ZK and Correctness
• An Efficient Authentication for Lightweight Devices by Perfecting Zero-Knowledgeness

スポンサーリンク