1
$\begingroup$

Suppose that I give you the challenge of successfully factoring any very big random number. That is, you pick a big random number (say, 65536 bits) and try to factor it. If you manage to, you win. If you don't, you can keep trying, or pick another random number, until you factor any big number. How hard is to win this challenge?

To put it in another way, suppose that I offer you a lot of money if you give me a tuple (nonce, rnd, factors), where nonce is any number selected by you, rnd is the 65536-bit variable length SHA3 output of the nonce, and factors is the list of prime factors of rnd. Will you be able to take my money?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

Yes, this is feasible. Just generate sufficiently many nonce, rnd values, and you will eventually stumble upon a prime (or a number that can be factored into a large prime and a number of small prime factors). This is how most probabilistic prime generators operate.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Ah, makes sense. The probability that a number is prime is roughly 1/ln(n), so it isn't that unlikely that a big random number is prime, and primality checks are fast. So, after a few attempts we find a prime one and immediately answer the challenge. Thanks for the answer. $\endgroup$
    – MaiaVictor
    Commented Mar 4, 2020 at 23:47
  • $\begingroup$ Just to be a little bit more precise, finding a random 64-bit prime number takes roughly 44 attempts, and it scales linearly, so finding a random 128-bit prime number takes roughly 88 attempts and so on. So, to be precise, the stated problem has at least a O(N) solution, where N is the hash size in bits and is, thus, very easy (not considering the complexity of the primality check though). $\endgroup$
    – MaiaVictor
    Commented Mar 5, 2020 at 0:03

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.