|
Title:
|
On the modular inversion hidden number problem.
|
|
Author:
|
Ling, San.; Shparlinski, Igor E.; Steinfeld, Ron.; Wang, Huaxiong.
|
|
Copyright year:
|
2011 |
|
Abstract:
|
We give a rigorous deterministic polynomial time algorithm for the modular inversion hidden number problem introduced by D. Boneh, S. Halevi and N. A. Howgrave-Graham in 2001. For
our algorithm we need to be given about 2/3 of the bits of the output, which matches one of the heuristic algorithms of D. Boneh, S. Halevi and N. A. Howgrave-Graham and answers one of their open questions. However their more e cient algorithm that requires only 1/3 of the bits of the output still remains heuristic. |
|
Subject:
|
DRNTU::Science::Mathematics. |
|
Type:
|
Journal Article |
|
Series/ Journal Title:
|
Journal of symbolic computation |
|
School:
|
School of Physical and Mathematical Sciences |
|
Rights:
|
© 2011 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Journal of Symbolic Computation, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: http://dx.doi.org.ezlibproxy1.ntu.edu.sg/10.1016/j.jsc.2011.09.002 |
|
Version:
|
Accepted version |
