2

Let that $n\in\Bbb N$ 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 ?

user2284570
  • 151
  • See https://mathoverflow.net/q/3820 – Max Alekseyev Mar 12 '24 at 22:21
  • @MaxAlekseyev but unlike https://mathoverflow.net/a/10062 knowing a large number is made of 2 prime divisors don t simplify factorization. – user2284570 Mar 12 '24 at 22:43
  • 2
    There are some methods to create unfactored semiprimes with elliptic curves, but I don't know the details. See http://www.graysage.com/djr/isp.txt and https://eprint.iacr.org/2021/1610 . What do you need it for? – Command Master Mar 14 '24 at 06:40
  • @CommandMaster question is about random numbers not generating such numbers. I’m not interested in generating such numbers but finding such numbers in the result of a specific custom hash function. – user2284570 Mar 14 '24 at 12:55
  • 1
    As far as I know there aren't any such results then, but I also don't know any proof of equivalence (and I don't expect that one exists) – Command Master Mar 14 '24 at 13:01
  • It is a folklore conjecture that this will be about as difficult as factoring in general. The answer of Terry Tao in the earlier linked question above helps give part of the reason for why we think this. – JoshuaZ Mar 23 '24 at 17:09

0 Answers0