diff options
| author | Brian Kessler <brian.m.kessler@gmail.com> | 2017-12-06 09:53:14 -0700 |
|---|---|---|
| committer | Robert Griesemer <gri@golang.org> | 2018-05-30 16:28:46 +0000 |
| commit | 85f4051731f9f2d0514301470d528db94ed5781c (patch) | |
| tree | 70ed73b90b47d725c990a9a72c95980e50ecf093 /src/cmd/vendor/github.com/google/pprof | |
| parent | fd4392ba6f8c593fdfdf19366f3896b668db2824 (diff) | |
| download | go-85f4051731f9f2d0514301470d528db94ed5781c.tar.xz | |
math/big: implement Atkin's ModSqrt for 5 mod 8 primes
For primes congruent to 5 mod 8 there is a simple deterministic
method for calculating the modular square root due to Atkin,
using one exponentiation and 4 multiplications.
A. Atkin. Probabilistic primality testing, summary by F. Morain.
Research Report 1779, INRIA, pages 159–163, 1992.
This increases the speed of modular square roots for these primes
considerably.
name old time/op new time/op delta
ModSqrt231_5Mod8-4 1.03ms ± 2% 0.36ms ± 5% -65.06% (p=0.008 n=5+5)
Change-Id: I024f6e514bbca8d634218983117db2afffe615fe
Reviewed-on: https://go-review.googlesource.com/99615
Reviewed-by: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/cmd/vendor/github.com/google/pprof')
0 files changed, 0 insertions, 0 deletions