On the modular inversion hidden number problem

• Main Authors: Ling, San, Shparlinski, Igor E., Steinfeld, Ron, Wang, Huaxiong
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2012
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/98740; http://hdl.handle.net/10220/7718
• Institution: Nanyang Technological University

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...