diff options
author | Russ Cox <rsc@golang.org> | 2010-01-05 16:49:05 -0800 |
---|---|---|
committer | Russ Cox <rsc@golang.org> | 2010-01-05 16:49:05 -0800 |
commit | cfbee34a277d75c19b843c27ef053b78c493b32d (patch) | |
tree | 5d009f6b279ef18b4c2dd473f027cde70e56920b | |
parent | e032ab9dc86877978064846f67ef4f1537912eda (diff) | |
download | go-cfbee34a277d75c19b843c27ef053b78c493b32d.tar.gz go-cfbee34a277d75c19b843c27ef053b78c493b32d.zip |
big: fix ProbablyPrime bug, comments
(changes adopted from alc, agl)
R=agl1, agl
CC=golang-dev
https://golang.org/cl/181137
-rw-r--r-- | src/pkg/big/int.go | 2 | ||||
-rw-r--r-- | src/pkg/big/int_test.go | 7 | ||||
-rw-r--r-- | src/pkg/big/nat.go | 9 |
3 files changed, 14 insertions, 4 deletions
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go index 5a0f7c0dfd..b48954ef8b 100644 --- a/src/pkg/big/int.go +++ b/src/pkg/big/int.go @@ -356,7 +356,7 @@ func GcdInt(d, x, y, a, b *Int) { // ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. // If it returns true, z is prime with probability 1 - 1/4^n. // If it returns false, z is not prime. -func ProbablyPrime(z *Int, reps int) bool { return !z.neg && probablyPrime(z.abs, reps) } +func ProbablyPrime(z *Int, n int) bool { return !z.neg && probablyPrime(z.abs, n) } // Rsh sets z = x >> s and returns z. diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go index b2c33fcc45..c178bab770 100644 --- a/src/pkg/big/int_test.go +++ b/src/pkg/big/int_test.go @@ -474,8 +474,15 @@ var primes = []string{ "5", "7", "11", + + "13756265695458089029", + "13496181268022124907", + "10953742525620032441", + "17908251027575790097", + "98920366548084643601728869055592650835572950932266967461790948584315647051443", "94560208308847015747498523884063394671606671904944666360068158221458669711639", + // http://primes.utm.edu/lists/small/small3.html "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163", "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593", diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go index 877bc98112..da9f1d735c 100644 --- a/src/pkg/big/nat.go +++ b/src/pkg/big/nat.go @@ -596,6 +596,9 @@ func powersOfTwoDecompose(n []Word) (q []Word, k Word) { // possible. n is the bit length of limit. func randomN(z []Word, rand *rand.Rand, limit []Word, n int) []Word { bitLengthOfMSW := uint(n % _W) + if bitLengthOfMSW == 0 { + bitLengthOfMSW = _W + } mask := Word((1 << bitLengthOfMSW) - 1) z = makeN(z, len(limit), false) @@ -616,7 +619,7 @@ func randomN(z []Word, rand *rand.Rand, limit []Word, n int) []Word { } } - return z + return normN(z) } @@ -702,8 +705,8 @@ const ( var bigOne = []Word{1} var bigTwo = []Word{2} -// ProbablyPrime performs n Miller-Rabin tests to check whether n is prime. -// If it returns true, n is prime with probability 1 - 1/4^n. +// ProbablyPrime performs reps Miller-Rabin tests to check whether n is prime. +// If it returns true, n is prime with probability 1 - 1/4^reps. // If it returns false, n is not prime. func probablyPrime(n []Word, reps int) bool { if len(n) == 0 { |