Skip to main content
5 of 7
composite --> divisor
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

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 divisors 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 divisors…

Or was it ever be proven even for probabilistic cases that’s not different from computing the number of factors ?