On RSA moduli with almost half of the bits prescribed (Q1003703)

From MaRDI portal
Revision as of 02:36, 29 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
On RSA moduli with almost half of the bits prescribed
scientific article

    Statements

    On RSA moduli with almost half of the bits prescribed (English)
    0 references
    0 references
    0 references
    4 March 2009
    0 references
    For an integer \(n \geq 1\), let \(M_n\) denote the set of RSA moduli \(m=pl\) that are products of two distinct primes \(p\) and \(l\) such that \(2^{n-1} < p, l < 2^n\). The authors show that using character sum estimates due \textit{H. Iwaniec} [Invent. Math. 23, 97--104 (1974; Zbl 0275.10024)] leads to an improvement of recent results about the distribution and finding RSA moduli \(m \in M_n\) with prescribed bit patterns. More exactly, it is shown that the algorithm previously proposed by the second author [Des. Codes Cryptography 39, No. 1, 113--122 (2006; Zbl 1172.11047)] allows to specify in expected polynomial time about \(n\) bits instead of about \(n/2\) bits as in the above paper of I. Shparlinski. Also some other arithmetic and combinatorial applications of the same result of H. Iwaniec are demonstrated.
    0 references
    bit patterns
    0 references
    character sums
    0 references
    smooth integers
    0 references
    Hadamard matrices
    0 references
    sparse integers
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references