Skip to main content
1 of 7

How to know if a random natural number is a probable semiprime?

Let that $n$ be a natural number generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ?

My problem is while it’s easy to check if $n$ has more than 2 composites most of the time, I’d like to avoid scenarios where I spend 9 months to discover N == 12027877772555050443795403742217395712075171104339858549779677653443493290409396821629865048061485233472904248389410406204110133340639818638965275807699743 * 10704786482380604791018378393733218626744420453905310617389097906743992630408179842533462993002334496991243299661277538908564708094125756092839493565529001 * 296097401239989775561915012266952427911 (meaning not a semi‑prime).
Also because what interests me in my scenario is using semi‑primes generated from the specific hash function, I’m less interested in ruling out candidates than likely confirming…

The miller‑rabin test allows one to check if a number is prime, but not if it’s made from 2 prime composites…

Or was it ever be proven that there’s no easier solution than factoring ?