# Tag Info

Accepted

### Why does RSA need p and q to be prime numbers?

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms. Not categorically. Factoring a large integer is trivial if it is only composed of ...
• 596
Accepted

### NIST Diffie-Hellman prime: how was it picked? Where did it come from?

Is this number specified anywhere? It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from ...
• 149k
Accepted

### Why does GMP only run Miller-Rabin test twice when generating a prime?

The Baillie-PSW test is being used in place of 24 Miller-Rabin tests. This is not unreasonable for large numbers when the cost of Miller-Rabin testing can become burdensome and also helps to prevent ...
• 24.1k
Accepted

### Has there ever been any real world consequences of using probabilistic primality tests for RSA or other similar systems?

The probability of accidentally mistaking a composite for a prime, for a number that you chose yourself, is extremely low and quantifiable, as others have mentioned. This is the situation that is ...
• 13.9k

### Why does RSA need p and q to be prime numbers?

The main reasons we usually choose $p$ an $q$ prime numbers are: For a given size of $N=p\,q$, that makes $N$ harder to factor, hence RSA safer. Although efficient factoring algorithms do not find ...
• 143k
Accepted

### How to efficiently generate a random safe prime of given length?

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024"...
Accepted

### Prime factorization (102 digits)

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ ...
• 49.1k

### How to encrypt the number one using RSA?

The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them). In practice, you have to pad (or ...
• 2,528
Accepted

### Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$?

The critical facts enabling to find such $p$ in practice are: We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-...
• 143k
Accepted

• 3,499
Accepted

### Relation between factors and their sum on RSA

Let $n = p \cdot q$ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup. The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both ...
• 49.1k

### Are there prime numbers that are easy to modulo within 40 bits to 60 bits?

First, this is obviously true with no restrictions on $b$. For example, for $b = 2^n-2$ we get that $2^n - b = 2^n - (2^n-2) = 2$ is prime. This is boring, and likely not what you mean (and instead, I ...
• 13.5k

• 149k

• 406

### Factoring 2048 bit number is easy?

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, \$n = 2^...
• 48.8k

### Why does GMP only run Miller-Rabin test twice when generating a prime?

The article, "Strengthening the Baillie-PSW primality test" referred to above, suggests adding a third test to the standard BPSW (MR test base 2 combined with Lucas). But there's a third ...