add some logic to sample safe primes more efficiently by incertia · Pull Request...
source link: https://github.com/ZenGo-X/rust-paillier/pull/17
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
New issue
add some logic to sample safe primes more efficiently #17
Conversation
Currently the code samples a prime q = 2p + 1 with no assumptions about p. This leads to performing expensive Miller-Rabin tests even in the case where p is not prime. Here we improve the generation of q by sieving p by small primes such that we avoid some common cases where p is not prime.
Awesome 👏🏻
It appears as if clippy received an upgrade between when the last tests were run, causing the build to fail. Would you like me to address the issue here or in a different PR?
Outdated
// FIXME: Why 500?
for _ in 0..500 {
let mut check_prime = true;
for p in SMALL_PRIMES.iter() {
I'm unsure if that is faster, but wouldn't it be more aesthetic if instead of checking each prime separately you would check that gcd((candidate-1)/2,product_of_all_small_primes) == 1 ? Mathematically it is equivalent.
this is some 7687 digit number that we would currently have to compute at the start of the function (or maybe somehow we can make it static?) but we can leave that question up to the maintainer. i believe gcd should terminate faster than multiple modulus operations.
The number can be static or simply embedded in the code, and it isn't that large (compared to typical BigInts we use in crypto code), if it is too large, we can use fewer primes (as a side note: notice that the effect of each additional number we add to SMALL_PRIMES on the performance is getting smaller and smaller).
In retrospect I guess there's no need to introduce another function we can just rewrite sample_safe_prime.
Outdated
// BitManipulation::set_bit(&mut candidate, 0, true);
BigInt::set_bit(&mut candidate, 0, true);
// We flip the 2nd LSB to make sure the candidate is 3 mod 4 because
// (q - 1) / 2 must also be an odd prime..
Remove the redundant dot in the end of the line.
@incertia I think rewriting sample_safe_prime makes sense.
What do you think about creating a function are_all_primes that takes a Vec<BigInt> and checks whether all inputs are prime?
It will make the first test (dividing by small primes) on all inputs, then the fermat test on all of them and then "miller_rabin" test on all of them.
It will return false the moment any of the tests return false on any of the numbers in the given vector.
Then, the original is_prime will be using this function with a vector of size 1 and the rewrite of sample_safe_prime will check that both p and q are both primes using the are_all_primes function.
What do you think about creating a function
are_all_primes
This function does appear to be a bit arcane in its use case and I'll leave that up to the maintainer. I will commit an updated version of the PR later today.
@incertia I've updated the pull request according to my suggestion so the sample_safe_prime checks that both p,q are prime using are_all_prime.
The way are_all_prime work first checks for both p,q that they are not divisible by the set of small primes and only later performs the miller-rabin test just like you are trying to do in the original PR.
Does it make sense to you?
Will now add a commit so travis-ci will pass.
PR looks great! Thanks for writing comments and making it clear what every set_bit means. I have a few purely stylistic suggestions — following them is not critical.
Outdated
let two = BigInt::from(2);
let four = &two + &two;
This works as well:
let four = BigInt::from(4);
Outdated
// To ensure the appropiate size
// we set the MSB of the candidate.
BitManipulation::set_bit(&mut q, bitsize - 1, true);
Just for unification matters, I'd suggest to change this line to look similar to two set_bit calls above:
Note also that there's a most native and shorter form of calling set_bit, but that's just a matter of choice:
q.set_bit(bitsize - 1, true);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
No one assigned
None yet
No milestone
Successfully merging this pull request may close these issues.
None yet
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK