<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small">A while back, I asked about next prime generation for use with Shamir secret sharing.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">2^n < p < 2^(n+8)</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">I am using these for Shamir secret sharing which is information theoretic secure so there are two obvious choices:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">p = Nextprime (2^n)  or   p = PreviousPrime (2^(n+8))</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">I have generated both tables (attached in case someone feels like checking). Question is which is the better choice for other applications?</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Select n+8 bits of randomness, reduce modulo p.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">So what to pick or doesn't it matter?</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default"><div class="gmail_default">        public readonly static int[] PrimeOffsetNext = new int[] {</div><div class="gmail_default">            1,            1,         43,          15,</div><div class="gmail_default">            15,          21,         81,          13,</div><div class="gmail_default">            15,          13,          7,          61,</div><div class="gmail_default">            111,         25,        451,          51,</div><div class="gmail_default">            85,         175,        253,           7,</div><div class="gmail_default">            87,         427,         27,         133,</div><div class="gmail_default">            235,        375,        423,         735,</div><div class="gmail_default">            357,        115,         81,         297,</div><div class="gmail_default">            175,         57,         45,         127,</div><div class="gmail_default">            61,          37,         91,          27,</div><div class="gmail_default">            15,         241,        231,          55,</div><div class="gmail_default">            105,        127,        115,         231,</div><div class="gmail_default">            207,        181,         37,         235,</div><div class="gmail_default">            163,       1093,        187,         211,</div><div class="gmail_default">            21,         841,        445,         165,</div><div class="gmail_default">            777,        583,        133,          75</div><div class="gmail_default">            };</div><div class="gmail_default"><br></div><div class="gmail_default">        public readonly static int[] PrimeOffsetPrevious = new int[] {</div><div class="gmail_default">            5,           15,          3,           5,</div><div class="gmail_default">            87,          59,          5,          59,</div><div class="gmail_default">            93,          65,        299,          17,</div><div class="gmail_default">            17,          75,        119,         159,</div><div class="gmail_default">            113,         83,         17,          47,</div><div class="gmail_default">            257,        233,         33,         237,</div><div class="gmail_default">            75,         299,        377,          63,</div><div class="gmail_default">            567,        467,        237,         189,</div><div class="gmail_default">            275,        237,         47,         167,</div><div class="gmail_default">            285,         75,        203,         197,</div><div class="gmail_default">            155,          3,        119,         657,</div><div class="gmail_default">            719,        315,         57,         317,</div><div class="gmail_default">            107,        593,       1005,         435,</div><div class="gmail_default">            389,        299,         33,         203,</div><div class="gmail_default">            627,        437,        209,          47,</div><div class="gmail_default">            17,         257,        503,         569</div><div class="gmail_default">            };</div></div><div class="gmail_default" style="font-size:small"><br></div></div></div></div></div></div>