On the modular inversion hidden number problem

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 efficient algorithm that requires only 1/3 of the bits of the output still remains heuristic.

► We give a polynomial time algorithm for the modular inversion hidden number problem.
► Our algorithm is deterministic and is rigorously analyzed.
► It needs to be given about 2/3 of the bits of the output.
► It answers an open question of Boneh et al.