diff options
Diffstat (limited to 'src/math')
| -rw-r--r-- | src/math/big/int.go | 25 | ||||
| -rw-r--r-- | src/math/big/int_test.go | 50 | ||||
| -rw-r--r-- | src/math/big/rat.go | 7 | ||||
| -rw-r--r-- | src/math/big/rat_test.go | 1 | ||||
| -rw-r--r-- | src/math/sincos_amd64.s | 13 |
5 files changed, 64 insertions, 32 deletions
diff --git a/src/math/big/int.go b/src/math/big/int.go index e70d0489b..d22e39e7c 100644 --- a/src/math/big/int.go +++ b/src/math/big/int.go @@ -605,6 +605,12 @@ func (z *Int) Exp(x, y, m *Int) *Int { z.abs = z.abs.expNN(x.abs, yWords, mWords) z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign + if z.neg && len(mWords) > 0 { + // make modulus result positive + z.abs = z.abs.sub(mWords, z.abs) // z == x**y mod |m| && 0 <= z < |m| + z.neg = false + } + return z } @@ -746,15 +752,16 @@ func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int { return z } -// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where -// p is a prime) and returns z. -func (z *Int) ModInverse(g, p *Int) *Int { +// ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ +// and returns z. If g and n are not relatively prime, the result is undefined. +func (z *Int) ModInverse(g, n *Int) *Int { var d Int - d.GCD(z, nil, g, p) - // x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking - // that modulo p results in g*x = 1, therefore x is the inverse element. + d.GCD(z, nil, g, n) + // x and y are such that g*x + n*y = d. Since g and n are + // relatively prime, d = 1. Taking that modulo n results in + // g*x = 1, therefore x is the inverse element. if z.neg { - z.Add(z, p) + z.Add(z, n) } return z } @@ -1010,12 +1017,12 @@ func (z *Int) UnmarshalJSON(text []byte) error { return nil } -// MarshalText implements the encoding.TextMarshaler interface +// MarshalText implements the encoding.TextMarshaler interface. func (z *Int) MarshalText() (text []byte, err error) { return []byte(z.String()), nil } -// UnmarshalText implements the encoding.TextUnmarshaler interface +// UnmarshalText implements the encoding.TextUnmarshaler interface. func (z *Int) UnmarshalText(text []byte) error { if _, ok := z.SetString(string(text), 0); !ok { return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Int", text) diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go index 299dc72fb..6070cf325 100644 --- a/src/math/big/int_test.go +++ b/src/math/big/int_test.go @@ -787,6 +787,7 @@ var expTests = []struct { {"-5", "0", "", "1"}, {"5", "1", "", "5"}, {"-5", "1", "", "-5"}, + {"-5", "1", "7", "2"}, {"-2", "3", "2", "0"}, {"5", "2", "", "25"}, {"1", "65537", "2", "1"}, @@ -802,6 +803,13 @@ var expTests = []struct { "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464", "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291", }, + // test case for issue 8822 + { + "-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2", + "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD", + "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", + "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442", + }, } func TestExp(t *testing.T) { @@ -833,12 +841,12 @@ func TestExp(t *testing.T) { } if m == nil { - // the result should be the same as for m == 0; - // specifically, there should be no div-zero panic + // The result should be the same as for m == 0; + // specifically, there should be no div-zero panic. m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0 z2 := new(Int).Exp(x, y, m) if z2.Cmp(z1) != 0 { - t.Errorf("#%d: got %s want %s", i, z1, z2) + t.Errorf("#%d: got %s want %s", i, z2, z1) } } } @@ -1440,24 +1448,40 @@ func TestNot(t *testing.T) { var modInverseTests = []struct { element string - prime string + modulus string }{ - {"1", "7"}, - {"1", "13"}, + {"1234567", "458948883992"}, {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"}, } func TestModInverse(t *testing.T) { - var element, prime Int + var element, modulus, gcd, inverse Int one := NewInt(1) for i, test := range modInverseTests { (&element).SetString(test.element, 10) - (&prime).SetString(test.prime, 10) - inverse := new(Int).ModInverse(&element, &prime) - inverse.Mul(inverse, &element) - inverse.Mod(inverse, &prime) - if inverse.Cmp(one) != 0 { - t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse) + (&modulus).SetString(test.modulus, 10) + (&inverse).ModInverse(&element, &modulus) + (&inverse).Mul(&inverse, &element) + (&inverse).Mod(&inverse, &modulus) + if (&inverse).Cmp(one) != 0 { + t.Errorf("#%d: failed (e·e^(-1)=%s)", i, &inverse) + } + } + // exhaustive test for small values + for n := 2; n < 100; n++ { + (&modulus).SetInt64(int64(n)) + for x := 1; x < n; x++ { + (&element).SetInt64(int64(x)) + (&gcd).GCD(nil, nil, &element, &modulus) + if (&gcd).Cmp(one) != 0 { + continue + } + (&inverse).ModInverse(&element, &modulus) + (&inverse).Mul(&inverse, &element) + (&inverse).Mod(&inverse, &modulus) + if (&inverse).Cmp(one) != 0 { + t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse) + } } } } diff --git a/src/math/big/rat.go b/src/math/big/rat.go index e6ab0bb48..c5339fe44 100644 --- a/src/math/big/rat.go +++ b/src/math/big/rat.go @@ -552,6 +552,9 @@ func (z *Rat) SetString(s string) (*Rat, bool) { if z.b.abs, _, err = z.b.abs.scan(strings.NewReader(s), 10); err != nil { return nil, false } + if len(z.b.abs) == 0 { + return nil, false + } return z.norm(), true } @@ -699,12 +702,12 @@ func (z *Rat) GobDecode(buf []byte) error { return nil } -// MarshalText implements the encoding.TextMarshaler interface +// MarshalText implements the encoding.TextMarshaler interface. func (r *Rat) MarshalText() (text []byte, err error) { return []byte(r.RatString()), nil } -// UnmarshalText implements the encoding.TextUnmarshaler interface +// UnmarshalText implements the encoding.TextUnmarshaler interface. func (r *Rat) UnmarshalText(text []byte) error { if _, ok := r.SetString(string(text)); !ok { return fmt.Errorf("math/big: cannot unmarshal %q into a *big.Rat", text) diff --git a/src/math/big/rat_test.go b/src/math/big/rat_test.go index 598eac8cc..5dbbb3510 100644 --- a/src/math/big/rat_test.go +++ b/src/math/big/rat_test.go @@ -89,6 +89,7 @@ var setStringTests = []struct { {"53/70893980658822810696", "53/70893980658822810696", true}, {"106/141787961317645621392", "53/70893980658822810696", true}, {"204211327800791583.81095", "4084226556015831676219/20000", true}, + {in: "1/0", ok: false}, } func TestRatSetString(t *testing.T) { diff --git a/src/math/sincos_amd64.s b/src/math/sincos_amd64.s index dae636b24..59bf55f58 100644 --- a/src/math/sincos_amd64.s +++ b/src/math/sincos_amd64.s @@ -15,9 +15,7 @@ // The README file says, "The software is in public domain. // You can use the software without any obligation." // -// This code is a simplified version of the original. The CMPSD -// instruction, not generated by the compiler, eliminates jumps in the -// body of the calculation. +// This code is a simplified version of the original. #define PosOne 0x3FF0000000000000 #define PosInf 0x7FF0000000000000 @@ -96,11 +94,10 @@ TEXT ·Sincos(SB),NOSPLIT,$0 // if ((q + 1) & 2) != 0 { sin, cos = cos, sin } MOVQ $1, DX ADDQ BX, DX - MOVQ $2, AX - ANDQ AX, DX - MOVQ DX, X0 - MOVSD $0.0, X3 - CMPSD X0, X3, 0 // cmpeq; x1= x, x2= z, x3 = y, x7= d, bx= q + ANDQ $2, DX + SHRQ $1, DX + SUBQ $1, DX + MOVQ DX, X3 // sin = (y & z) | (^y & x) MOVAPD X2, X0 ANDPD X3, X0 // x0= sin |