[Cryptography] Factoring safe semiprimes

[Pierre Abbat]

On Saturday, October 18, 2025 11:09:58 AM EDT Christian Huitema wrote:
> Is the factor 2/3 arbitrary, or is it the result of some equation?

I think it's arbitrary and could be anything between 1/2 and 1. But I'd have 
to ask Fouvry and Cài to be sure.

> I had the same concern when considered "semiprimes that aren't close to
> being squares". "Close" is an awfully loose term. That could mean, for
> example, that one of the divisors should be greater than p^x, for some x
> larger than 1/2. But how much larger? If that divider is p/3 and p is
> big enough, it is certainly larger than p^(2/3). Does p meet the "safe
> prime" requirement?

I propose the criteria for a semiprime pq:
p^2>q
q^2>p
(p-q)^2>p+q
gcd(p-1,q-1)^3<pq.
The first two are trivially satisfied if p and q have the same number of bits or 
one has one more bit than the other (unless they're 2 and 3, which are way too 
small). The third is the criterion of not being close to square. The fourth, I 
think, should keep the order of numbers mod pq big enough to give Shor 
problems, and prevents the case that p and q are Fouvry primes such that the 
largest prime factor of p-1 and q-1 is the same.

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 suggest this procedure for generating primes:
1. Pick a number l which is the number of bits, such as 4096.
2. Pick coprime a and b where a has l bits and b<cl where c is a small number 
at least 2 (you can round cl up to the next power of 2).
3. Check a, a+b, a+2b, ... until you find a prime. Call it o.
4. Check 2o+1, 4o+1, ... 2clo+1. If at least one of them is a prime (the 
probability of which is positive), select one of those primes and call it p.
5. If none of them is prime, go back to step 2.
As long as 2^l>(2cl)^2, p is a Fouvry prime.

Pierre

-- 
Lanthanidia deliciosa: What the kiwifruit would be
if it weren't so radioactive.