TY - JOUR
T1 - On the modular inversion hidden number problem
AU - Ling, San
AU - Shparlinski, Igor E.
AU - Steinfeld, Ron
AU - Wang, Huaxiong
PY - 2012/4
Y1 - 2012/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84857371394&partnerID=8YFLogxK
U2 - 10.1016/j.jsc.2011.09.002
DO - 10.1016/j.jsc.2011.09.002
M3 - Article
AN - SCOPUS:84857371394
SN - 0747-7171
VL - 47
SP - 358
EP - 367
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
IS - 4
ER -