mpp_sieve incorrectly records composites and slows down prime number generation

RESOLVED FIXED in 3.27

Status

NSS
Libraries
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: ttaubert, Assigned: ttaubert)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Assignee)

Description

2 years ago
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.
(Assignee)

Comment 1

2 years ago
Created attachment 8780147 [details] [diff] [review]
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.
Attachment #8780147 - Flags: review?(franziskuskiefer)
(Assignee)

Updated

2 years ago
Blocks: 1272818
(Assignee)

Comment 3

2 years ago
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 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!
Attachment #8780147 - Flags: review?(franziskuskiefer) → review+
https://hg.mozilla.org/projects/nss/rev/f8b37bbd8432
Status: ASSIGNED → RESOLVED
Last Resolved: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.27
You need to log in before you can comment on or make changes to this bug.