1294461 - mpp_sieve incorrectly records composites and slows down prime number generation

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Tim Taubert [:ttaubert] (inactive)]

mpp_sieve() takes a list of prime numbers (which is static and precompiled) and a random number $x. It then takes these primes and marks every number after $x that's divisible by one of these small primes as a composite.

It looks like the implementer tried to have us only record values for odd numbers after $x but that's now what we do. In mpp_make_prime() below we then take the sieved numbers and check/discard the wrong ones.

With this fixed I get a ~2.6x speedup when generating primes. cert.sh and chains.sh run a lot faster, which is nice.

Comment 1

[Tim Taubert [:ttaubert] (inactive)]

Attachment: 0001-Bug-1294461-Fix-mpp_sieve-to-correctly-record-compos.patch

Here's a small patch that speeds up prime number generation by a factor of ~2.6. The good thing is that it doesn't touch the algorithm itself but simply makes us discard the right numbers (composites) instead of possible prime candidates.

Comment 2

[Tim Taubert [:ttaubert] (inactive)]

Build times look great:

https://treeherder.mozilla.org/#/jobs?repo=nss-try&revision=fa12946dc98eef0c5a01fc885b2dfc43c7b9ebe7&filter-tier=1&filter-tier=2&filter-tier=3

Comment 3

[Tim Taubert [:ttaubert] (inactive)]

The Chains tests on ARM finished in 106 and 134 minutes, that's definitely a huge improvement. And wrt bug 1272818, we seem to be even faster than Chrome when generating RSA keys with the WebCrypto API.

Comment 4

[Franziskus Kiefer [:franziskus]]

Comment on attachment 8780147 [details] [diff] [review]
0001-Bug-1294461-Fix-mpp_sieve-to-correctly-record-compos.patch

Review of attachment 8780147 [details] [diff] [review]:
-----------------------------------------------------------------

awesome!

Comment 5

[Franziskus Kiefer [:franziskus]]

https://hg.mozilla.org/projects/nss/rev/f8b37bbd8432