2
$\begingroup$

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 ?

Improve this question
$\endgroup$
6
  • $\begingroup$ See mathoverflow.net/q/3820 $\endgroup$
    – Max Alekseyev
    Commented Mar 12 at 22:21
  • $\begingroup$ @MaxAlekseyev but unlike mathoverflow.net/a/10062 knowing a large number is made of 2 prime divisors don t simplify factorization. $\endgroup$
    – user2284570
    Commented Mar 12 at 22:43
  • 2
    $\begingroup$ There are some methods to create unfactored semiprimes with elliptic curves, but I don't know the details. See graysage.com/djr/isp.txt and eprint.iacr.org/2021/1610 . What do you need it for? $\endgroup$
    – Daniel Weber
    Commented Mar 14 at 6:40
  • $\begingroup$ @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. $\endgroup$
    – user2284570
    Commented Mar 14 at 12:55
  • 1
    $\begingroup$ 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) $\endgroup$
    – Daniel Weber
    Commented Mar 14 at 13:01

0

Reset to default

You must log in to answer this question.