4 ms·
The problem is that since the qualities of these special semi-primes that allow SNFS to work on them is not very well understood there is not an easy way to tes
by vabmit 10y ago
The problem is that since the qualities of these special semi-primes that allow SNFS to work on them is not very well understood there is not an easy way to test if an attacker could use SNFS rather than GNFS. Additionally, running SNFS (or GNFS) on a semi-prime is not guaranteed to result in a factorization. Unlucky polynomial choice, for example, is one of the reasons such an attempt may fail. So, you could expend massive resources attempting to perform an SNFS factorization and not have a clear answer.
If you go into the Linux kernel (or other software) and look at the randomness testing and primality testing code, you can see that it is not extremely complex. Basic checks include things like making sure that a stream of data from /dev/random is not just a repetition of the pattern 1010101010101010... Prime candidates are typically checked with trail division routines. After making it through the basic checks, software will typically do something more advanced and computationally expensive. Usually, a Miller-Rabin test is run on the candidate number. That is usually all there is to it. Extensive verification of cryptographic primitives ("random" large primes, etc) is typically not feasible.