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.