Close values of shifted modular inversions and the decisional modular inversion hidden number problem

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We give deterministic polynomial time algorithms for two different decision version the modular inversion hidden number problem introduced by D. Boneh, S. Halevi and N. A. Howgrave-Graham in 2001. For example, for one of our algorithms we need to be given about 1=2 of the bits of each inversion, while for the computational version the best known algorithm requires about 2=3 of the bits and is probabilistic.

Original languageEnglish
Pages (from-to)169-176
Number of pages8
JournalAdvances in Mathematics of Communications
Volume9
Issue number2
DOIs
Publication statusPublished - 1 May 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'Close values of shifted modular inversions and the decisional modular inversion hidden number problem'. Together they form a unique fingerprint.

Cite this