On 2014-03-11 23:14, Daniel Kahn Gillmor wrote:
More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of pi, followed by 64 more bits of 0xFF. I don't know why this sequence was selected. Does anyone have any pointers to reasons you might want the modulus structured this way?
- If the least significant word of the modulus equals 2^w-1, Montgomery reduction becomes more efficient. - If the most significant word of the modulus equals 2^w-1, school-book reduction and Barrett reduction becomes more efficient. - Pi usually plays the role of a "nothing-up-my-sleeve" value. If a random value had been chosen, there would have been no easy way to verify that a specially crafted value hadn't been chosen. For instance, it is possible to generate a prime, such that the discrete logarithm of selected smooth numbers becomes to known to the entity generating the prime, and that would make the discrete logarithm problem easier for that entity.
i haven't yet generated these (mainly due to time): * 4096-bit (MODP 16) * 6144-bit (MODP 17) * 8192-bit (MODP 18)
Python is likely too slow for this. Generating the 8192 bit prime takes a couple of hours on a contemporary PC using reasonably optimized native code.