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, P. 150–154
DOI: https://doi.org/10.47910/FEMJ202016


Abstract
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).

Keywords:
Number theory, cryptography, RSA cryptosystem

Download the article (PDF-file)

References

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

To content of the issue