• Russ Cox's avatar
    math/big: add Baillie-PSW test to (*Int).ProbablyPrime · 37d078ed
    Russ Cox authored
    After x.ProbablyPrime(n) passes the n Miller-Rabin rounds,
    add a Baillie-PSW test before declaring x probably prime.
    
    Although the provable error bounds are unchanged, the empirical
    error bounds drop dramatically: there are no known inputs
    for which Baillie-PSW gives the wrong answer. For example,
    before this CL, big.NewInt(443*1327).ProbablyPrime(1) == true.
    Now it is (correctly) false.
    
    The new Baillie-PSW test is two pieces: an added Miller-Rabin
    round with base 2, and a so-called extra strong Lucas test.
    (See the references listed in prime.go for more details.)
    The Lucas test takes about 3.5x as long as the Miller-Rabin round,
    which is close to theoretical expectations.
    
    name                              time/op
    ProbablyPrime/Lucas             2.91ms ± 2%
    ProbablyPrime/MillerRabinBase2   850µs ± 1%
    ProbablyPrime/n=0               3.75ms ± 3%
    
    The speed of prime testing for a prime input does get slower:
    
    name                  old time/op  new time/op   delta
    ProbablyPrime/n=1    849µs ± 1%   4521µs ± 1%  +432.31%   (p=0.000 n=10+9)
    ProbablyPrime/n=5   4.31ms ± 3%   7.87ms ± 1%   +82.70%  (p=0.000 n=10+10)
    ProbablyPrime/n=10  8.52ms ± 3%  12.28ms ± 1%   +44.11%  (p=0.000 n=10+10)
    ProbablyPrime/n=20  16.9ms ± 2%   21.4ms ± 2%   +26.35%   (p=0.000 n=9+10)
    
    However, because the Baillie-PSW test is only added when the old
    ProbablyPrime(n) would return true, testing composites runs at
    the same speed as before, except in the case where the result
    would have been incorrect and is now correct.
    
    In particular, the most important use of this code is for
    generating random primes in crypto/rand. That use spends
    essentially all its time testing composites, so it is not
    slowed down by the new Baillie-PSW check:
    
    name                  old time/op  new time/op   delta
    Prime                104ms ±22%    111ms ±16%      ~     (p=0.165 n=10+10)
    
    Thanks to Serhat Şevki Dinçer for CL 20170, which this CL builds on.
    
    Fixes #13229.
    
    Change-Id: Id26dde9b012c7637c85f2e96355d029b6382812a
    Reviewed-on: https://go-review.googlesource.com/30770
    Run-TryBot: Russ Cox <rsc@golang.org>
    TryBot-Result: Gobot Gobot <gobot@golang.org>
    Reviewed-by: 's avatarRobert Griesemer <gri@golang.org>
    37d078ed
Name
Last commit
Last update
..
archive Loading commit data...
bufio Loading commit data...
builtin Loading commit data...
bytes Loading commit data...
cmd Loading commit data...
compress Loading commit data...
container Loading commit data...
context Loading commit data...
crypto Loading commit data...
database/sql Loading commit data...
debug Loading commit data...
encoding Loading commit data...
errors Loading commit data...
expvar Loading commit data...
flag Loading commit data...
fmt Loading commit data...
go Loading commit data...
hash Loading commit data...
html Loading commit data...
image Loading commit data...
index/suffixarray Loading commit data...
internal Loading commit data...
io Loading commit data...
log Loading commit data...
math Loading commit data...
mime Loading commit data...
net Loading commit data...
os Loading commit data...
path Loading commit data...
plugin Loading commit data...
reflect Loading commit data...
regexp Loading commit data...
runtime Loading commit data...
sort Loading commit data...
strconv Loading commit data...
strings Loading commit data...
sync Loading commit data...
syscall Loading commit data...
testing Loading commit data...
text Loading commit data...
time Loading commit data...
unicode Loading commit data...
unsafe Loading commit data...
vendor/golang_org/x Loading commit data...
Make.dist Loading commit data...
all.bash Loading commit data...
all.bat Loading commit data...
all.rc Loading commit data...
androidtest.bash Loading commit data...
bootstrap.bash Loading commit data...
buildall.bash Loading commit data...
clean.bash Loading commit data...
clean.bat Loading commit data...
clean.rc Loading commit data...
cmp.bash Loading commit data...
iostest.bash Loading commit data...
make.bash Loading commit data...
make.bat Loading commit data...
make.rc Loading commit data...
naclmake.bash Loading commit data...
nacltest.bash Loading commit data...
race.bash Loading commit data...
race.bat Loading commit data...
run.bash Loading commit data...
run.bat Loading commit data...
run.rc Loading commit data...