Far Eastern Mathematical Journal

To content of the issue

Calculation of random pairs of primes whose product lies in a given short interval

Bykovskii V.A.

2020, issue 2, . 150154
DOI: https://doi.org/10.47910/FEMJ202016

The paper proposes heuristic algorithms for constructing pairs of random primes, the product of which lies in a given interval $ \left (\Delta, \, \Delta + \delta \right). $ One algorithm refers to the case $ \delta = \sqrt {\Delta }, $ and the second to $ \delta = 30 \Delta^{1/3}. $ They allow in the well-known RSA cryptosystem to choose shorter public keys (twice for the first algorithm and three times for the second).

Number theory, cryptography, RSA cryptosystem

Download the article (PDF-file)


[1] Rivest R. L., Shamir A., Adleman L., Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. ACM, 21:2, (1978), 120126.
[2] Huxley M. N., On the di?erence between consecutive primes, Invent. math., 15, (1972), 164170.

To content of the issue