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

  • $\begingroup$ 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? $\endgroup$ – pg1989 Apr 16 '14 at 3:21
  • $\begingroup$ possible duplicate of How can I generate large prime numbers for RSA? $\endgroup$ – rath Apr 16 '14 at 3:50
  • 2
    $\begingroup$ @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? $\endgroup$ – DrLecter Apr 16 '14 at 5:16
  • 3
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Apr 16 '14 at 7:09
  • 1
    $\begingroup$ Welcome to Cryptography Stack Exchange. From your question, it seems like you have some more needs which are not clearly stated in the question. Maybe you could expand your question a bit? $\endgroup$ – 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$



  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)

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Thomas Apr 16 '14 at 7:46
  • $\begingroup$ 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. $\endgroup$ – gurghet Apr 16 '14 at 7:52
  • $\begingroup$ k is just a small int. The random oracle protects me from collisions @Thomas $\endgroup$ – gurghet Apr 16 '14 at 7:53
  • $\begingroup$ @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. $\endgroup$ – Thomas Apr 16 '14 at 8:24
  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Apr 16 '14 at 14:48

Misiec´s conjecture:


$$x= \frac{1}{n \cdot n^{\frac{1}{2} + n \cdot 2 \cdot i}}$$

if $n$ is a prime number then the $\sin(x)=x$, and if not the number is not a prime number.

Even though the conjecture does not hold true the $x$ value obtained turns a non-prime number into a complex prime number.

| improve this answer | |
  • $\begingroup$ Can I turn this into an algorithm? $\endgroup$ – gurghet Jan 20 at 13:47
  • 1
    $\begingroup$ Welcome, Luis. Can you check the algorithm for correctness? MathJax explanation is here. Please also provide a reference to the conjecture, it seems hard to find. $\endgroup$ – Maarten Bodewes Jan 20 at 16:46
  • 5
    $\begingroup$ I would definitely like to see a proof of this. It smells like BS. $\endgroup$ – user253751 Jan 20 at 17:45
  • $\begingroup$ The equality seems to always hold, thus the conjecture looks false: bit.ly/2tr9xJq Zooming on the prime 7, the curves do not join, so I guess the difference between the curves comes from computation errors: bit.ly/2G6OnD5 $\endgroup$ – A. Hersean Jan 20 at 17:53
  • $\begingroup$ sorry i do not have a proof as it came to me by verifying that the sumation of the zeta function when divided by n when n is a prime all the numbers expressed by the equation f(x) you get a result where the sin of x is equal x, $\endgroup$ – luis felipe massena misiec Apr 10 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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