On RSA moduli with prescribed bit patterns

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticle

14 Citations (Scopus)

Abstract

We give a polynomial time probabilistic algorithm that constructs an RSA modulus M=pl, where p and l are two n-bit primes, which has about n/2 bits, on certain positions, prescribed in advance. Although the number of prescribed bits is less than in other constructions, this algorithm can be rigorously analyzed while the other approaches remain heuristic. The proof is based on bounds of exponential sums. We also show that this algorithm can be used for finding 2n-bit RSA moduli whose binary expansions are of Hamming weight about 3n/4. Finally, similar arguments are also applied to smooth integers.

Original languageEnglish
Pages (from-to)113-122
Number of pages10
JournalDesigns, Codes and Cryptography
Volume39
Issue number1
DOIs
Publication statusPublished - Apr 2006

Fingerprint Dive into the research topics of 'On RSA moduli with prescribed bit patterns'. Together they form a unique fingerprint.

Cite this