Tag Info

New answers tagged

11

If $p=2q+1$ is a safe prime (i.e. $q$ is a prime as well), then $p-1=2q$ has two prime factors: $2$ and $q$.


3

All the properties discussed in the question are for strong primes $p$ in the context of using $p$ as a secret factor of a large composite $n$ which factorization should be intractable; these properties are given in the landmark RSA paper (1978), without justification. Properties thought for (often public) primes used in other cryptosystems can be different. ...


1

Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter $p$ or $q$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or ...


1

According to PKCS, a strong prime p is a prime with the following properties: Factorisation of (p-1) contains a large prime $p_1$, Factorisation of (p+1) contains a large prime $p_2$. This is equivalent to: $$p=2\times a_1 \times p_1+1=2\times a_2\times p_2-1$$ the integer $a_i$ are suffisently small compared to $p_i$. Choosing $a_i$= 1 leads to bad ...


4

A Sophie Germain prime is a prime $p$ such that $2p+1$ is prime (that later prime is deemed a safe prime). For small examples, see A005384 in the OEIS. A random integer $n$ has odds commensurate to $1/\log(n)^2$ to be a Sophie Germain prime. Therefore, there's in the order of $2^{495}$ Sophie Germain primes of 511 bits, way too much to enumerate them, much ...



Top 50 recent answers are included