tree 036f0e63ae0bf3e5729d36ce82c1dc76b669eb25
parent 40729e374d93cfec69f1a7ae75591610c0bf4ab7
author David Benjamin <davidben@google.com> 1517959950 -0500
committer Adam Langley <alangley@gmail.com> 1522439586 +0000

Change the order of GCD and trial division.

RSA key generation currently does the GCD check before the primality
test, in hopes of discarding things invalid by other means before
running the expensive primality check.

However, GCD is about to get a bit more expensive to clear the timing
leak, and the trial division part of primality testing is quite fast.
Thus, split that portion out via a new bn_is_obviously_composite and
call it before GCD.

Median of 29 RSA keygens: 0m0.252s -> 0m0.207s
(Accuracy beyond 0.1s is questionable.)

Bug: 238
Change-Id: I3999771fb73cca16797cab9332d14c4ebeb02046
Reviewed-on: https://boringssl-review.googlesource.com/26366
Reviewed-by: Adam Langley <alangley@gmail.com>