# How can I convert numbers into prime numbers?

I'm working with one-way accumulators, but I'm not knowledgable in cryptography. Is there an easy peasy way to hash numbers (or whatever) into prime numbers? Obviously I'd like it to be collision resistant and all that, but this project is huge, I'm alone and I'm confident someone else in the field will pick up from there. Also, primality tests are linear in n or what? Thanks

• Please expand your question with more detail, it's hard to tell what you're asking for. Also, what does the size of the project have to do with anything? – pg1989 Apr 16 '14 at 3:21
• possible duplicate of How can I generate large prime numbers for RSA? – rath Apr 16 '14 at 3:50
• @gurghet I think the question is how to deterministically and efficiently map a given interger to a prime such that you can safely accumulate it in an RSA based accumulator? – DrLecter Apr 16 '14 at 5:16
• Hashing to primes is easy. Just seed a PRNG with the hash of the input and use it to generate a prime with any standard algorithm. – CodesInChaos Apr 16 '14 at 7:09
• Welcome to Cryptography Stack Exchange. From your answer, it seems like you have some more needs which are not clearly stated in the question. Maybe you could expand your question a bit? – Paŭlo Ebermann Apr 18 '14 at 13:50

Thank you for your answers but I think I found a better method.

1. Take the hash of your input $h(x)$, preferably with random oracle approximation
2. Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
3. Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
4. Write to memory: $H(x)=p$

Done!

notes:

1. The random oracle makes collisions infeasible

2. Universal hashing gives high density of primes with high probability (there is a theorem out there but the principle is that, for a given prime, I have multiple hash outputs, so the probability that one of them is my input increases. See: Gennaro et al. - Secure hash-and-sign signatures without the Random Oracle, lemma 2)

• What is $k$? Why the universal hashing function? I don't see how this is "better" than the standard PRNG method CodesInChaos suggested in the comments. – Thomas Apr 16 '14 at 7:46
• Why $h(x)$? If this works there are only $k$ bits to play with in step 2. Thus only $2^k$ tests in the worst case. – gurghet Apr 16 '14 at 7:52
• k is just a small int. The random oracle protects me from collisions @Thomas – gurghet Apr 16 '14 at 7:53
• @gurghet Again, what advantage does this scheme have over using a PRNG? You can't claim it's "better" without giving any explanation, you should elaborate so future people reading this can understand why. – Thomas Apr 16 '14 at 8:24
• You state without reference "Universal hashing gives high density of primes with high probability". I fail to see why, and doubt it. And I fail to see why it would matter, for the input of the universal hash is prime in your method, not the output. -- Trying $p$ until $f(p)=h(x)$ is expected to require $2^{w-1}$ steps where $w$ is the output width of $h$, and thus impractical. -- The method outlined by CodesInChaos seems just fine to me. – fgrieu Apr 16 '14 at 14:48