TY - JOUR
T1 - On RSA moduli with prescribed bit patterns
AU - Shparlinski, Igor E.
PY - 2006/4
Y1 - 2006/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=32944467360&partnerID=8YFLogxK
U2 - 10.1007/s10623-005-3137-2
DO - 10.1007/s10623-005-3137-2
M3 - Article
AN - SCOPUS:32944467360
SN - 0925-1022
VL - 39
SP - 113
EP - 122
JO - Designs, Codes and Cryptography
JF - Designs, Codes and Cryptography
IS - 1
ER -