From a73abca37bcdc4016ccf98754c68f21e7abc8c0e Mon Sep 17 00:00:00 2001 From: Brian Kessler Date: Wed, 13 Feb 2019 13:18:17 -0700 Subject: [PATCH] math/big: handle alias of cofactor inputs in GCD If the variables passed in to the cofactor arguments of GCD (x, y) aliased the input arguments (a, b), the previous implementation would result in incorrect results for y. This change reorganizes the calculation so that the only case that need to be handled is when y aliases b, which can be handled with a simple check. Tests were added for all of the alias cases for input arguments and and and irrelevant test case for a previous binary GCD calculation was dropped. Fixes #30217 Change-Id: Ibe6137f09b3e1ae3c29e3c97aba85b67f33dc169 Reviewed-on: https://go-review.googlesource.com/c/162517 Run-TryBot: Robert Griesemer Reviewed-by: Robert Griesemer TryBot-Result: Gobot Gobot --- src/math/big/int.go | 18 ++++++++++++------ src/math/big/int_test.go | 41 +++++++++++++++++++++++++++++++++++++--- 2 files changed, 50 insertions(+), 9 deletions(-) diff --git a/src/math/big/int.go b/src/math/big/int.go index dab9a5cc0f..8c1a54a9c6 100644 --- a/src/math/big/int.go +++ b/src/math/big/int.go @@ -700,15 +700,21 @@ func (z *Int) lehmerGCD(x, y, a, b *Int) *Int { } } - if x != nil { - *x = *Ua - } - if y != nil { + // avoid aliasing b needed in the division below + if y == b { + B.Set(b) + } else { + B = b + } // y = (z - a*x)/b - y.Mul(a, Ua) + y.Mul(a, Ua) // y can safely alias a y.Sub(A, y) - y.Div(y, b) + y.Div(y, B) + } + + if x != nil { + *x = *Ua } *z = *A diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index 7ef2b3907f..48d08d0e7e 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -760,9 +760,6 @@ var gcdTests = []struct { {"935", "-3", "8", "64515", "24310"}, {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"}, {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"}, - - // test early exit (after one Euclidean iteration) in binaryGCD - {"1", "", "", "1", "98920366548084643601728869055592650835572950932266967461790948584315647051443"}, } func testGcd(t *testing.T, d, x, y, a, b *Int) { @@ -793,6 +790,12 @@ func testGcd(t *testing.T, d, x, y, a, b *Int) { if a2.Cmp(d) != 0 { t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d) } + if x != nil && X.Cmp(x) != 0 { + t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x) + } + if y != nil && Y.Cmp(y) != 0 { + t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y) + } a2 = new(Int).Set(a) b2 = new(Int).Set(b) @@ -800,6 +803,38 @@ func testGcd(t *testing.T, d, x, y, a, b *Int) { if b2.Cmp(d) != 0 { t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d) } + if x != nil && X.Cmp(x) != 0 { + t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x) + } + if y != nil && Y.Cmp(y) != 0 { + t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y) + } + + a2 = new(Int).Set(a) + b2 = new(Int).Set(b) + D = new(Int).GCD(a2, b2, a2, b2) // x = a, y = b + if D.Cmp(d) != 0 { + t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d) + } + if x != nil && a2.Cmp(x) != 0 { + t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x) + } + if y != nil && b2.Cmp(y) != 0 { + t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y) + } + + a2 = new(Int).Set(a) + b2 = new(Int).Set(b) + D = new(Int).GCD(b2, a2, a2, b2) // x = b, y = a + if D.Cmp(d) != 0 { + t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d) + } + if x != nil && b2.Cmp(x) != 0 { + t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x) + } + if y != nil && a2.Cmp(y) != 0 { + t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y) + } } func TestGcd(t *testing.T) { -- 2.50.0