On the modular inversion hidden number problem

San Ling*, Igor E. Shparlinski, Ron Steinfeld, Huaxiong Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)358-367
Number of pages10
JournalJournal of Symbolic Computation
Volume47
Issue number4
DOIs
Publication statusPublished - Apr 2012

Fingerprint Dive into the research topics of 'On the modular inversion hidden number problem'. Together they form a unique fingerprint.

Cite this