On the modular inversion hidden number problem

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

Full description

Saved in:
Bibliographic Details
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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 e cient algorithm that requires only 1/3 of the bits of the output still remains heuristic.

Similar Items