Source file
src/math/big/int_test.go
1
2
3
4
5 package big
6
7 import (
8 "bytes"
9 "encoding/hex"
10 "fmt"
11 "internal/testenv"
12 "math"
13 "math/rand"
14 "strconv"
15 "strings"
16 "testing"
17 "testing/quick"
18 )
19
20 func isNormalized(x *Int) bool {
21 if len(x.abs) == 0 {
22 return !x.neg
23 }
24
25 return x.abs[len(x.abs)-1] != 0
26 }
27
28 type funZZ func(z, x, y *Int) *Int
29 type argZZ struct {
30 z, x, y *Int
31 }
32
33 var sumZZ = []argZZ{
34 {NewInt(0), NewInt(0), NewInt(0)},
35 {NewInt(1), NewInt(1), NewInt(0)},
36 {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
37 {NewInt(-1), NewInt(-1), NewInt(0)},
38 {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
39 {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
40 }
41
42 var prodZZ = []argZZ{
43 {NewInt(0), NewInt(0), NewInt(0)},
44 {NewInt(0), NewInt(1), NewInt(0)},
45 {NewInt(1), NewInt(1), NewInt(1)},
46 {NewInt(-991 * 991), NewInt(991), NewInt(-991)},
47
48 }
49
50 func TestSignZ(t *testing.T) {
51 var zero Int
52 for _, a := range sumZZ {
53 s := a.z.Sign()
54 e := a.z.Cmp(&zero)
55 if s != e {
56 t.Errorf("got %d; want %d for z = %v", s, e, a.z)
57 }
58 }
59 }
60
61 func TestSetZ(t *testing.T) {
62 for _, a := range sumZZ {
63 var z Int
64 z.Set(a.z)
65 if !isNormalized(&z) {
66 t.Errorf("%v is not normalized", z)
67 }
68 if (&z).Cmp(a.z) != 0 {
69 t.Errorf("got z = %v; want %v", z, a.z)
70 }
71 }
72 }
73
74 func TestAbsZ(t *testing.T) {
75 var zero Int
76 for _, a := range sumZZ {
77 var z Int
78 z.Abs(a.z)
79 var e Int
80 e.Set(a.z)
81 if e.Cmp(&zero) < 0 {
82 e.Sub(&zero, &e)
83 }
84 if z.Cmp(&e) != 0 {
85 t.Errorf("got z = %v; want %v", z, e)
86 }
87 }
88 }
89
90 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
91 var z Int
92 f(&z, a.x, a.y)
93 if !isNormalized(&z) {
94 t.Errorf("%s%v is not normalized", msg, z)
95 }
96 if (&z).Cmp(a.z) != 0 {
97 t.Errorf("%v %s %v\n\tgot z = %v; want %v", a.x, msg, a.y, &z, a.z)
98 }
99 }
100
101 func TestSumZZ(t *testing.T) {
102 AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
103 SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
104 for _, a := range sumZZ {
105 arg := a
106 testFunZZ(t, "AddZZ", AddZZ, arg)
107
108 arg = argZZ{a.z, a.y, a.x}
109 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
110
111 arg = argZZ{a.x, a.z, a.y}
112 testFunZZ(t, "SubZZ", SubZZ, arg)
113
114 arg = argZZ{a.y, a.z, a.x}
115 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
116 }
117 }
118
119 func TestProdZZ(t *testing.T) {
120 MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
121 for _, a := range prodZZ {
122 arg := a
123 testFunZZ(t, "MulZZ", MulZZ, arg)
124
125 arg = argZZ{a.z, a.y, a.x}
126 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
127 }
128 }
129
130
131
132
133 func mulBytes(x, y []byte) []byte {
134 z := make([]byte, len(x)+len(y))
135
136
137 k0 := len(z) - 1
138 for j := len(y) - 1; j >= 0; j-- {
139 d := int(y[j])
140 if d != 0 {
141 k := k0
142 carry := 0
143 for i := len(x) - 1; i >= 0; i-- {
144 t := int(z[k]) + int(x[i])*d + carry
145 z[k], carry = byte(t), t>>8
146 k--
147 }
148 z[k] = byte(carry)
149 }
150 k0--
151 }
152
153
154 i := 0
155 for i < len(z) && z[i] == 0 {
156 i++
157 }
158
159 return z[i:]
160 }
161
162 func checkMul(a, b []byte) bool {
163 var x, y, z1 Int
164 x.SetBytes(a)
165 y.SetBytes(b)
166 z1.Mul(&x, &y)
167
168 var z2 Int
169 z2.SetBytes(mulBytes(a, b))
170
171 return z1.Cmp(&z2) == 0
172 }
173
174 func TestMul(t *testing.T) {
175 if err := quick.Check(checkMul, nil); err != nil {
176 t.Error(err)
177 }
178 }
179
180 var mulRangesZ = []struct {
181 a, b int64
182 prod string
183 }{
184
185 {-1, 1, "0"},
186 {-2, -1, "2"},
187 {-3, -2, "6"},
188 {-3, -1, "-6"},
189 {1, 3, "6"},
190 {-10, -10, "-10"},
191 {0, -1, "1"},
192 {-1, -100, "1"},
193 {-1, 1, "0"},
194 {-1e9, 0, "0"},
195 {-1e9, 1e9, "0"},
196 {-10, -1, "3628800"},
197 {-20, -2, "-2432902008176640000"},
198 {-99, -1,
199 "-933262154439441526816992388562667004907159682643816214685929" +
200 "638952175999932299156089414639761565182862536979208272237582" +
201 "511852109168640000000000000000000000",
202 },
203
204
205 {math.MaxInt64 - 0, math.MaxInt64, "9223372036854775807"},
206 {math.MaxInt64 - 1, math.MaxInt64, "85070591730234615838173535747377725442"},
207 {math.MaxInt64 - 2, math.MaxInt64, "784637716923335094969050127519550606919189611815754530810"},
208 {math.MaxInt64 - 3, math.MaxInt64, "7237005577332262206126809393809643289012107973151163787181513908099760521240"},
209 }
210
211 func TestMulRangeZ(t *testing.T) {
212 var tmp Int
213
214 for i, r := range mulRangesN {
215
216 if int64(r.a) < 0 || int64(r.b) < 0 {
217 continue
218 }
219 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
220 if prod != r.prod {
221 t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
222 }
223 }
224
225 for i, r := range mulRangesZ {
226 prod := tmp.MulRange(r.a, r.b).String()
227 if prod != r.prod {
228 t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
229 }
230 }
231 }
232
233 func TestBinomial(t *testing.T) {
234 var z Int
235 for _, test := range []struct {
236 n, k int64
237 want string
238 }{
239 {0, 0, "1"},
240 {0, 1, "0"},
241 {1, 0, "1"},
242 {1, 1, "1"},
243 {1, 10, "0"},
244 {4, 0, "1"},
245 {4, 1, "4"},
246 {4, 2, "6"},
247 {4, 3, "4"},
248 {4, 4, "1"},
249 {10, 1, "10"},
250 {10, 9, "10"},
251 {10, 5, "252"},
252 {11, 5, "462"},
253 {11, 6, "462"},
254 {100, 10, "17310309456440"},
255 {100, 90, "17310309456440"},
256 {1000, 10, "263409560461970212832400"},
257 {1000, 990, "263409560461970212832400"},
258 {5, -1, "0"},
259 } {
260 if got := z.Binomial(test.n, test.k).String(); got != test.want {
261 t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
262 }
263 }
264 }
265
266 func BenchmarkBinomial(b *testing.B) {
267 var z Int
268 for i := 0; i < b.N; i++ {
269 z.Binomial(1000, 990)
270 }
271 }
272
273
274 var divisionSignsTests = []struct {
275 x, y int64
276 q, r int64
277 d, m int64
278 }{
279 {5, 3, 1, 2, 1, 2},
280 {-5, 3, -1, -2, -2, 1},
281 {5, -3, -1, 2, -1, 2},
282 {-5, -3, 1, -2, 2, 1},
283 {1, 2, 0, 1, 0, 1},
284 {8, 4, 2, 0, 2, 0},
285 }
286
287 func TestDivisionSigns(t *testing.T) {
288 for i, test := range divisionSignsTests {
289 x := NewInt(test.x)
290 y := NewInt(test.y)
291 q := NewInt(test.q)
292 r := NewInt(test.r)
293 d := NewInt(test.d)
294 m := NewInt(test.m)
295
296 q1 := new(Int).Quo(x, y)
297 r1 := new(Int).Rem(x, y)
298 if !isNormalized(q1) {
299 t.Errorf("#%d Quo: %v is not normalized", i, *q1)
300 }
301 if !isNormalized(r1) {
302 t.Errorf("#%d Rem: %v is not normalized", i, *r1)
303 }
304 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
305 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
306 }
307
308 q2, r2 := new(Int).QuoRem(x, y, new(Int))
309 if !isNormalized(q2) {
310 t.Errorf("#%d Quo: %v is not normalized", i, *q2)
311 }
312 if !isNormalized(r2) {
313 t.Errorf("#%d Rem: %v is not normalized", i, *r2)
314 }
315 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
316 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
317 }
318
319 d1 := new(Int).Div(x, y)
320 m1 := new(Int).Mod(x, y)
321 if !isNormalized(d1) {
322 t.Errorf("#%d Div: %v is not normalized", i, *d1)
323 }
324 if !isNormalized(m1) {
325 t.Errorf("#%d Mod: %v is not normalized", i, *m1)
326 }
327 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
328 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
329 }
330
331 d2, m2 := new(Int).DivMod(x, y, new(Int))
332 if !isNormalized(d2) {
333 t.Errorf("#%d Div: %v is not normalized", i, *d2)
334 }
335 if !isNormalized(m2) {
336 t.Errorf("#%d Mod: %v is not normalized", i, *m2)
337 }
338 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
339 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
340 }
341 }
342 }
343
344 func norm(x nat) nat {
345 i := len(x)
346 for i > 0 && x[i-1] == 0 {
347 i--
348 }
349 return x[:i]
350 }
351
352 func TestBits(t *testing.T) {
353 for _, test := range []nat{
354 nil,
355 {0},
356 {1},
357 {0, 1, 2, 3, 4},
358 {4, 3, 2, 1, 0},
359 {4, 3, 2, 1, 0, 0, 0, 0},
360 } {
361 var z Int
362 z.neg = true
363 got := z.SetBits(test)
364 want := norm(test)
365 if got.abs.cmp(want) != 0 {
366 t.Errorf("SetBits(%v) = %v; want %v", test, got.abs, want)
367 }
368
369 if got.neg {
370 t.Errorf("SetBits(%v): got negative result", test)
371 }
372
373 bits := nat(z.Bits())
374 if bits.cmp(want) != 0 {
375 t.Errorf("%v.Bits() = %v; want %v", z.abs, bits, want)
376 }
377 }
378 }
379
380 func checkSetBytes(b []byte) bool {
381 hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
382 hex2 := hex.EncodeToString(b)
383
384 for len(hex1) < len(hex2) {
385 hex1 = "0" + hex1
386 }
387
388 for len(hex1) > len(hex2) {
389 hex2 = "0" + hex2
390 }
391
392 return hex1 == hex2
393 }
394
395 func TestSetBytes(t *testing.T) {
396 if err := quick.Check(checkSetBytes, nil); err != nil {
397 t.Error(err)
398 }
399 }
400
401 func checkBytes(b []byte) bool {
402
403
404 for len(b) > 0 && b[0] == 0 {
405 b = b[1:]
406 }
407 b2 := new(Int).SetBytes(b).Bytes()
408 return bytes.Equal(b, b2)
409 }
410
411 func TestBytes(t *testing.T) {
412 if err := quick.Check(checkBytes, nil); err != nil {
413 t.Error(err)
414 }
415 }
416
417 func checkQuo(x, y []byte) bool {
418 u := new(Int).SetBytes(x)
419 v := new(Int).SetBytes(y)
420
421 if len(v.abs) == 0 {
422 return true
423 }
424
425 r := new(Int)
426 q, r := new(Int).QuoRem(u, v, r)
427
428 if r.Cmp(v) >= 0 {
429 return false
430 }
431
432 uprime := new(Int).Set(q)
433 uprime.Mul(uprime, v)
434 uprime.Add(uprime, r)
435
436 return uprime.Cmp(u) == 0
437 }
438
439 var quoTests = []struct {
440 x, y string
441 q, r string
442 }{
443 {
444 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
445 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
446 "50911",
447 "1",
448 },
449 {
450 "11510768301994997771168",
451 "1328165573307167369775",
452 "8",
453 "885443715537658812968",
454 },
455 }
456
457 func TestQuo(t *testing.T) {
458 if err := quick.Check(checkQuo, nil); err != nil {
459 t.Error(err)
460 }
461
462 for i, test := range quoTests {
463 x, _ := new(Int).SetString(test.x, 10)
464 y, _ := new(Int).SetString(test.y, 10)
465 expectedQ, _ := new(Int).SetString(test.q, 10)
466 expectedR, _ := new(Int).SetString(test.r, 10)
467
468 r := new(Int)
469 q, r := new(Int).QuoRem(x, y, r)
470
471 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
472 t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
473 }
474 }
475 }
476
477 func TestQuoStepD6(t *testing.T) {
478
479
480
481 u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
482 v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
483
484 r := new(Int)
485 q, r := new(Int).QuoRem(u, v, r)
486 const expectedQ64 = "18446744073709551613"
487 const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
488 const expectedQ32 = "4294967293"
489 const expectedR32 = "39614081266355540837921718287"
490 if q.String() != expectedQ64 && q.String() != expectedQ32 ||
491 r.String() != expectedR64 && r.String() != expectedR32 {
492 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
493 }
494 }
495
496 func BenchmarkQuoRem(b *testing.B) {
497 x, _ := new(Int).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
498 y, _ := new(Int).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
499 q := new(Int)
500 r := new(Int)
501
502 b.ResetTimer()
503 for i := 0; i < b.N; i++ {
504 q.QuoRem(y, x, r)
505 }
506 }
507
508 func TestIntDivide(t *testing.T) {
509 x := new(Int)
510 y := new(Int)
511 q := new(Int)
512 r := new(Int)
513 f := new(Int)
514 qGot := new(Int)
515 rGot := new(Int)
516
517 check := func(i, j, q_ int64, mode RoundingMode, modeName string) {
518 x.SetInt64(i)
519 y.SetInt64(j)
520 q.SetInt64(q_)
521 r.SetInt64(i - j*q_)
522
523
524
525 x.Mul(x, f)
526 y.Mul(y, f)
527 r.Mul(r, f)
528
529 qGot, rGot = qGot.Divide(x, y, rGot, mode)
530 if qGot.Cmp(q) != 0 || rGot.Cmp(r) != 0 {
531 t.Errorf("%v(%v/%v): got q = %v, r = %v; want q = %v, r = %v", modeName, x, y, qGot, rGot, q, r)
532 }
533
534
535 qGot, _ = qGot.Divide(x, y, nil, mode)
536 if qGot.Cmp(q) != 0 {
537 t.Errorf("%v(%v/%v): got q = %v; want q = %v", modeName, x, y, qGot, q)
538 }
539
540
541 _, rGot = (*Int)(nil).Divide(x, y, rGot, mode)
542 if rGot.Cmp(r) != 0 {
543 t.Errorf("%v(%v/%v): got r = %v; want r = %v", modeName, x, y, rGot, r)
544 }
545
546
547 (*Int)(nil).Divide(x, y, nil, mode)
548 }
549
550
551 for _, s := range []string{
552 "1",
553 "1234",
554 "99991",
555 "1234567890",
556 "12345678901234567890",
557 } {
558 f.SetString(s, 10)
559 const n int64 = 10
560 for i := -n; i <= n; i++ {
561 for j := -n; j <= n; j++ {
562 if j == 0 {
563 continue
564 }
565 z := float64(i) / float64(j)
566 check(i, j, i/j, Trunc, "trunc")
567 check(i, j, int64(math.Trunc(z)), Trunc, "trunc")
568 check(i, j, int64(math.Floor(z)), Floor, "floor")
569 check(i, j, int64(math.Ceil(z)), Ceil, "ceil")
570 check(i, j, int64(math.RoundToEven(z)), Round, "round")
571 }
572 }
573 }
574 }
575
576 var bitLenTests = []struct {
577 in string
578 out int
579 }{
580 {"-1", 1},
581 {"0", 0},
582 {"1", 1},
583 {"2", 2},
584 {"4", 3},
585 {"0xabc", 12},
586 {"0x8000", 16},
587 {"0x80000000", 32},
588 {"0x800000000000", 48},
589 {"0x8000000000000000", 64},
590 {"0x80000000000000000000", 80},
591 {"-0x4000000000000000000000", 87},
592 }
593
594 func TestBitLen(t *testing.T) {
595 for i, test := range bitLenTests {
596 x, ok := new(Int).SetString(test.in, 0)
597 if !ok {
598 t.Errorf("#%d test input invalid: %s", i, test.in)
599 continue
600 }
601
602 if n := x.BitLen(); n != test.out {
603 t.Errorf("#%d got %d want %d", i, n, test.out)
604 }
605 }
606 }
607
608 var expTests = []struct {
609 x, y, m string
610 out string
611 }{
612
613 {"0", "0", "", "1"},
614 {"1", "0", "", "1"},
615 {"-10", "0", "", "1"},
616 {"1234", "-1", "", "1"},
617 {"1234", "-1", "0", "1"},
618 {"17", "-100", "1234", "865"},
619 {"2", "-100", "1234", ""},
620
621
622 {"0", "0", "1", "0"},
623 {"1", "0", "1", "0"},
624 {"-10", "0", "1", "0"},
625 {"1234", "-1", "1", "0"},
626
627
628 {"5", "1", "3", "2"},
629 {"5", "-7", "", "1"},
630 {"-5", "-7", "", "1"},
631 {"5", "0", "", "1"},
632 {"-5", "0", "", "1"},
633 {"5", "1", "", "5"},
634 {"-5", "1", "", "-5"},
635 {"-5", "1", "7", "2"},
636 {"-2", "3", "2", "0"},
637 {"5", "2", "", "25"},
638 {"1", "65537", "2", "1"},
639 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
640 {"0x8000000000000000", "2", "6719", "4944"},
641 {"0x8000000000000000", "3", "6719", "5447"},
642 {"0x8000000000000000", "1000", "6719", "1603"},
643 {"0x8000000000000000", "1000000", "6719", "3199"},
644 {"0x8000000000000000", "-1000000", "6719", "3663"},
645
646 {"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
647
648 {
649 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
650 "298472983472983471903246121093472394872319615612417471234712061",
651 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
652 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
653 },
654
655 {
656 "11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
657 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
658 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
659 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
660 },
661 {
662 "-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
663 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
664 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
665 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
666 },
667
668
669 {"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
670 {"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
671 {"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
672 {"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
673
674 {
675 "2",
676 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
677 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
678 "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
679 },
680 {
681 "2",
682 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
683 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72",
684 "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
685 },
686 }
687
688 func TestExp(t *testing.T) {
689 for i, test := range expTests {
690 x, ok1 := new(Int).SetString(test.x, 0)
691 y, ok2 := new(Int).SetString(test.y, 0)
692
693 var ok3, ok4 bool
694 var out, m *Int
695
696 if len(test.out) == 0 {
697 out, ok3 = nil, true
698 } else {
699 out, ok3 = new(Int).SetString(test.out, 0)
700 }
701
702 if len(test.m) == 0 {
703 m, ok4 = nil, true
704 } else {
705 m, ok4 = new(Int).SetString(test.m, 0)
706 }
707
708 if !ok1 || !ok2 || !ok3 || !ok4 {
709 t.Errorf("#%d: error in input", i)
710 continue
711 }
712
713 z1 := new(Int).Exp(x, y, m)
714 if z1 != nil && !isNormalized(z1) {
715 t.Errorf("#%d: %v is not normalized", i, *z1)
716 }
717 if !(z1 == nil && out == nil || z1.Cmp(out) == 0) {
718 t.Errorf("#%d: got %x want %x", i, z1, out)
719 }
720
721 if m == nil {
722
723
724 m = &Int{abs: nat{}}
725 z2 := new(Int).Exp(x, y, m)
726 if z2.Cmp(z1) != 0 {
727 t.Errorf("#%d: got %x want %x", i, z2, z1)
728 }
729 }
730 }
731 }
732
733 func BenchmarkExp(b *testing.B) {
734 x, _ := new(Int).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
735 y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
736 n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
737 out := new(Int)
738 for i := 0; i < b.N; i++ {
739 out.Exp(x, y, n)
740 }
741 }
742
743 func BenchmarkExpMont(b *testing.B) {
744 x, _ := new(Int).SetString("297778224889315382157302278696111964193", 0)
745 y, _ := new(Int).SetString("2548977943381019743024248146923164919440527843026415174732254534318292492375775985739511369575861449426580651447974311336267954477239437734832604782764979371984246675241012538135715981292390886872929238062252506842498360562303324154310849745753254532852868768268023732398278338025070694508489163836616810661033068070127919590264734220833816416141878688318329193389865030063416339367925710474801991305827284114894677717927892032165200876093838921477120036402410731159852999623461591709308405270748511350289172153076023215", 0)
746 var mods = []struct {
747 name string
748 val string
749 }{
750 {"Odd", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF"},
751 {"Even1", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FE"},
752 {"Even2", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FC"},
753 {"Even3", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F8"},
754 {"Even4", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281F0"},
755 {"Even8", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B21828100"},
756 {"Even32", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B00000000"},
757 {"Even64", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828282828200FF0000000000000000"},
758 {"Even96", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF82828283000000000000000000000000"},
759 {"Even128", "0x82828282828200FFFF28FF2B218281FF82828282828200FFFF28FF2B218281FF00000000000000000000000000000000"},
760 {"Even255", "0x82828282828200FFFF28FF2B218281FF8000000000000000000000000000000000000000000000000000000000000000"},
761 {"SmallEven1", "0x7E"},
762 {"SmallEven2", "0x7C"},
763 {"SmallEven3", "0x78"},
764 {"SmallEven4", "0x70"},
765 }
766 for _, mod := range mods {
767 n, _ := new(Int).SetString(mod.val, 0)
768 out := new(Int)
769 b.Run(mod.name, func(b *testing.B) {
770 b.ReportAllocs()
771 for i := 0; i < b.N; i++ {
772 out.Exp(x, y, n)
773 }
774 })
775 }
776 }
777
778 func BenchmarkExp2(b *testing.B) {
779 x, _ := new(Int).SetString("2", 0)
780 y, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
781 n, _ := new(Int).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
782 out := new(Int)
783 for i := 0; i < b.N; i++ {
784 out.Exp(x, y, n)
785 }
786 }
787
788 func checkGcd(aBytes, bBytes []byte) bool {
789 x := new(Int)
790 y := new(Int)
791 a := new(Int).SetBytes(aBytes)
792 b := new(Int).SetBytes(bBytes)
793
794 d := new(Int).GCD(x, y, a, b)
795 x.Mul(x, a)
796 y.Mul(y, b)
797 x.Add(x, y)
798
799 return x.Cmp(d) == 0
800 }
801
802
803
804
805 func euclidExtGCD(a, b *Int) (g, x, y *Int) {
806 A := new(Int).Set(a)
807 B := new(Int).Set(b)
808
809
810
811 Ua := new(Int).SetInt64(1)
812 Va := new(Int)
813
814 Ub := new(Int)
815 Vb := new(Int).SetInt64(1)
816
817 q := new(Int)
818 temp := new(Int)
819
820 r := new(Int)
821 for len(B.abs) > 0 {
822 q, r = q.QuoRem(A, B, r)
823
824 A, B, r = B, r, A
825
826
827 temp.Set(Ub)
828 Ub.Mul(Ub, q)
829 Ub.Sub(Ua, Ub)
830 Ua.Set(temp)
831
832
833 temp.Set(Vb)
834 Vb.Mul(Vb, q)
835 Vb.Sub(Va, Vb)
836 Va.Set(temp)
837 }
838 return A, Ua, Va
839 }
840
841 func checkLehmerGcd(aBytes, bBytes []byte) bool {
842 a := new(Int).SetBytes(aBytes)
843 b := new(Int).SetBytes(bBytes)
844
845 if a.Sign() <= 0 || b.Sign() <= 0 {
846 return true
847 }
848
849 d := new(Int).lehmerGCD(nil, nil, a, b)
850 d0, _, _ := euclidExtGCD(a, b)
851
852 return d.Cmp(d0) == 0
853 }
854
855 func checkLehmerExtGcd(aBytes, bBytes []byte) bool {
856 a := new(Int).SetBytes(aBytes)
857 b := new(Int).SetBytes(bBytes)
858 x := new(Int)
859 y := new(Int)
860
861 if a.Sign() <= 0 || b.Sign() <= 0 {
862 return true
863 }
864
865 d := new(Int).lehmerGCD(x, y, a, b)
866 d0, x0, y0 := euclidExtGCD(a, b)
867
868 return d.Cmp(d0) == 0 && x.Cmp(x0) == 0 && y.Cmp(y0) == 0
869 }
870
871 var gcdTests = []struct {
872 d, x, y, a, b string
873 }{
874
875 {"0", "0", "0", "0", "0"},
876 {"7", "0", "1", "0", "7"},
877 {"7", "0", "-1", "0", "-7"},
878 {"11", "1", "0", "11", "0"},
879 {"7", "-1", "-2", "-77", "35"},
880 {"935", "-3", "8", "64515", "24310"},
881 {"935", "-3", "-8", "64515", "-24310"},
882 {"935", "3", "-8", "-64515", "-24310"},
883
884 {"1", "-9", "47", "120", "23"},
885 {"7", "1", "-2", "77", "35"},
886 {"935", "-3", "8", "64515", "24310"},
887 {"935000000000000000", "-3", "8", "64515000000000000000", "24310000000000000000"},
888 {"1", "-221", "22059940471369027483332068679400581064239780177629666810348940098015901108344", "98920366548084643601728869055592650835572950932266967461790948584315647051443", "991"},
889 }
890
891 func testGcd(t *testing.T, d, x, y, a, b *Int) {
892 var X *Int
893 if x != nil {
894 X = new(Int)
895 }
896 var Y *Int
897 if y != nil {
898 Y = new(Int)
899 }
900
901 D := new(Int).GCD(X, Y, a, b)
902 if D.Cmp(d) != 0 {
903 t.Errorf("GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
904 }
905 if x != nil && X.Cmp(x) != 0 {
906 t.Errorf("GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
907 }
908 if y != nil && Y.Cmp(y) != 0 {
909 t.Errorf("GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
910 }
911
912
913 a2 := new(Int).Set(a)
914 b2 := new(Int).Set(b)
915 a2.GCD(X, Y, a2, b2)
916 if a2.Cmp(d) != 0 {
917 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, a2, d)
918 }
919 if x != nil && X.Cmp(x) != 0 {
920 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
921 }
922 if y != nil && Y.Cmp(y) != 0 {
923 t.Errorf("aliased z = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
924 }
925
926 a2 = new(Int).Set(a)
927 b2 = new(Int).Set(b)
928 b2.GCD(X, Y, a2, b2)
929 if b2.Cmp(d) != 0 {
930 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, b2, d)
931 }
932 if x != nil && X.Cmp(x) != 0 {
933 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, X, x)
934 }
935 if y != nil && Y.Cmp(y) != 0 {
936 t.Errorf("aliased z = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, Y, y)
937 }
938
939 a2 = new(Int).Set(a)
940 b2 = new(Int).Set(b)
941 D = new(Int).GCD(a2, b2, a2, b2)
942 if D.Cmp(d) != 0 {
943 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
944 }
945 if x != nil && a2.Cmp(x) != 0 {
946 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, a2, x)
947 }
948 if y != nil && b2.Cmp(y) != 0 {
949 t.Errorf("aliased x = a, y = b GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, b2, y)
950 }
951
952 a2 = new(Int).Set(a)
953 b2 = new(Int).Set(b)
954 D = new(Int).GCD(b2, a2, a2, b2)
955 if D.Cmp(d) != 0 {
956 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got d = %s, want %s", x, y, a, b, D, d)
957 }
958 if x != nil && b2.Cmp(x) != 0 {
959 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got x = %s, want %s", x, y, a, b, b2, x)
960 }
961 if y != nil && a2.Cmp(y) != 0 {
962 t.Errorf("aliased x = b, y = a GCD(%s, %s, %s, %s): got y = %s, want %s", x, y, a, b, a2, y)
963 }
964 }
965
966 func TestGcd(t *testing.T) {
967 for _, test := range gcdTests {
968 d, _ := new(Int).SetString(test.d, 0)
969 x, _ := new(Int).SetString(test.x, 0)
970 y, _ := new(Int).SetString(test.y, 0)
971 a, _ := new(Int).SetString(test.a, 0)
972 b, _ := new(Int).SetString(test.b, 0)
973
974 testGcd(t, d, nil, nil, a, b)
975 testGcd(t, d, x, nil, a, b)
976 testGcd(t, d, nil, y, a, b)
977 testGcd(t, d, x, y, a, b)
978 }
979
980 if err := quick.Check(checkGcd, nil); err != nil {
981 t.Error(err)
982 }
983
984 if err := quick.Check(checkLehmerGcd, nil); err != nil {
985 t.Error(err)
986 }
987
988 if err := quick.Check(checkLehmerExtGcd, nil); err != nil {
989 t.Error(err)
990 }
991 }
992
993 type intShiftTest struct {
994 in string
995 shift uint
996 out string
997 }
998
999 var rshTests = []intShiftTest{
1000 {"0", 0, "0"},
1001 {"-0", 0, "0"},
1002 {"0", 1, "0"},
1003 {"0", 2, "0"},
1004 {"1", 0, "1"},
1005 {"1", 1, "0"},
1006 {"1", 2, "0"},
1007 {"2", 0, "2"},
1008 {"2", 1, "1"},
1009 {"-1", 0, "-1"},
1010 {"-1", 1, "-1"},
1011 {"-1", 10, "-1"},
1012 {"-100", 2, "-25"},
1013 {"-100", 3, "-13"},
1014 {"-100", 100, "-1"},
1015 {"4294967296", 0, "4294967296"},
1016 {"4294967296", 1, "2147483648"},
1017 {"4294967296", 2, "1073741824"},
1018 {"18446744073709551616", 0, "18446744073709551616"},
1019 {"18446744073709551616", 1, "9223372036854775808"},
1020 {"18446744073709551616", 2, "4611686018427387904"},
1021 {"18446744073709551616", 64, "1"},
1022 {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
1023 {"340282366920938463463374607431768211456", 128, "1"},
1024 }
1025
1026 func TestRsh(t *testing.T) {
1027 for i, test := range rshTests {
1028 in, _ := new(Int).SetString(test.in, 10)
1029 expected, _ := new(Int).SetString(test.out, 10)
1030 out := new(Int).Rsh(in, test.shift)
1031
1032 if !isNormalized(out) {
1033 t.Errorf("#%d: %v is not normalized", i, *out)
1034 }
1035 if out.Cmp(expected) != 0 {
1036 t.Errorf("#%d: got %s want %s", i, out, expected)
1037 }
1038 }
1039 }
1040
1041 func TestRshSelf(t *testing.T) {
1042 for i, test := range rshTests {
1043 z, _ := new(Int).SetString(test.in, 10)
1044 expected, _ := new(Int).SetString(test.out, 10)
1045 z.Rsh(z, test.shift)
1046
1047 if !isNormalized(z) {
1048 t.Errorf("#%d: %v is not normalized", i, *z)
1049 }
1050 if z.Cmp(expected) != 0 {
1051 t.Errorf("#%d: got %s want %s", i, z, expected)
1052 }
1053 }
1054 }
1055
1056 var lshTests = []intShiftTest{
1057 {"0", 0, "0"},
1058 {"0", 1, "0"},
1059 {"0", 2, "0"},
1060 {"1", 0, "1"},
1061 {"1", 1, "2"},
1062 {"1", 2, "4"},
1063 {"2", 0, "2"},
1064 {"2", 1, "4"},
1065 {"2", 2, "8"},
1066 {"-87", 1, "-174"},
1067 {"4294967296", 0, "4294967296"},
1068 {"4294967296", 1, "8589934592"},
1069 {"4294967296", 2, "17179869184"},
1070 {"18446744073709551616", 0, "18446744073709551616"},
1071 {"9223372036854775808", 1, "18446744073709551616"},
1072 {"4611686018427387904", 2, "18446744073709551616"},
1073 {"1", 64, "18446744073709551616"},
1074 {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
1075 {"1", 128, "340282366920938463463374607431768211456"},
1076 }
1077
1078 func TestLsh(t *testing.T) {
1079 for i, test := range lshTests {
1080 in, _ := new(Int).SetString(test.in, 10)
1081 expected, _ := new(Int).SetString(test.out, 10)
1082 out := new(Int).Lsh(in, test.shift)
1083
1084 if !isNormalized(out) {
1085 t.Errorf("#%d: %v is not normalized", i, *out)
1086 }
1087 if out.Cmp(expected) != 0 {
1088 t.Errorf("#%d: got %s want %s", i, out, expected)
1089 }
1090 }
1091 }
1092
1093 func TestLshSelf(t *testing.T) {
1094 for i, test := range lshTests {
1095 z, _ := new(Int).SetString(test.in, 10)
1096 expected, _ := new(Int).SetString(test.out, 10)
1097 z.Lsh(z, test.shift)
1098
1099 if !isNormalized(z) {
1100 t.Errorf("#%d: %v is not normalized", i, *z)
1101 }
1102 if z.Cmp(expected) != 0 {
1103 t.Errorf("#%d: got %s want %s", i, z, expected)
1104 }
1105 }
1106 }
1107
1108 func TestLshRsh(t *testing.T) {
1109 for i, test := range rshTests {
1110 in, _ := new(Int).SetString(test.in, 10)
1111 out := new(Int).Lsh(in, test.shift)
1112 out = out.Rsh(out, test.shift)
1113
1114 if !isNormalized(out) {
1115 t.Errorf("#%d: %v is not normalized", i, *out)
1116 }
1117 if in.Cmp(out) != 0 {
1118 t.Errorf("#%d: got %s want %s", i, out, in)
1119 }
1120 }
1121 for i, test := range lshTests {
1122 in, _ := new(Int).SetString(test.in, 10)
1123 out := new(Int).Lsh(in, test.shift)
1124 out.Rsh(out, test.shift)
1125
1126 if !isNormalized(out) {
1127 t.Errorf("#%d: %v is not normalized", i, *out)
1128 }
1129 if in.Cmp(out) != 0 {
1130 t.Errorf("#%d: got %s want %s", i, out, in)
1131 }
1132 }
1133 }
1134
1135
1136 var cmpAbsTests = []string{
1137 "0",
1138 "1",
1139 "2",
1140 "10",
1141 "10000000",
1142 "2783678367462374683678456387645876387564783686583485",
1143 "2783678367462374683678456387645876387564783686583486",
1144 "32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
1145 }
1146
1147 func TestCmpAbs(t *testing.T) {
1148 values := make([]*Int, len(cmpAbsTests))
1149 var prev *Int
1150 for i, s := range cmpAbsTests {
1151 x, ok := new(Int).SetString(s, 0)
1152 if !ok {
1153 t.Fatalf("SetString(%s, 0) failed", s)
1154 }
1155 if prev != nil && prev.Cmp(x) >= 0 {
1156 t.Fatal("cmpAbsTests entries not sorted in ascending order")
1157 }
1158 values[i] = x
1159 prev = x
1160 }
1161
1162 for i, x := range values {
1163 for j, y := range values {
1164
1165 for k := 0; k < 4; k++ {
1166 var a, b Int
1167 a.Set(x)
1168 b.Set(y)
1169 if k&1 != 0 {
1170 a.Neg(&a)
1171 }
1172 if k&2 != 0 {
1173 b.Neg(&b)
1174 }
1175
1176 got := a.CmpAbs(&b)
1177 want := 0
1178 switch {
1179 case i > j:
1180 want = 1
1181 case i < j:
1182 want = -1
1183 }
1184 if got != want {
1185 t.Errorf("absCmp |%s|, |%s|: got %d; want %d", &a, &b, got, want)
1186 }
1187 }
1188 }
1189 }
1190 }
1191
1192 func TestIntCmpSelf(t *testing.T) {
1193 for _, s := range cmpAbsTests {
1194 x, ok := new(Int).SetString(s, 0)
1195 if !ok {
1196 t.Fatalf("SetString(%s, 0) failed", s)
1197 }
1198 got := x.Cmp(x)
1199 want := 0
1200 if got != want {
1201 t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want)
1202 }
1203 }
1204 }
1205
1206 var int64Tests = []string{
1207
1208 "0",
1209 "1",
1210 "-1",
1211 "4294967295",
1212 "-4294967295",
1213 "4294967296",
1214 "-4294967296",
1215 "9223372036854775807",
1216 "-9223372036854775807",
1217 "-9223372036854775808",
1218
1219
1220 "0x8000000000000000",
1221 "-0x8000000000000001",
1222 "38579843757496759476987459679745",
1223 "-38579843757496759476987459679745",
1224 }
1225
1226 func TestInt64(t *testing.T) {
1227 for _, s := range int64Tests {
1228 var x Int
1229 _, ok := x.SetString(s, 0)
1230 if !ok {
1231 t.Errorf("SetString(%s, 0) failed", s)
1232 continue
1233 }
1234
1235 want, err := strconv.ParseInt(s, 0, 64)
1236 if err != nil {
1237 if err.(*strconv.NumError).Err == strconv.ErrRange {
1238 if x.IsInt64() {
1239 t.Errorf("IsInt64(%s) succeeded unexpectedly", s)
1240 }
1241 } else {
1242 t.Errorf("ParseInt(%s) failed", s)
1243 }
1244 continue
1245 }
1246
1247 if !x.IsInt64() {
1248 t.Errorf("IsInt64(%s) failed unexpectedly", s)
1249 }
1250
1251 got := x.Int64()
1252 if got != want {
1253 t.Errorf("Int64(%s) = %d; want %d", s, got, want)
1254 }
1255 }
1256 }
1257
1258 var uint64Tests = []string{
1259
1260 "0",
1261 "1",
1262 "4294967295",
1263 "4294967296",
1264 "8589934591",
1265 "8589934592",
1266 "9223372036854775807",
1267 "9223372036854775808",
1268 "0x08000000000000000",
1269
1270
1271 "0x10000000000000000",
1272 "-0x08000000000000000",
1273 "-1",
1274 }
1275
1276 func TestUint64(t *testing.T) {
1277 for _, s := range uint64Tests {
1278 var x Int
1279 _, ok := x.SetString(s, 0)
1280 if !ok {
1281 t.Errorf("SetString(%s, 0) failed", s)
1282 continue
1283 }
1284
1285 want, err := strconv.ParseUint(s, 0, 64)
1286 if err != nil {
1287
1288 if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange {
1289 if x.IsUint64() {
1290 t.Errorf("IsUint64(%s) succeeded unexpectedly", s)
1291 }
1292 } else {
1293 t.Errorf("ParseUint(%s) failed", s)
1294 }
1295 continue
1296 }
1297
1298 if !x.IsUint64() {
1299 t.Errorf("IsUint64(%s) failed unexpectedly", s)
1300 }
1301
1302 got := x.Uint64()
1303 if got != want {
1304 t.Errorf("Uint64(%s) = %d; want %d", s, got, want)
1305 }
1306 }
1307 }
1308
1309 var bitwiseTests = []struct {
1310 x, y string
1311 and, or, xor, andNot string
1312 }{
1313 {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1314 {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1315 {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1316 {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1317 {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1318 {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1319 {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1320 {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1321 {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1322 {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1323 {"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
1324 {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1325 {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1326 {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1327 {
1328 "0x1000009dc6e3d9822cba04129bcbe3401",
1329 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1330 "0x1000001186210100001000009048c2001",
1331 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1332 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1333 "0x8c40c2d8822caa04120b8321400",
1334 },
1335 {
1336 "0x1000009dc6e3d9822cba04129bcbe3401",
1337 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1338 "0x8c40c2d8822caa04120b8321401",
1339 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1340 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1341 "0x1000001186210100001000009048c2000",
1342 },
1343 {
1344 "-0x1000009dc6e3d9822cba04129bcbe3401",
1345 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1346 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1347 "-0x1000001186210100001000009048c2001",
1348 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1349 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1350 },
1351 }
1352
1353 type bitFun func(z, x, y *Int) *Int
1354
1355 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1356 expected := new(Int)
1357 expected.SetString(exp, 0)
1358
1359 out := f(new(Int), x, y)
1360 if out.Cmp(expected) != 0 {
1361 t.Errorf("%s: got %s want %s", msg, out, expected)
1362 }
1363 }
1364
1365 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1366 self := new(Int)
1367 self.Set(x)
1368 expected := new(Int)
1369 expected.SetString(exp, 0)
1370
1371 self = f(self, self, y)
1372 if self.Cmp(expected) != 0 {
1373 t.Errorf("%s: got %s want %s", msg, self, expected)
1374 }
1375 }
1376
1377 func altBit(x *Int, i int) uint {
1378 z := new(Int).Rsh(x, uint(i))
1379 z = z.And(z, NewInt(1))
1380 if z.Cmp(new(Int)) != 0 {
1381 return 1
1382 }
1383 return 0
1384 }
1385
1386 func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1387 one := NewInt(1)
1388 m := one.Lsh(one, uint(i))
1389 switch b {
1390 case 1:
1391 return z.Or(x, m)
1392 case 0:
1393 return z.AndNot(x, m)
1394 }
1395 panic("set bit is not 0 or 1")
1396 }
1397
1398 func testBitset(t *testing.T, x *Int) {
1399 n := x.BitLen()
1400 z := new(Int).Set(x)
1401 z1 := new(Int).Set(x)
1402 for i := 0; i < n+10; i++ {
1403 old := z.Bit(i)
1404 old1 := altBit(z1, i)
1405 if old != old1 {
1406 t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1407 }
1408 z := new(Int).SetBit(z, i, 1)
1409 z1 := altSetBit(new(Int), z1, i, 1)
1410 if z.Bit(i) == 0 {
1411 t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1412 }
1413 if z.Cmp(z1) != 0 {
1414 t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1415 }
1416 z.SetBit(z, i, 0)
1417 altSetBit(z1, z1, i, 0)
1418 if z.Bit(i) != 0 {
1419 t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1420 }
1421 if z.Cmp(z1) != 0 {
1422 t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1423 }
1424 altSetBit(z1, z1, i, old)
1425 z.SetBit(z, i, old)
1426 if z.Cmp(z1) != 0 {
1427 t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1428 }
1429 }
1430 if z.Cmp(x) != 0 {
1431 t.Errorf("bitset: got %s want %s", z, x)
1432 }
1433 }
1434
1435 var bitsetTests = []struct {
1436 x string
1437 i int
1438 b uint
1439 }{
1440 {"0", 0, 0},
1441 {"0", 200, 0},
1442 {"1", 0, 1},
1443 {"1", 1, 0},
1444 {"-1", 0, 1},
1445 {"-1", 200, 1},
1446 {"0x2000000000000000000000000000", 108, 0},
1447 {"0x2000000000000000000000000000", 109, 1},
1448 {"0x2000000000000000000000000000", 110, 0},
1449 {"-0x2000000000000000000000000001", 108, 1},
1450 {"-0x2000000000000000000000000001", 109, 0},
1451 {"-0x2000000000000000000000000001", 110, 1},
1452 }
1453
1454 func TestBitSet(t *testing.T) {
1455 for _, test := range bitwiseTests {
1456 x := new(Int)
1457 x.SetString(test.x, 0)
1458 testBitset(t, x)
1459 x = new(Int)
1460 x.SetString(test.y, 0)
1461 testBitset(t, x)
1462 }
1463 for i, test := range bitsetTests {
1464 x := new(Int)
1465 x.SetString(test.x, 0)
1466 b := x.Bit(test.i)
1467 if b != test.b {
1468 t.Errorf("#%d got %v want %v", i, b, test.b)
1469 }
1470 }
1471 z := NewInt(1)
1472 z.SetBit(NewInt(0), 2, 1)
1473 if z.Cmp(NewInt(4)) != 0 {
1474 t.Errorf("destination leaked into result; got %s want 4", z)
1475 }
1476 }
1477
1478 var tzbTests = []struct {
1479 in string
1480 out uint
1481 }{
1482 {"0", 0},
1483 {"1", 0},
1484 {"-1", 0},
1485 {"4", 2},
1486 {"-8", 3},
1487 {"0x4000000000000000000", 74},
1488 {"-0x8000000000000000000", 75},
1489 }
1490
1491 func TestTrailingZeroBits(t *testing.T) {
1492 for i, test := range tzbTests {
1493 in, _ := new(Int).SetString(test.in, 0)
1494 want := test.out
1495 got := in.TrailingZeroBits()
1496
1497 if got != want {
1498 t.Errorf("#%d: got %v want %v", i, got, want)
1499 }
1500 }
1501 }
1502
1503 func BenchmarkBitset(b *testing.B) {
1504 z := new(Int)
1505 z.SetBit(z, 512, 1)
1506 b.ResetTimer()
1507 for i := b.N - 1; i >= 0; i-- {
1508 z.SetBit(z, i&512, 1)
1509 }
1510 }
1511
1512 func BenchmarkBitsetNeg(b *testing.B) {
1513 z := NewInt(-1)
1514 z.SetBit(z, 512, 0)
1515 b.ResetTimer()
1516 for i := b.N - 1; i >= 0; i-- {
1517 z.SetBit(z, i&512, 0)
1518 }
1519 }
1520
1521 func BenchmarkBitsetOrig(b *testing.B) {
1522 z := new(Int)
1523 altSetBit(z, z, 512, 1)
1524 b.ResetTimer()
1525 for i := b.N - 1; i >= 0; i-- {
1526 altSetBit(z, z, i&512, 1)
1527 }
1528 }
1529
1530 func BenchmarkBitsetNegOrig(b *testing.B) {
1531 z := NewInt(-1)
1532 altSetBit(z, z, 512, 0)
1533 b.ResetTimer()
1534 for i := b.N - 1; i >= 0; i-- {
1535 altSetBit(z, z, i&512, 0)
1536 }
1537 }
1538
1539
1540
1541 func tri(n uint) *Int {
1542 x := NewInt(1)
1543 x.Lsh(x, n)
1544 x2 := new(Int).Lsh(x, n)
1545 x2.Sub(x2, x)
1546 x2.Sub(x2, intOne)
1547 return x2
1548 }
1549
1550 func BenchmarkModSqrt225_Tonelli(b *testing.B) {
1551 p := tri(225)
1552 x := NewInt(2)
1553 for i := 0; i < b.N; i++ {
1554 x.SetUint64(2)
1555 x.modSqrtTonelliShanks(x, p)
1556 }
1557 }
1558
1559 func BenchmarkModSqrt225_3Mod4(b *testing.B) {
1560 p := tri(225)
1561 x := new(Int).SetUint64(2)
1562 for i := 0; i < b.N; i++ {
1563 x.SetUint64(2)
1564 x.modSqrt3Mod4Prime(x, p)
1565 }
1566 }
1567
1568 func BenchmarkModSqrt231_Tonelli(b *testing.B) {
1569 p := tri(231)
1570 p.Sub(p, intOne)
1571 p.Sub(p, intOne)
1572 x := new(Int).SetUint64(7)
1573 for i := 0; i < b.N; i++ {
1574 x.SetUint64(7)
1575 x.modSqrtTonelliShanks(x, p)
1576 }
1577 }
1578
1579 func BenchmarkModSqrt231_5Mod8(b *testing.B) {
1580 p := tri(231)
1581 p.Sub(p, intOne)
1582 p.Sub(p, intOne)
1583 x := new(Int).SetUint64(7)
1584 for i := 0; i < b.N; i++ {
1585 x.SetUint64(7)
1586 x.modSqrt5Mod8Prime(x, p)
1587 }
1588 }
1589
1590 func TestBitwise(t *testing.T) {
1591 x := new(Int)
1592 y := new(Int)
1593 for _, test := range bitwiseTests {
1594 x.SetString(test.x, 0)
1595 y.SetString(test.y, 0)
1596
1597 testBitFun(t, "and", (*Int).And, x, y, test.and)
1598 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1599 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1600 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1601 testBitFun(t, "or", (*Int).Or, x, y, test.or)
1602 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1603 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1604 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1605 }
1606 }
1607
1608 var notTests = []struct {
1609 in string
1610 out string
1611 }{
1612 {"0", "-1"},
1613 {"1", "-2"},
1614 {"7", "-8"},
1615 {"0", "-1"},
1616 {"-81910", "81909"},
1617 {
1618 "298472983472983471903246121093472394872319615612417471234712061",
1619 "-298472983472983471903246121093472394872319615612417471234712062",
1620 },
1621 }
1622
1623 func TestNot(t *testing.T) {
1624 in := new(Int)
1625 out := new(Int)
1626 expected := new(Int)
1627 for i, test := range notTests {
1628 in.SetString(test.in, 10)
1629 expected.SetString(test.out, 10)
1630 out = out.Not(in)
1631 if out.Cmp(expected) != 0 {
1632 t.Errorf("#%d: got %s want %s", i, out, expected)
1633 }
1634 out = out.Not(out)
1635 if out.Cmp(in) != 0 {
1636 t.Errorf("#%d: got %s want %s", i, out, in)
1637 }
1638 }
1639 }
1640
1641 var modInverseTests = []struct {
1642 element string
1643 modulus string
1644 }{
1645 {"1234567", "458948883992"},
1646 {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1647 {"-10", "13"},
1648 {"10", "-13"},
1649 {"-17", "-13"},
1650 }
1651
1652 func TestModInverse(t *testing.T) {
1653 var element, modulus, gcd, inverse Int
1654 one := NewInt(1)
1655 for _, test := range modInverseTests {
1656 (&element).SetString(test.element, 10)
1657 (&modulus).SetString(test.modulus, 10)
1658 (&inverse).ModInverse(&element, &modulus)
1659 (&inverse).Mul(&inverse, &element)
1660 (&inverse).Mod(&inverse, &modulus)
1661 if (&inverse).Cmp(one) != 0 {
1662 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1663 }
1664 }
1665
1666 for n := 2; n < 100; n++ {
1667 (&modulus).SetInt64(int64(n))
1668 for x := 1; x < n; x++ {
1669 (&element).SetInt64(int64(x))
1670 (&gcd).GCD(nil, nil, &element, &modulus)
1671 if (&gcd).Cmp(one) != 0 {
1672 continue
1673 }
1674 (&inverse).ModInverse(&element, &modulus)
1675 (&inverse).Mul(&inverse, &element)
1676 (&inverse).Mod(&inverse, &modulus)
1677 if (&inverse).Cmp(one) != 0 {
1678 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1679 }
1680 }
1681 }
1682 }
1683
1684 func BenchmarkModInverse(b *testing.B) {
1685 p := new(Int).SetInt64(1)
1686 p.abs = p.abs.lsh(p.abs, 1279)
1687 p.Sub(p, intOne)
1688 x := new(Int).Sub(p, intOne)
1689 z := new(Int)
1690 for i := 0; i < b.N; i++ {
1691 z.ModInverse(x, p)
1692 }
1693 }
1694
1695
1696
1697 func testModSqrt(t *testing.T, elt, mod, sq, sqrt *Int) bool {
1698 var sqChk, sqrtChk, sqrtsq Int
1699 sq.Mul(elt, elt)
1700 sq.Mod(sq, mod)
1701 z := sqrt.ModSqrt(sq, mod)
1702 if z != sqrt {
1703 t.Errorf("ModSqrt returned wrong value %s", z)
1704 }
1705
1706
1707 sqChk.Add(sq, mod)
1708 z = sqrtChk.ModSqrt(&sqChk, mod)
1709 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1710 t.Errorf("ModSqrt returned inconsistent value %s", z)
1711 }
1712 sqChk.Sub(sq, mod)
1713 z = sqrtChk.ModSqrt(&sqChk, mod)
1714 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1715 t.Errorf("ModSqrt returned inconsistent value %s", z)
1716 }
1717
1718
1719 z = sqrtChk.ModSqrt(sqrtChk.Set(sq), mod)
1720 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
1721 t.Errorf("ModSqrt returned inconsistent value %s", z)
1722 }
1723
1724
1725 if sqrt.Cmp(elt) == 0 {
1726 return true
1727 }
1728 sqrtsq.Mul(sqrt, sqrt)
1729 sqrtsq.Mod(&sqrtsq, mod)
1730 return sq.Cmp(&sqrtsq) == 0
1731 }
1732
1733 func TestModSqrt(t *testing.T) {
1734 var elt, mod, modx4, sq, sqrt Int
1735 r := rand.New(rand.NewSource(9))
1736 for i, s := range primes[1:] {
1737 mod.SetString(s, 10)
1738 modx4.Lsh(&mod, 2)
1739
1740
1741 for x := 1; x < 5; x++ {
1742 elt.Rand(r, &modx4)
1743 elt.Sub(&elt, &mod)
1744 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1745 t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
1746 }
1747 }
1748
1749 if testing.Short() && i > 2 {
1750 break
1751 }
1752 }
1753
1754 if testing.Short() {
1755 return
1756 }
1757
1758
1759 for n := 3; n < 100; n++ {
1760 mod.SetInt64(int64(n))
1761 if !mod.ProbablyPrime(10) {
1762 continue
1763 }
1764 isSquare := make([]bool, n)
1765
1766
1767 for x := 1; x < n; x++ {
1768 elt.SetInt64(int64(x))
1769 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
1770 t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
1771 }
1772 isSquare[sq.Uint64()] = true
1773 }
1774
1775
1776 for x := 1; x < n; x++ {
1777 sq.SetInt64(int64(x))
1778 z := sqrt.ModSqrt(&sq, &mod)
1779 if !isSquare[x] && z != nil {
1780 t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
1781 }
1782 }
1783 }
1784 }
1785
1786 func TestJacobi(t *testing.T) {
1787 testCases := []struct {
1788 x, y int64
1789 result int
1790 }{
1791 {0, 1, 1},
1792 {0, -1, 1},
1793 {1, 1, 1},
1794 {1, -1, 1},
1795 {0, 5, 0},
1796 {1, 5, 1},
1797 {2, 5, -1},
1798 {-2, 5, -1},
1799 {2, -5, -1},
1800 {-2, -5, 1},
1801 {3, 5, -1},
1802 {5, 5, 0},
1803 {-5, 5, 0},
1804 {6, 5, 1},
1805 {6, -5, 1},
1806 {-6, 5, 1},
1807 {-6, -5, -1},
1808 }
1809
1810 var x, y Int
1811
1812 for i, test := range testCases {
1813 x.SetInt64(test.x)
1814 y.SetInt64(test.y)
1815 expected := test.result
1816 actual := Jacobi(&x, &y)
1817 if actual != expected {
1818 t.Errorf("#%d: Jacobi(%d, %d) = %d, but expected %d", i, test.x, test.y, actual, expected)
1819 }
1820 }
1821 }
1822
1823 func TestJacobiPanic(t *testing.T) {
1824 const failureMsg = "test failure"
1825 defer func() {
1826 msg := recover()
1827 if msg == nil || msg == failureMsg {
1828 panic(msg)
1829 }
1830 t.Log(msg)
1831 }()
1832 x := NewInt(1)
1833 y := NewInt(2)
1834
1835 Jacobi(x, y)
1836 panic(failureMsg)
1837 }
1838
1839 func TestIssue2607(t *testing.T) {
1840
1841 n := NewInt(10)
1842 n.Rand(rand.New(rand.NewSource(9)), n)
1843 }
1844
1845 func TestSqrt(t *testing.T) {
1846 root := 0
1847 r := new(Int)
1848 for i := 0; i < 10000; i++ {
1849 if (root+1)*(root+1) <= i {
1850 root++
1851 }
1852 n := NewInt(int64(i))
1853 r.SetInt64(-2)
1854 r.Sqrt(n)
1855 if r.Cmp(NewInt(int64(root))) != 0 {
1856 t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
1857 }
1858 }
1859
1860 for i := 0; i < 1000; i += 10 {
1861 n, _ := new(Int).SetString("1"+strings.Repeat("0", i), 10)
1862 r := new(Int).Sqrt(n)
1863 root, _ := new(Int).SetString("1"+strings.Repeat("0", i/2), 10)
1864 if r.Cmp(root) != 0 {
1865 t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
1866 }
1867 }
1868
1869
1870 r.SetInt64(100)
1871 r.Sqrt(r)
1872 if r.Int64() != 10 {
1873 t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
1874 }
1875 }
1876
1877
1878
1879 func TestIssue22830(t *testing.T) {
1880 one := new(Int).SetInt64(1)
1881 base, _ := new(Int).SetString("84555555300000000000", 10)
1882 mod, _ := new(Int).SetString("66666670001111111111", 10)
1883 want, _ := new(Int).SetString("17888885298888888889", 10)
1884
1885 var tests = []int64{
1886 0, 1, -1,
1887 }
1888
1889 for _, n := range tests {
1890 m := NewInt(n)
1891 if got := m.Exp(base, one, mod); got.Cmp(want) != 0 {
1892 t.Errorf("(%v).Exp(%s, 1, %s) = %s, want %s", n, base, mod, got, want)
1893 }
1894 }
1895 }
1896
1897 func BenchmarkSqrt(b *testing.B) {
1898 n, _ := new(Int).SetString("1"+strings.Repeat("0", 1001), 10)
1899 b.ResetTimer()
1900 t := new(Int)
1901 for i := 0; i < b.N; i++ {
1902 t.Sqrt(n)
1903 }
1904 }
1905
1906 func benchmarkIntSqr(b *testing.B, nwords int) {
1907 x := new(Int)
1908 x.abs = rndNat(nwords)
1909 t := new(Int)
1910 b.ResetTimer()
1911 for i := 0; i < b.N; i++ {
1912 t.Mul(x, x)
1913 }
1914 }
1915
1916 func BenchmarkIntSqr(b *testing.B) {
1917 for _, n := range sqrBenchSizes {
1918 if isRaceBuilder && n > 1e3 {
1919 continue
1920 }
1921 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
1922 benchmarkIntSqr(b, n)
1923 })
1924 }
1925 }
1926
1927 func benchmarkDiv(b *testing.B, aSize, bSize int) {
1928 var r = rand.New(rand.NewSource(1234))
1929 aa := randInt(r, uint(aSize))
1930 bb := randInt(r, uint(bSize))
1931 if aa.Cmp(bb) < 0 {
1932 aa, bb = bb, aa
1933 }
1934 x := new(Int)
1935 y := new(Int)
1936
1937 b.ResetTimer()
1938 for i := 0; i < b.N; i++ {
1939 x.DivMod(aa, bb, y)
1940 }
1941 }
1942
1943 func BenchmarkDiv(b *testing.B) {
1944 sizes := []int{
1945 10, 20, 50, 100, 200, 500, 1000,
1946 1e4, 1e5, 1e6, 1e7,
1947 }
1948 for _, i := range sizes {
1949 j := 2 * i
1950 b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) {
1951 benchmarkDiv(b, j, i)
1952 })
1953 }
1954 }
1955
1956 func TestFillBytes(t *testing.T) {
1957 checkResult := func(t *testing.T, buf []byte, want *Int) {
1958 t.Helper()
1959 got := new(Int).SetBytes(buf)
1960 if got.CmpAbs(want) != 0 {
1961 t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
1962 }
1963 }
1964 panics := func(f func()) (panic bool) {
1965 defer func() { panic = recover() != nil }()
1966 f()
1967 return
1968 }
1969
1970 for _, n := range []string{
1971 "0",
1972 "1000",
1973 "0xffffffff",
1974 "-0xffffffff",
1975 "0xffffffffffffffff",
1976 "0x10000000000000000",
1977 "0xabababababababababababababababababababababababababa",
1978 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
1979 } {
1980 t.Run(n, func(t *testing.T) {
1981 t.Log(n)
1982 x, ok := new(Int).SetString(n, 0)
1983 if !ok {
1984 panic("invalid test entry")
1985 }
1986
1987
1988 byteLen := (x.BitLen() + 7) / 8
1989 buf := make([]byte, byteLen)
1990 checkResult(t, x.FillBytes(buf), x)
1991
1992
1993 buf = make([]byte, 100)
1994 for i := range buf {
1995 buf[i] = 0xff
1996 }
1997 checkResult(t, x.FillBytes(buf), x)
1998
1999
2000 if byteLen > 0 {
2001 buf = make([]byte, byteLen-1)
2002 if !panics(func() { x.FillBytes(buf) }) {
2003 t.Errorf("expected panic for small buffer and value %x", x)
2004 }
2005 }
2006 })
2007 }
2008 }
2009
2010 func TestNewIntMinInt64(t *testing.T) {
2011
2012 want := int64(math.MinInt64)
2013 if got := NewInt(want).Int64(); got != want {
2014 t.Fatalf("wanted %d, got %d", want, got)
2015 }
2016 }
2017
2018 func TestNewIntAllocs(t *testing.T) {
2019 testenv.SkipIfOptimizationOff(t)
2020 for _, n := range []int64{0, 7, -7, 1 << 30, -1 << 30, 1 << 50, -1 << 50} {
2021 x := NewInt(3)
2022 got := testing.AllocsPerRun(100, func() {
2023
2024
2025
2026 x.Add(x, NewInt(n))
2027 })
2028 if got != 0 {
2029 t.Errorf("x.Add(x, NewInt(%d)), wanted 0 allocations, got %f", n, got)
2030 }
2031 }
2032 }
2033
2034 func TestFloat64(t *testing.T) {
2035 for _, test := range []struct {
2036 istr string
2037 f float64
2038 acc Accuracy
2039 }{
2040 {"-1000000000000000000000000000000000000000000000000000000", -1000000000000000078291540404596243842305360299886116864.000000, Below},
2041 {"-9223372036854775809", math.MinInt64, Above},
2042 {"-9223372036854775808", -9223372036854775808, Exact},
2043 {"-9223372036854775807", -9223372036854775807, Below},
2044 {"-18014398509481985", -18014398509481984.000000, Above},
2045 {"-18014398509481984", -18014398509481984.000000, Exact},
2046 {"-18014398509481983", -18014398509481984.000000, Below},
2047 {"-9007199254740993", -9007199254740992.000000, Above},
2048 {"-9007199254740992", -9007199254740992.000000, Exact},
2049 {"-9007199254740991", -9007199254740991.000000, Exact},
2050 {"-4503599627370497", -4503599627370497.000000, Exact},
2051 {"-4503599627370496", -4503599627370496.000000, Exact},
2052 {"-4503599627370495", -4503599627370495.000000, Exact},
2053 {"-12345", -12345, Exact},
2054 {"-1", -1, Exact},
2055 {"0", 0, Exact},
2056 {"1", 1, Exact},
2057 {"12345", 12345, Exact},
2058 {"0x1010000000000000", 0x1010000000000000, Exact},
2059 {"9223372036854775807", 9223372036854775808, Above},
2060 {"9223372036854775808", 9223372036854775808, Exact},
2061 {"1000000000000000000000000000000000000000000000000000000", 1000000000000000078291540404596243842305360299886116864.000000, Above},
2062 } {
2063 i, ok := new(Int).SetString(test.istr, 0)
2064 if !ok {
2065 t.Errorf("SetString(%s) failed", test.istr)
2066 continue
2067 }
2068
2069
2070 f, acc := i.Float64()
2071 if f != test.f || acc != test.acc {
2072 t.Errorf("%s: got %f (%s); want %f (%s)", test.istr, f, acc, test.f, test.acc)
2073 }
2074
2075
2076 f2, acc2 := new(Float).SetInt(i).Float64()
2077 if f != f2 || acc != acc2 {
2078 t.Errorf("%s: got %f (%s); Float.Float64 gives %f (%s)", test.istr, f, acc, f2, acc2)
2079 }
2080 }
2081 }
2082
View as plain text