big: fix ProbablyPrime bug, comments
(changes adopted from alc, agl)
R=agl1, agl
CC=golang-dev
https://golang.org/cl/181137
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go
index 5a0f7c0..b48954e 100644
--- a/src/pkg/big/int.go
+++ b/src/pkg/big/int.go
@@ -356,7 +356,7 @@
// 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 b2c33fc..c178bab 100644
--- a/src/pkg/big/int_test.go
+++ b/src/pkg/big/int_test.go
@@ -474,8 +474,15 @@
"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 877bc98..da9f1d7 100644
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -596,6 +596,9 @@
// 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 @@
}
}
- return z
+ return normN(z)
}
@@ -702,8 +705,8 @@
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 {
