hashing to primes

[burdges]

In https://github.com/poanetwork/vdf/blob/master/vdf/src/create_discriminant.rs#L60 you choose a prime of the form n + m x where m has many small prime factors https://github.com/poanetwork/vdf/blob/master/vdf/build.rs#L82

How does m having many prime factors improve uniformity for the prime? You site https://eprint.iacr.org/2011/401.pdf but I do not really know that literature so no explination jumped out at me.

I suppose the second hashing-to-a-prime function hash_prime in https://github.com/poanetwork/vdf/blob/master/vdf/src/proof_wesolowski.rs#L112 can use a simpler algorithm because it generates only 128 bit primes.

[afck]

I'm not sure about it, but I think it's not about making the primes more uniform, but rather about speeding up the prime number generation by picking a number that is likely to be a prime (because m has many factors and n is coprime to them).

I believe it was inspired by Chia's inkfish.

I'm also confused by that comment at the end, though.

[burdges]

We'd create an extremely non-uniform distribution of primes found if we used p = n + 2 x where x is incremented by 1 each time. I could imagine making them more uniform could become important, except maybe we've so many starting positions n that even 2 creates a secure distribution. I would not precompute the VDF for some number of very high probability primes, but maybe some more informed attack can exploit the bias.

It appears the hash_prime function worries about this for smaller primes, but the sieve scheme is surely faster for larger primes created for the discriminate. I'd kinda imagine p = n + (log n) x should avoid any bias, although I had no proof of this fact. It's quite a mystery why p = n + m x avoids bias with such a small m, but..

Thank you for linking inkfish though. I'd missed the link earlier in the file. In fact, the inkfish file links https://eprint.iacr.org/2011/481.pdf so maybe @DemiMarie simply miss-copied the reference?