crypto/rsa: use Div instead of GCD for trial division
Div is way faster. We could actually test a lot more primes and still
gain performance despite the diminishing returns, but necessarily it
would have marginal impact overall.
fips140: off
goos: linux
goarch: amd64
pkg: crypto/rsa
cpu: AMD Ryzen 7 PRO 8700GE w/ Radeon 780M Graphics
│
e325b41ad1 │
0f611af2e1 │
│ sec/op │ sec/op vs base │
GenerateKey/2048-16 124.19m ± 0% 39.93m ± 0% -67.85% (p=0.000 n=20)
Surprisingly, the performance gain is similar on ARM64, which doesn't
have intrinsified math.Div.
fips140: off
goos: darwin
goarch: arm64
pkg: crypto/rsa
cpu: Apple M2
│
e325b41ad1 │
6276161a7f │
│ sec/op │ sec/op vs base │
GenerateKey/2048-8 136.49m ± 0% 47.97m ± 1% -64.86% (p=0.000 n=20)
Change-Id: I6a6a46560331198312bd09c1cbe4d2b3c370c552
Reviewed-on: https://go-review.googlesource.com/c/go/+/639955
Reviewed-by: Junyang Shao <shaojunyang@google.com>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Russ Cox <rsc@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Daniel McCarney <daniel@binaryparadox.net>