This PR aims at improving performance of the safe prime generator. The previous approach was as follows:
1. Generate prime `q` of `nBits - 1`
2. Compute `p = 2q + 1`.
3. Check if `p` is prime. If it is, return `(p,q)`. If not, go back to the point 1.
This approach was simple, but not fast enough. In this PR, we propose an alternative algorithm as well as make the search process concurrent.
The new algorithm is as follows:
1. Generate a random odd number `q` of length `pBitLen-1` with two the most
significant bytes set to `1`.
2. Execute preliminary primality test on `q` checking whether it is coprime
to all the elements of `smallPrimes`. It allows to eliminate trivial
cases quickly, when `q` is obviously no prime, without running an
expensive final primality tests.
If `q` is coprime to all of the `smallPrimes`, then go to the point 3.
If not, add `2` and try again. Do it at most 10 times.
3. Check the potentially prime `q`, whether `q = 1 (mod 3)`. This will
happen for 50% of cases.
If it is, then `p = 2q+1` will be a multiple of 3, so it will be obviously
not a prime number. In this case, add `2` and try again. Do it at most 10
times. If `q != 1 (mod 3)`, go to the point 4.
4. Now we know `q` is potentially prime and `p = 2q+1` is not a multiple of
3. We execute a preliminary primality test on `p`, checking whether
it is coprime to all the elements of `smallPrimes` just like we did for
`q` in point 2. If `p` is not coprime to at least one element of the
`smallPrimes`, then go back to point 1.
If `p` is coprime to all the elements of `smallPrimes`, go to point 5.
5. At this point, we know `q` is potentially prime, and `p=q+1` is also
potentially prime. We need to execute a final primality test for `q`.
We apply Miller-Rabin and Baillie-PSW tests. If they succeed, it means
that `q` is prime with a very high probability. Knowing `q` is prime,
we use Pocklington's criterion to prove the primality of `p=2q+1`, that
is, we execute Fermat primality test to base 2 checking whether
`2^{p-1} = 1 (mod p)`. It's significantly faster than running full
Miller-Rabin and Baillie-PSW for `p`.
If `q` and `p` are found to be prime, return them as a result. If not, go
back to the point 1.
How fast we generate a prime number is mostly a matter of luck and it depends on how lucky we are with choosing the first bytes. With today's multicore processors, we can execute the process on multiple cores concurrently, accept the first valid result and cancel the rest of work. This way, with the same finding algorithm, we can get the result faster. Such an approach is presented in this PR.
Detailed benchmark results are presented in the comment. We can observe an improvement in almost all cases (still, a small factor of luck is needed). I've tested for 512, 1024 and 2048 bit numbers on my MBP 3,1 GHz Intel Core i7 with concurrency level set to 4.
I did not present a result for 2048 bits, since the previous algorithm wasn't able to produce one 2048bit safe prime in one hour so I had nothing to compare.
If you want, you can compare the new approach with the performance of openssl dhparam -5 2048. (512/1024).
This PR aims at improving performance of the safe prime generator. The previous approach was as follows:
```
1. Generate prime `q` of `nBits - 1`
2. Compute `p = 2q + 1`.
3. Check if `p` is prime. If it is, return `(p,q)`. If not, go back to the point 1.
```
This approach was simple, but not fast enough. In this PR, we propose an alternative algorithm as well as make the search process concurrent.
The new algorithm is as follows:
```
1. Generate a random odd number `q` of length `pBitLen-1` with two the most
significant bytes set to `1`.
2. Execute preliminary primality test on `q` checking whether it is coprime
to all the elements of `smallPrimes`. It allows to eliminate trivial
cases quickly, when `q` is obviously no prime, without running an
expensive final primality tests.
If `q` is coprime to all of the `smallPrimes`, then go to the point 3.
If not, add `2` and try again. Do it at most 10 times.
3. Check the potentially prime `q`, whether `q = 1 (mod 3)`. This will
happen for 50% of cases.
If it is, then `p = 2q+1` will be a multiple of 3, so it will be obviously
not a prime number. In this case, add `2` and try again. Do it at most 10
times. If `q != 1 (mod 3)`, go to the point 4.
4. Now we know `q` is potentially prime and `p = 2q+1` is not a multiple of
3. We execute a preliminary primality test on `p`, checking whether
it is coprime to all the elements of `smallPrimes` just like we did for
`q` in point 2. If `p` is not coprime to at least one element of the
`smallPrimes`, then go back to point 1.
If `p` is coprime to all the elements of `smallPrimes`, go to point 5.
5. At this point, we know `q` is potentially prime, and `p=q+1` is also
potentially prime. We need to execute a final primality test for `q`.
We apply Miller-Rabin and Baillie-PSW tests. If they succeed, it means
that `q` is prime with a very high probability. Knowing `q` is prime,
we use Pocklington's criterion to prove the primality of `p=2q+1`, that
is, we execute Fermat primality test to base 2 checking whether
`2^{p-1} = 1 (mod p)`. It's significantly faster than running full
Miller-Rabin and Baillie-PSW for `p`.
If `q` and `p` are found to be prime, return them as a result. If not, go
back to the point 1.
```
How fast we generate a prime number is mostly a matter of luck and it depends on how lucky we are with choosing the first bytes. With today's multicore processors, we can execute the process on multiple cores concurrently, accept the first valid result and cancel the rest of work. This way, with the same finding algorithm, we can get the result faster. Such an approach is presented in this PR.
Detailed benchmark results are presented in the comment. We can observe an improvement in almost all cases (still, a small factor of luck is needed). I've tested for `512`, `1024` and `2048` bit numbers on my MBP 3,1 GHz Intel Core i7 with concurrency level set to 4.
I did not present a result for `2048` bits, since the previous algorithm wasn't able to produce one `2048`bit safe prime in one hour so I had nothing to compare.
If you want, you can compare the new approach with the performance of `openssl dhparam -5 2048`. (512/1024).
The original PR with a discussion/review on our side: https://github.com/keep-network/paillier/pull/8
Go 1.7 moves the golang.org/x/net/context package into the standard library as context. Because of that, import "context" in the safe_prime_generator.go does not compile on Go versions prior to 1.7.
There is no easy way to support older versions without sacrificing quality. Since Go 1.7 was released two years ago, I think that supporting 1.7+ is an acceptable move.
Go 1.7 [moves](https://golang.org/doc/go1.7#context) the `golang.org/x/net/context` package into the standard library as `context`. Because of that, `import "context"` in the `safe_prime_generator.go` does not compile on Go versions prior to 1.7.
There is no easy way to support older versions without sacrificing quality. Since Go 1.7 was released two years ago, I think that supporting 1.7+ is an acceptable move.
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
This PR aims at improving performance of the safe prime generator. The previous approach was as follows:
This approach was simple, but not fast enough. In this PR, we propose an alternative algorithm as well as make the search process concurrent.
The new algorithm is as follows:
How fast we generate a prime number is mostly a matter of luck and it depends on how lucky we are with choosing the first bytes. With today's multicore processors, we can execute the process on multiple cores concurrently, accept the first valid result and cancel the rest of work. This way, with the same finding algorithm, we can get the result faster. Such an approach is presented in this PR.
Detailed benchmark results are presented in the comment. We can observe an improvement in almost all cases (still, a small factor of luck is needed). I've tested for
512,1024and2048bit numbers on my MBP 3,1 GHz Intel Core i7 with concurrency level set to 4.I did not present a result for
2048bits, since the previous algorithm wasn't able to produce one2048bit safe prime in one hour so I had nothing to compare.If you want, you can compare the new approach with the performance of
openssl dhparam -5 2048. (512/1024).The original PR with a discussion/review on our side: https://github.com/keep-network/paillier/pull/8
512-bit
1024-bit
@@ -4,3 +4,2 @@- 1.3- 1.4- 1.7- tipGo 1.7 moves the
golang.org/x/net/contextpackage into the standard library ascontext. Because of that,import "context"in thesafe_prime_generator.godoes not compile on Go versions prior to 1.7.There is no easy way to support older versions without sacrificing quality. Since Go 1.7 was released two years ago, I think that supporting 1.7+ is an acceptable move.
@@ -4,3 +4,2 @@- 1.3- 1.4- 1.7- tipTotally okay with me.
Outstanding code. I learn so much by reading your code review.
Thanks a lot for them.
didier
Thanks! ❤️ 🎉