| Presentation | 2012-07-20 An Improved Algorithm for Approximate GCD Problems Atsushi TAKAYASU, Noboru KUNIHIRO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we analyze multivariate approximate common divisor problem (ACDP), given approximate multiples of the integer and we recover the integer. So far, via lattice based Coppersmith's theorem, the polynomial time ACDP algorithms have been proposed. In 2001, Howgrave-Graham proposed the polynomial time algorithms for ACDP as long as the tolerated errors are sufficiently small, when given two approximate multiples. In 2011, Cohn and Heninger gave the multivariate generalization of Howgrave-Graham's algorithm, when given plural approximate multiples. In this paper, we analyze only partially approximate common divisor problem (PACDP) when given one exact multiple of the integer. We propose the improved polynomial time algorithm by Cohn and Heninger when given plural approximate multiples. Cohn and Heninger revealed that PACDP can be solved when (α_1+…+α_n)/n<β^<(n+1)/n>. We change the lattice construction by Cohn and Heninger's algorithm and improve the condition ^n√<α_1…α_n><β^<(n+1)/n>. In the left hand side of the inequality, where is the arithmetic mean of α_1,...α_n in Cohn and Heninger's condition become the geometric mean of α_1,...α_n in our condition. Our algorithm can be applied to broader context. Moreover, considering the multivariate generalization of Howgrave-Graham's algorithm, our condition is more natural than Cohn and Heninger's condition. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | approximate-GCD / lattice / Coppersmith's theorem |
| Paper # | ISEC2012-35,SITE2012-31,ICSS2012-37,EMM2012-27 |
| Date of Issue |
| Conference Information | |
| Committee | ICSS |
|---|---|
| Conference Date | 2012/7/12(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information and Communication System Security (ICSS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An Improved Algorithm for Approximate GCD Problems |
| Sub Title (in English) | |
| Keyword(1) | approximate-GCD |
| Keyword(2) | lattice |
| Keyword(3) | Coppersmith's theorem |
| 1st Author's Name | Atsushi TAKAYASU |
| 1st Author's Affiliation | The University of Tokyo() |
| 2nd Author's Name | Noboru KUNIHIRO |
| 2nd Author's Affiliation | The University of Tokyo |
| Date | 2012-07-20 |
| Paper # | ISEC2012-35,SITE2012-31,ICSS2012-37,EMM2012-27 |
| Volume (vol) | vol.112 |
| Number (no) | 128 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |