Skip to content
naulon
Not checkedNot checked for notices yet.

Generating safe primes

von zur Gathen Joachim, Shparlinski Igor E.

Journal of Mathematical Cryptology · 2013

doi:10.1515/jmc-2013-5011 (opens in a new tab)

We email you when a new notice or a question about this paper appears.

Abstract

Safe primes and safe RSA moduli are used in several cryptographic schemes. The most common notion is that of a prime p, where is also prime. The latter is then a Sophie Germain prime. Under appropriate heuristics, they exist in abundance and can be generated efficiently. But the modern methods of analytic number theory have – so far – not even allowed to prove that there are infinitely many of them. Thus for this notion of safe primes, there is no algorithm in the literature that is unconditionally proven to terminate, let alone to be efficient. This paper considers a different notion of safe primes and moduli. They can be generated in polynomial time, without any unproven assumptions, and are good enough for the cryptographic applications that we are aware of.

Abstract licence: CC BY

References33

    33 more references, whose wording the paper’s licence keeps private.

    Reads

    Read by people on this page

    None yet.

    Checked or read by AI through naulon

    None yet.

    A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.

    Are you an author?

    Is this your paper?

    Claim it to add your note and be paid when agents cite it. Free.