Close values of shifted modular inversions and the decisional modular inversion hidden number problem
Igor E. Shparlinski · Advances in Mathematics of Communications · 2015
We give deterministic polynomialtime algorithms for two different decision version the modularinversion hidden number problemintroduced by D. Boneh, S. Halevi and N. A. Howgrave-Grahamin 2001. For example, for one of our algorithms we need to be given about $1/2$ of thebits of each inversion, while for the computationalversion the best known algorithm requires about $2/3$ of the bitsand is probabilistic.