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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| 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 |
| id |
sg-ntu-dr.10356-98740 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.10356-987402023-02-28T19:37:24Z On the modular inversion hidden number problem Ling, San Shparlinski, Igor E. Steinfeld, Ron Wang, Huaxiong School of Physical and Mathematical Sciences DRNTU::Science::Mathematics 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. Accepted version 2012-04-11T03:58:35Z 2019-12-06T19:59:06Z 2012-04-11T03:58:35Z 2019-12-06T19:59:06Z 2011 2011 Journal Article Ling, S., Shparlinski, I.E., Steinfeld, R., & Wang, H. (2011). On the modular inversion hidden number problem. Journal of Symbolic Computation, 47(4), 358-367. https://hdl.handle.net/10356/98740 http://hdl.handle.net/10220/7718 10.1016/j.jsc.2011.09.002 en Journal of symbolic computation © 2011 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Journal of Symbolic Computation, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: http://dx.doi.org.ezlibproxy1.ntu.edu.sg/10.1016/j.jsc.2011.09.002 11 p. application/pdf |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
DRNTU::Science::Mathematics |
| spellingShingle |
DRNTU::Science::Mathematics Ling, San Shparlinski, Igor E. Steinfeld, Ron Wang, Huaxiong On the modular inversion hidden number problem |
| description |
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. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Ling, San Shparlinski, Igor E. Steinfeld, Ron Wang, Huaxiong |
| format |
Article |
| author |
Ling, San Shparlinski, Igor E. Steinfeld, Ron Wang, Huaxiong |
| author_sort |
Ling, San |
| title |
On the modular inversion hidden number problem |
| title_short |
On the modular inversion hidden number problem |
| title_full |
On the modular inversion hidden number problem |
| title_fullStr |
On the modular inversion hidden number problem |
| title_full_unstemmed |
On the modular inversion hidden number problem |
| title_sort |
on the modular inversion hidden number problem |
| publishDate |
2012 |
| url |
https://hdl.handle.net/10356/98740 http://hdl.handle.net/10220/7718 |
| _version_ |
1759852922897694720 |