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.
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.
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.
It's still interesting though.
These "weak" primes are perfect for backdoors, however, if you know about them being weak, and noone else does.
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.