3 ms·
Assuming at least 768 bits (an RSA number of this size has been factored), the gaps between such numbers are more than 10^232. Even if every number of this form
by cobbal 9y ago
Assuming at least 768 bits (an RSA number of this size has been factored), the gaps between such numbers are more than 10^232. Even if every number of this form was prime, the prime number theorem tells us we can expect one out of every 10^229 primes to be weak.
There could or course be a larger class of such easy primes, but it seems like it's extremely unlikely a prime of this particular form would ever be generated by chance.
- wybiral 9y agoAh, thanks. That's exactly what I was wondering. It's still interesting though.
- jabot 9y agoThanks for that answer. These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.
- peoplewindow 9y agoVery likely that they've been used for that. I once talked to someone who had worked at a company in the 90s that was shipping crypto software. This was shortly after Snowden, so the topic of backdoors came up. He said that back in those days, they'd been visited by the NSA and told to change the primes they were using, otherwise they wouldn't get export clearance. He said they couldn't figure out what was different about the primes they were given - the number passed primality testing, so they switched to using them to avoid being denied export clearance. His theory was that they were pseudoprimes that somehow passed testing because primality tests were statistical and not definitive. But I guess this is an alternative explanation that would also make sense.
- cobbal 9y agoOops, looks like I made several mistakes in the above calculations. For a 768 bit number the primes would be 384 bits each, gaps between numbers of the form "27a^2 ..." would be 10^58 apart, and weak primes would be at worst one out of 10^56. Still extremely unlikely, but not by as much as I thought.