tree 23163d582cfff54661eee51ab20d3b1b645214ca
parent f3bd757ee5e7ad409d2fdf7c3bb5fdfa5f0a307a
author David Benjamin <davidben@google.com> 1570937079 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1571171357 +0000

Do fewer trial divisions for larger RSA keygens.

Now that Miller-Rabin can reject composites faster, we can do fewer
trial divisions. Halving the table seems to improve things for RSA-3072
and RSA-4096. I left RSA-2048 alone since measurements with it halved
were a bit more of a wash.

(Although now that I've left it alone, it's gotten faster, so these
numbers are generally noisy.)

Before:
Did 320 RSA 2048 key-gen operations in 30132984us (10.6 ops/sec)
  min: 27703us, median: 81774us, max: 375687us
Did 84 RSA 3072 key-gen operations in 30166627us (2.8 ops/sec)
  min: 86961us, median: 322184us, max: 1170392us
Did 30 RSA 4096 key-gen operations in 30644802us (1.0 ops/sec)
  min: 260916us, median: 772364us, max: 2743435us

After:
Did 345 RSA 2048 key-gen operations in 30103781us (11.5 ops/sec)
  min: 23359us, median: 75033us, max: 267159us
Did 91 RSA 3072 key-gen operations in 30185495us (3.0 ops/sec)
  min: 72531us, median: 267385us, max: 1119039us
Did 38 RSA 4096 key-gen operations in 30473203us (1.2 ops/sec)
  min: 228529us, median: 720027us, max: 2039681us

Change-Id: I52d431347a70572034ced5b7778a2edac8f15173
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38168
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>