1
$\begingroup$

Consider I need to assign a large distinct prime number to each element in a large set. This must be deterministic so the function always gives me the same prime to the same value.

  1. What is the most efficient way to do this (if there is any).

  2. Would this function work if I need to find millions of prime number to assign them to the set elements.

Btw.: With “large prime number”, I mean the one is usually considered for RSA.

Improve this question
$\endgroup$
24
  • $\begingroup$ Note: I'm aware of the other posts, but they consider only a couple of large prime numbers. $\endgroup$
    – user153465
    Oct 8, 2014 at 16:29
  • $\begingroup$ Mind if I ask about the problem you're solving? If you're trying to generate a large number of distinct RSA keys, well, there're actually faster approaches... $\endgroup$
    – poncho
    Oct 8, 2014 at 16:46
  • 1
    $\begingroup$ @poncho: That's a bit of a strange requirement given that knowledge of $p_1\cdot p_2$, and $p_1\cdot p_3$, it will be trivial to find $p_1$ (by GCD), then $p_2$ and $p_3$. $\,$ Sieve algorithms can be extended to generate primes far apart from each others; that's standard practice with regular spacing, and I do not rule out that it can be done with more haphazard spacing. $\endgroup$
    – fgrieu ♦
    Oct 8, 2014 at 17:04
  • 2
    $\begingroup$ @user153465: turning a randomized algorithm into a deterministic one is standard practice in crypto: we'll use a CSPRNG seeded with a secret and e.g. the index of the element to which the prime is associated. $\;$ Doing this and using a standard algorithm for RSA primes would be an easy way to solve your problem (as in the present question), save for the most efficient requirement. A standard desktop CPU would generate some hundred 1024-bit primes per second, I guess. $\;$ I'll read and ponder the math.se question. $\endgroup$
    – fgrieu ♦
    Oct 8, 2014 at 17:08
  • 2
    $\begingroup$ @Willem Hengeveld: issues with your idea: $\;$ A) SHA-256 is not wide enough. That's easily fixed with a CSPRNG or KDF $\;$ B) The primes generated are distinguishable from random ones, for the expected gap from such prime to the immediately lower prime is higher. That can be fixed by incrementing by a pseudo-randomly chosen step about (say) 100 times the number of bits in the prime. $\;$ C) This is relatively slow; at the very least, sieving the prime candidates will speed-up things many-fold. $\;$ All this is sometime practiced for RSA. $\endgroup$
    – fgrieu ♦
    Oct 9, 2014 at 9:41

1 Answer 1

Reset to default
2
$\begingroup$

Yes, this is doable. Here is a construction, built out of several basic primitives:

  • Let $R$ be a randomized primality generation algorithm; there are many of them.

    It uses randomness, so let's make the bits of randomness it uses explicit as input: $R(c)$ is the output it produces, when given a random number generator that outputs the random bits $c$.

  • Let $G$ be a cryptographically secure pseudorandom generator: something that stretches a short seed (key) to a long pseudorandom output. You could use AES in CTR mode, or any stream cipher, for this.

  • Let $H$ be a cryptographic hash function, e.g., SHA256.

Now, to element $x$, you can assign the prime number $R(G(H(x)))$ to $x$. It's as simple as that.

This is a deterministic algorithm that will assign a prime to each element, and always assign the same prime to each possible element. Also, if you generate primes from a large enough range, then the primes will almost surely be distinct. For instance, if you generate 256-bit primes, then by the birthday paradox, it is essentially guaranteed that all the primes will be distinct (the chances that two different elements $x,x'$ is exponentially small, and negligible in practice).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your very clear explanation. I'm wondering why cannot we use $x$ as the input of $G()$, so we could eliminate $H()$. $\endgroup$
    – user153465
    Oct 13, 2014 at 20:13
  • $\begingroup$ @user153465, that's because pseudorandom generators require their seed to be uniformly distributed. The way to extract the entropy in a value and make it look uniformly distributed is to use a hash function. Justifying that would probably require some non-trivial cryptographic knowledge (e.g., the random oracle model, definitions of security of a PRG, and so on). Or, you can just trust me that this is a competently engineered cryptographic construction. $\endgroup$
    – D.W.
    Oct 14, 2014 at 21:22

Your Answer

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

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