tree 91b7ddb3c2cb5da5b2edddc71e92fc3b4da66569
parent 18d145e651b6c80ae562bcf41ff804aaad674595
author David Benjamin <davidben@google.com> 1570923581 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1571164916 +0000

Break early on composites in the primality test.

|a| is usually much smaller than |w_bits|. We only need to loop up to
|w_bits| and hide |a| when the value is possibly composite. If
Miller-Rabin has not hit -1 by then, break early.

This speeds up RSA keygen by a bit.

Before:
Did 248 RSA 2048 key-gen operations in 30041496us (8.3 ops/sec)
  min: 31690us, median: 109097us, max: 373911us
Did 71 RSA 3072 key-gen operations in 30096719us (2.4 ops/sec)
  min: 108650us, median: 370844us, max: 1768070us
Did 27 RSA 4096 key-gen operations in 32829007us (0.8 ops/sec)
  min: 205485us, median: 1107051us, max: 4035040us

After:
Did 340 RSA 2048 key-gen operations in 30026342us (11.3 ops/sec)
  min: 24681us, median: 77749us, max: 350477us
Did 67 RSA 3072 key-gen operations in 30089075us (2.2 ops/sec)
  min: 75070us, median: 394220us, max: 1101562us
Did 38 RSA 4096 key-gen operations in 30283788us (1.3 ops/sec)
  min: 284947us, median: 742688us, max: 1970468us

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