[Cryptography] Factoring safe semiprimes

[Peter Fairbrother]

On 19/10/2025 00:41, Pierre Abbat wrote:
[...]
> As to safe primes, a safe prime is a number p such that both p and (p-1)/2 are
> prime. I don't think they're necessary, and safe primes have zero density
> within primes. 

I'm not sure what you mean by zero density?

Afaik most people think there isn't a largest safe prime, though that is 
not proven, and the usual density estimate is > 1/(ln n)^2 within 
integers, or >> 1/ln |p| within primes.

Also OpenSSL can use safe primes, so there doesn't seem to be any 
practical lack of them.

In the (bad?) old days we generated primes for RSA where p-1 had a prime 
factor of at least 128 bits, to avoid smoothness of p-1 and Pollard's 
p-1 attack. This was increased in RFC's to up to 256 bits, which is 
pretty standard now except where safe primes are used.

However these do not fulfil what we might call Cai's criterion.

I have long been in favour of the use of safe primes, not for some 
specific technical property but because non-safe primes add useless 
structure which an attacker may be able to exploit.

Safe primes are also harder to attack with Shor as the cycle-finding 
part needs to find a bigger cycle, but if Cai can be taken to mean that 
they provide positive resistance to Shor, then well and good.

The only downside I can see is their lower density, but in the ranges 
typically  used for DH and RSA I don't see that as a problem.


Peter Fairbrother