Geodesic
An algorithm for generating a~pair of special primes
Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 160-162.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, a modification is described for an algorithm generating the pair of prime integers $p,q$ such that the integers $g=\frac12(p-1,q-1)$ and $h=\frac1{2g}(pq-1)$ are also prime. The primes $p,q$ satisfied this condition are called common primes. In 2006 M. J. Hinek introduced such primes for the variant of RSA cryptosystem resistant to small private exponent attacks. The original algorithm for generating common primes can be optimized with the modification described here. The optimized algorithm is two times faster in worst case and more times in average. It takes 19 seconds to generate a pair of $512$-bit common primes $p,q$ with $384$-bit prime $g$. The modification uses sieving technique which is also mentioned in the paper of M. J. Hinek. Despite the speed up of the algorithm, the generation of common primes still takes much more time than the generation of typical primes used in RSA cryptosystem.
Keywords: special primes, Common Prime RSA. 
@article{PDMA_2014_7_a67,
     author = {K. D. Zhukov and A. S. Rybakov},
     title = {An algorithm for generating a~pair of special primes},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {160--162},
     publisher = {mathdoc},
     number = {7},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2014_7_a67/}
}
TY  - JOUR
AU  - K. D. Zhukov
AU  - A. S. Rybakov
TI  - An algorithm for generating a~pair of special primes
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2014
SP  - 160
EP  - 162
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2014_7_a67/
LA  - ru
ID  - PDMA_2014_7_a67
ER  - 
%0 Journal Article
%A K. D. Zhukov
%A A. S. Rybakov
%T An algorithm for generating a~pair of special primes
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2014
%P 160-162
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2014_7_a67/
%G ru
%F PDMA_2014_7_a67
K. D. Zhukov; A. S. Rybakov. An algorithm for generating a~pair of special primes. Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 160-162. http://geodesic.mathdoc.fr/item/PDMA_2014_7_a67/

[1] Hinek M. J., “Another look at small RSA exponents”, LNCS, 3860, 2006, 82–98 | MR | Zbl

[2] Hinek M. J., Cryptanalysis of RSA and Its Variants, CRC Press, 2009 | MR

[3] Shoup V., NTL – a library for doing number theory, http://www.shoup.net