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
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$– pg1989Apr 16, 2014 at 3:21
-
$\begingroup$ possible duplicate of How can I generate large prime numbers for RSA? $\endgroup$– rathApr 16, 2014 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$– DrLecterApr 16, 2014 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$– CodesInChaosApr 16, 2014 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 EbermannApr 18, 2014 at 13:50
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
11
Thank you for your answers but I think I found a better method.
- Take the hash of your input $h(x)$, preferably with random oracle approximation
- Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
- Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
- Write to memory: $H(x)=p$
Done!
notes:
The random oracle makes collisions infeasible
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)
-
$\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$– ThomasApr 16, 2014 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$– gurghetApr 16, 2014 at 7:52
-
$\begingroup$ k is just a small int. The random oracle protects me from collisions @Thomas $\endgroup$– gurghetApr 16, 2014 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$– ThomasApr 16, 2014 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, 2014 at 14:48
$\begingroup$
$\endgroup$
8
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.
-
-
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, 2020 at 16:46
-
5$\begingroup$ I would definitely like to see a proof of this. It smells like BS. $\endgroup$ Jan 20, 2020 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$ Jan 20, 2020 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, 2020 at 22:03