0
$\begingroup$

Simple question : given a randomly generated number $N$ from a hash that is hard to factor, 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 having big divisors generated from the specific hash function I’m less interested in ruling out candidates…

The miller‑rabin test allows one to check if a number is a prime, but not if it has 2 big prime divisors…

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ I don't believe that there is an easy way to check (that is, a way that is more efficient than finding a factor). There are zero knowledge proofs that a number is a semiprime, but those are useful only if someone knows the factorization (and so can use that knowledge to generate the proof) $\endgroup$
    – poncho
    Commented Mar 12 at 20:45
  • $\begingroup$ @poncho I’m interested in knowing if it’s a semiprime, not finding which are the composites… I recognize such flies might only be killable through a hammer. $\endgroup$
    – user2284570
    Commented Mar 12 at 21:03
  • $\begingroup$ It's unlikely such a capability exists. Can you supply more specific information? You said you have a hash (output of a hash function?) that is hard to factor. How do you know it is hard to factor? Beyond "it's large and odd", I mean. $\endgroup$
    – kodlu
    Commented Mar 13 at 6:51
  • $\begingroup$ @kodlu hard to factor just because large and odd and without small composites like the example I wrote in my question. $\endgroup$
    – user2284570
    Commented Mar 13 at 8:41
  • 1
    $\begingroup$ @kodlu I’m checking for small prime divisors as a preprocessing step. The situation is somewhat similar to the miller‑rabin test in the way it’s easy to rule out a number isn’t prime but hard (without the test) to know if it’s a probable prime… $\endgroup$
    – user2284570
    Commented Mar 13 at 11:33

1 Answer 1

Reset to default
0
$\begingroup$

It’s easy to create a large number that is practically guaranteed to be a semi prime, by multiplying two numbers that are almost sure to be primes. If I tried to create a 1024 bit

Beyoncé semiprime by multiplying two likely 512 bit primes, but one of the two is really composite, I’ll have one factor of 256 bits or shorter.

An attacker might try to factor your public key. Finding a 256 bit factor is of course much easier than finding a 512 bit factor.

You could probably check for a nine or 12 digit prime factor. Beyond that it is very hard.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Except in my case the number has to be randomly generated as I wrote in my question. Chosen (P1*P2) must be equal to hash(Chosen_known_Seed) on the verifier side. $\endgroup$
    – user2284570
    Commented Mar 13 at 12:49
  • $\begingroup$ @user2284570, you should edit your question, to clarify the constraint between the hash and the product instead of adding it as a comment. $\endgroup$
    – kodlu
    Commented Mar 13 at 14:16
  • 1
    $\begingroup$ @kodlu I already told the number to be tested must be random, so that the question never how to build a large semiprime but indeed if a random big integer is 1… $\endgroup$
    – user2284570
    Commented Mar 13 at 14:20
  • $\begingroup$ I wonder what that information would be useful for. $\endgroup$
    – gnasher729
    Commented Mar 13 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.