math/big: add modular square-root and Jacobi functions
This change adds Int.ModSqrt to compute modular square-roots via the
standard Tonelli-Shanks algorithm, and the Jacobi function that this and
many other modular-arithmetic algorithms depend on.
This is needed by change 1883 (https://golang.org/cl/1883), to add
support for ANSI-standard compressed encoding of elliptic curve points.
Change-Id: Icc4805001bba0b3cb7200e0b0a7f87b14a9e9439
Reviewed-on: https://go-review.googlesource.com/1886
Reviewed-by: Adam Langley <agl@golang.org>
diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go
index fa4ae2d..c19e88a 100644
--- a/src/math/big/int_test.go
+++ b/src/math/big/int_test.go
@@ -704,6 +704,13 @@
"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
+
+ // ECC primes: http://tools.ietf.org/html/draft-ladd-safecurves-02
+ "3618502788666131106986593281521497120414687020801267626233049500247285301239", // Curve1174: 2^251-9
+ "57896044618658097711785492504343953926634992332820282019728792003956564819949", // Curve25519: 2^255-19
+ "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599", // E-382: 2^382-105
+ "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367", // Curve41417: 2^414-17
+ "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", // E-521: 2^521-1
}
var composites = []string{
@@ -1249,6 +1256,136 @@
}
}
+// testModSqrt is a helper for TestModSqrt,
+// which checks that ModSqrt can compute a square-root of elt^2.
+func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
+ var sqChk, sqrtChk, sqrtsq Int
+ sq.Mul(elt, elt)
+ sq.Mod(sq, mod)
+ z := sqrt.ModSqrt(sq, mod)
+ if z != sqrt {
+ t.Errorf("ModSqrt returned wrong value %s", z)
+ }
+
+ // test ModSqrt arguments outside the range [0,mod)
+ sqChk.Add(sq, mod)
+ z = sqrtChk.ModSqrt(&sqChk, mod)
+ if z != &sqrtChk || z.Cmp(sqrt) != 0 {
+ t.Errorf("ModSqrt returned inconsistent value %s", z)
+ }
+ sqChk.Sub(sq, mod)
+ z = sqrtChk.ModSqrt(&sqChk, mod)
+ if z != &sqrtChk || z.Cmp(sqrt) != 0 {
+ t.Errorf("ModSqrt returned inconsistent value %s", z)
+ }
+
+ // make sure we actually got a square root
+ if sqrt.Cmp(elt) == 0 {
+ return true // we found the "desired" square root
+ }
+ sqrtsq.Mul(sqrt, sqrt) // make sure we found the "other" one
+ sqrtsq.Mod(&sqrtsq, mod)
+ return sq.Cmp(&sqrtsq) == 0
+}
+
+func TestModSqrt(t *testing.T) {
+ var elt, mod, modx4, sq, sqrt Int
+ r := rand.New(rand.NewSource(9))
+ for i, s := range primes[1:] { // skip 2, use only odd primes
+ mod.SetString(s, 10)
+ modx4.Lsh(&mod, 2)
+
+ // test a few random elements per prime
+ for x := 1; x < 5; x++ {
+ elt.Rand(r, &modx4)
+ elt.Sub(&elt, &mod) // test range [-mod, 3*mod)
+ if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
+ t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
+ }
+ }
+ }
+
+ // exhaustive test for small values
+ for n := 3; n < 100; n++ {
+ mod.SetInt64(int64(n))
+ if !mod.ProbablyPrime(10) {
+ continue
+ }
+ isSquare := make([]bool, n)
+
+ // test all the squares
+ for x := 1; x < n; x++ {
+ elt.SetInt64(int64(x))
+ if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
+ t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
+ }
+ isSquare[sq.Uint64()] = true
+ }
+
+ // test all non-squares
+ for x := 1; x < n; x++ {
+ sq.SetInt64(int64(x))
+ z := sqrt.ModSqrt(&sq, &mod)
+ if !isSquare[x] && z != nil {
+ t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
+ }
+ }
+ }
+}
+
+func TestJacobi(t *testing.T) {
+ testCases := []struct {
+ x, y int64
+ result int
+ }{
+ {0, 1, 1},
+ {0, -1, 1},
+ {1, 1, 1},
+ {1, -1, 1},
+ {0, 5, 0},
+ {1, 5, 1},
+ {2, 5, -1},
+ {-2, 5, -1},
+ {2, -5, -1},
+ {-2, -5, 1},
+ {3, 5, -1},
+ {5, 5, 0},
+ {-5, 5, 0},
+ {6, 5, 1},
+ {6, -5, 1},
+ {-6, 5, 1},
+ {-6, -5, -1},
+ }
+
+ var x, y Int
+
+ for i, test := range testCases {
+ x.SetInt64(test.x)
+ y.SetInt64(test.y)
+ expected := test.result
+ actual := Jacobi(&x, &y)
+ if actual != expected {
+ t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
+ }
+ }
+}
+
+func TestJacobiPanic(t *testing.T) {
+ const failureMsg = "test failure"
+ defer func() {
+ msg := recover()
+ if msg == nil || msg == failureMsg {
+ panic(msg)
+ }
+ t.Log(msg)
+ }()
+ x := NewInt(1)
+ y := NewInt(2)
+ // Jacobi should panic when the second argument is even.
+ Jacobi(x, y)
+ panic(failureMsg)
+}
+
var encodingTests = []string{
"-539345864568634858364538753846587364875430589374589",
"-678645873",
