# [Cryptography] What type of nearest prime is most likely to be useful?

Phillip Hallam-Baker phill at hallambaker.com
Thu Aug 6 14:13:15 EDT 2020

```A while back, I asked about next prime generation for use with Shamir
secret sharing.

I have since revised my spec after discovering that my previous approach of
rounding up secrets to a multiple of 32 bits was a bad plan. So I now have
a list of offsets that are to be used to deterministically generate a list
of primes p such that:

2^n < p < 2^(n+8)

I am using these for Shamir secret sharing which is information theoretic
secure so there are two obvious choices:

p = Nextprime (2^n)  or   p = PreviousPrime (2^(n+8))

I have generated both tables (attached in case someone feels like
checking). Question is which is the better choice for other applications?

I am inclined to pick  p = Nextprime (2^n) because that results in the
least bias when selecting a random number in the interval 0 <= r < p using
the modulo reduction approach:

Select n+8 bits of randomness, reduce modulo p.

So for an 8 bit value p = 257. Generate a 2^16 bit value and the
probability the result is 0 will be 1/256 and the probability it will be
1-256 will be 1/255. Which is not completely flat but near enough for most
purposes. And we can get the result as flat as we like using n+32 or such.

So what to pick or doesn't it matter?

public readonly static int[] PrimeOffsetNext = new int[] {
1,            1,         43,          15,
15,          21,         81,          13,
15,          13,          7,          61,
111,         25,        451,          51,
85,         175,        253,           7,
87,         427,         27,         133,
235,        375,        423,         735,
357,        115,         81,         297,
175,         57,         45,         127,
61,          37,         91,          27,
15,         241,        231,          55,
105,        127,        115,         231,
207,        181,         37,         235,
163,       1093,        187,         211,
21,         841,        445,         165,
777,        583,        133,          75
};

public readonly static int[] PrimeOffsetPrevious = new int[] {
5,           15,          3,           5,
87,          59,          5,          59,
93,          65,        299,          17,
17,          75,        119,         159,
113,         83,         17,          47,
257,        233,         33,         237,
75,         299,        377,          63,
567,        467,        237,         189,
275,        237,         47,         167,
285,         75,        203,         197,
155,          3,        119,         657,
719,        315,         57,         317,
107,        593,       1005,         435,
389,        299,         33,         203,
627,        437,        209,          47,
17,         257,        503,         569
};
-------------- next part --------------
An HTML attachment was scrubbed...