1
$\begingroup$

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

$\endgroup$
7
  • $\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$ 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$ Apr 18 '14 at 13:50
1
$\begingroup$

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)

$\endgroup$
11
  • $\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
-1
$\begingroup$

Misiec´s conjecture:

Let

$$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.

$\endgroup$
8
  • $\begingroup$ Can I turn this into an algorithm? $\endgroup$
    – gurghet
    Jan 20 '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 '20 at 16:46
  • 5
    $\begingroup$ I would definitely like to see a proof of this. It smells like BS. $\endgroup$
    – user253751
    Jan 20 '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 '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$ Apr 10 '20 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.