DaylightingSociety / Paillier

Paillier Homomorphic Addition Public Key Cryptosystem
GNU Lesser General Public License v3.0
18 stars 9 forks source link

Change primality test #1

Closed tfdahlin closed 6 years ago

tfdahlin commented 6 years ago

Little Fermat isn't as effective as we want for testing primes; specifically, it cannot detect Carmichael numbers. We should be using Miller-Rabin primality testing instead. According to a stack overflow response I found, 50 rounds of Miller-Rabin is much less likely to cause an error than a cosmic bit-flip, and should be suitable for our use case. I'm unsure how this will affect current key generation speed in comparison to our current implementation.

Source: https://stackoverflow.com/questions/4159333/rsa-and-prime-generator-algorithms/4160517#4160517

tfdahlin commented 6 years ago

Updated to use 50 rounds of Miller-Rabin, does not seem to affect speed much, if at all.

milo-trujillo commented 6 years ago

For historical clarity, this issue relates to the following commit: https://github.com/DaylightingSociety/Paillier/commit/bf2fae8a969229395752e86d59321c4806c604b3