On the modular inversion hidden number problem
Shparlinski, Igor E.
Date of Issue2011
School of Physical and Mathematical Sciences
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.
Journal of symbolic computation
© 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