Check if a Number is Semiprime

Question

I would like to know if there's a quick way to check if a number is semiprime. By far all the links I have seen only tell either how to generate a semiprime or count the number of semiprimes or to factorize it... But I just want to check whether it is one or isn't.

Answer 1

David Broadhurst came up with a provable semiprime back in 2005, based on some ideas from Don Reble and Phil Carmody.

From MathWorld's semiprime -- "In 2005, Don Reble showed how an elliptic pseudo-curve and the Goldwasser-Kilian ECPP theorem could generate a 1084-digit provable semiprime without a known factorization (Reble 2005)."

It's not quick. For quick, you need relative small, factorable numbers.

Answer 2

For small numbers, the best method is to trial-divide by primes (or take the gcd with blocks of primes). If a prime factor is discovered, divide it out and test if the rest is prime or not. If no prime factor is found up to the cube root, it is semiprime if and only if it is not prime (assuming it is > 1). Usually the best order is trial dividing by the first hundred or so primes, checking if the number is itself prime, then finishing the trial division.

For large numbers, do a reasonable amount of trial division, check if the number is prime, run some ECM curves, then factor it completely (with SIQS or NFS, or perhaps even MPQS if the numbers are small enough). This is faster than trial division all the way up to the cube root.

The best way to find out what numbers are 'big' vs. 'small' is to implement both methods and test. As an order of magnitude, 10¹⁴ is probably the largest size where trial division outperforms ECM + MPQS.

It may be possible, for numbers of intermediate size, to use Strassen's algorithm (as improved by Costa & Harvey, building on Bostan, Gaudry, & Schost, themselves building on Chudnovsky & Chudnovsky's improvements on Strassen's original). Asymptotically, this takes time $O(n^{1/6}\log^{2+\varepsilon} n)$ compared to $O(n^{1/3}\log n)$ for trial division (using schoolbook division -- too small for Karatsuba) and $O(\exp(c(\log n)^{1/3}(\log\log n)^{2/3}))$ for the NFS. I haven't seen a practical implementation of this algorithm, so I can't speak to what its true breakpoints might be, but 10⁴⁰ should be a rough upper bound.