1
2
3
4
5 package big
6
7 import (
8 "bytes"
9 "encoding/hex"
10 "fmt"
11 "gob"
12 "testing"
13 "testing/quick"
14 )
15
16 func isNormalized(x *Int) bool {
17 if len(x.abs) == 0 {
18 return !x.neg
19 }
20
21 return x.abs[len(x.abs)-1] != 0
22 }
23
24 type funZZ func(z, x, y *Int) *Int
25 type argZZ struct {
26 z, x, y *Int
27 }
28
29 var sumZZ = []argZZ{
30 {NewInt(0), NewInt(0), NewInt(0)},
31 {NewInt(1), NewInt(1), NewInt(0)},
32 {NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
33 {NewInt(-1), NewInt(-1), NewInt(0)},
34 {NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
35 {NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
36 }
37
38 var prodZZ = []argZZ{
39 {NewInt(0), NewInt(0), NewInt(0)},
40 {NewInt(0), NewInt(1), NewInt(0)},
41 {NewInt(1), NewInt(1), NewInt(1)},
42 {NewInt(-991 * 991), NewInt(991), NewInt(-991)},
43
44 }
45
46 func TestSignZ(t *testing.T) {
47 var zero Int
48 for _, a := range sumZZ {
49 s := a.z.Sign()
50 e := a.z.Cmp(&zero)
51 if s != e {
52 t.Errorf("got %d; want %d for z = %v", s, e, a.z)
53 }
54 }
55 }
56
57 func TestSetZ(t *testing.T) {
58 for _, a := range sumZZ {
59 var z Int
60 z.Set(a.z)
61 if !isNormalized(&z) {
62 t.Errorf("%v is not normalized", z)
63 }
64 if (&z).Cmp(a.z) != 0 {
65 t.Errorf("got z = %v; want %v", z, a.z)
66 }
67 }
68 }
69
70 func TestAbsZ(t *testing.T) {
71 var zero Int
72 for _, a := range sumZZ {
73 var z Int
74 z.Abs(a.z)
75 var e Int
76 e.Set(a.z)
77 if e.Cmp(&zero) < 0 {
78 e.Sub(&zero, &e)
79 }
80 if z.Cmp(&e) != 0 {
81 t.Errorf("got z = %v; want %v", z, e)
82 }
83 }
84 }
85
86 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
87 var z Int
88 f(&z, a.x, a.y)
89 if !isNormalized(&z) {
90 t.Errorf("%s%v is not normalized", z, msg)
91 }
92 if (&z).Cmp(a.z) != 0 {
93 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
94 }
95 }
96
97 func TestSumZZ(t *testing.T) {
98 AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
99 SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
100 for _, a := range sumZZ {
101 arg := a
102 testFunZZ(t, "AddZZ", AddZZ, arg)
103
104 arg = argZZ{a.z, a.y, a.x}
105 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
106
107 arg = argZZ{a.x, a.z, a.y}
108 testFunZZ(t, "SubZZ", SubZZ, arg)
109
110 arg = argZZ{a.y, a.z, a.x}
111 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
112 }
113 }
114
115 func TestProdZZ(t *testing.T) {
116 MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
117 for _, a := range prodZZ {
118 arg := a
119 testFunZZ(t, "MulZZ", MulZZ, arg)
120
121 arg = argZZ{a.z, a.y, a.x}
122 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
123 }
124 }
125
126
127
128
129 func mulBytes(x, y []byte) []byte {
130 z := make([]byte, len(x)+len(y))
131
132
133 k0 := len(z) - 1
134 for j := len(y) - 1; j >= 0; j-- {
135 d := int(y[j])
136 if d != 0 {
137 k := k0
138 carry := 0
139 for i := len(x) - 1; i >= 0; i-- {
140 t := int(z[k]) + int(x[i])*d + carry
141 z[k], carry = byte(t), t>>8
142 k--
143 }
144 z[k] = byte(carry)
145 }
146 k0--
147 }
148
149
150 i := 0
151 for i < len(z) && z[i] == 0 {
152 i++
153 }
154
155 return z[i:]
156 }
157
158 func checkMul(a, b []byte) bool {
159 var x, y, z1 Int
160 x.SetBytes(a)
161 y.SetBytes(b)
162 z1.Mul(&x, &y)
163
164 var z2 Int
165 z2.SetBytes(mulBytes(a, b))
166
167 return z1.Cmp(&z2) == 0
168 }
169
170 func TestMul(t *testing.T) {
171 if err := quick.Check(checkMul, nil); err != nil {
172 t.Error(err)
173 }
174 }
175
176 var mulRangesZ = []struct {
177 a, b int64
178 prod string
179 }{
180
181 {-1, 1, "0"},
182 {-2, -1, "2"},
183 {-3, -2, "6"},
184 {-3, -1, "-6"},
185 {1, 3, "6"},
186 {-10, -10, "-10"},
187 {0, -1, "1"},
188 {-1, -100, "1"},
189 {-1, 1, "0"},
190 {-1e9, 0, "0"},
191 {-1e9, 1e9, "0"},
192 {-10, -1, "3628800"},
193 {-20, -2, "-2432902008176640000"},
194 {-99, -1,
195 "-933262154439441526816992388562667004907159682643816214685929" +
196 "638952175999932299156089414639761565182862536979208272237582" +
197 "511852109168640000000000000000000000",
198 },
199 }
200
201 func TestMulRangeZ(t *testing.T) {
202 var tmp Int
203
204 for i, r := range mulRangesN {
205 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
206 if prod != r.prod {
207 t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
208 }
209 }
210
211 for i, r := range mulRangesZ {
212 prod := tmp.MulRange(r.a, r.b).String()
213 if prod != r.prod {
214 t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
215 }
216 }
217 }
218
219 var stringTests = []struct {
220 in string
221 out string
222 base int
223 val int64
224 ok bool
225 }{
226 {in: "", ok: false},
227 {in: "a", ok: false},
228 {in: "z", ok: false},
229 {in: "+", ok: false},
230 {in: "-", ok: false},
231 {in: "0b", ok: false},
232 {in: "0x", ok: false},
233 {in: "2", base: 2, ok: false},
234 {in: "0b2", base: 0, ok: false},
235 {in: "08", ok: false},
236 {in: "8", base: 8, ok: false},
237 {in: "0xg", base: 0, ok: false},
238 {in: "g", base: 16, ok: false},
239 {"0", "0", 0, 0, true},
240 {"0", "0", 10, 0, true},
241 {"0", "0", 16, 0, true},
242 {"+0", "0", 0, 0, true},
243 {"-0", "0", 0, 0, true},
244 {"10", "10", 0, 10, true},
245 {"10", "10", 10, 10, true},
246 {"10", "10", 16, 16, true},
247 {"-10", "-10", 16, -16, true},
248 {"+10", "10", 16, 16, true},
249 {"0x10", "16", 0, 16, true},
250 {in: "0x10", base: 16, ok: false},
251 {"-0x10", "-16", 0, -16, true},
252 {"+0x10", "16", 0, 16, true},
253 {"00", "0", 0, 0, true},
254 {"0", "0", 8, 0, true},
255 {"07", "7", 0, 7, true},
256 {"7", "7", 8, 7, true},
257 {"023", "19", 0, 19, true},
258 {"23", "23", 8, 19, true},
259 {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
260 {"0b0", "0", 0, 0, true},
261 {"-111", "-111", 2, -7, true},
262 {"-0b111", "-7", 0, -7, true},
263 {"0b1001010111", "599", 0, 0x257, true},
264 {"1001010111", "1001010111", 2, 0x257, true},
265 }
266
267 func format(base int) string {
268 switch base {
269 case 2:
270 return "%b"
271 case 8:
272 return "%o"
273 case 16:
274 return "%x"
275 }
276 return "%d"
277 }
278
279 func TestGetString(t *testing.T) {
280 z := new(Int)
281 for i, test := range stringTests {
282 if !test.ok {
283 continue
284 }
285 z.SetInt64(test.val)
286
287 if test.base == 10 {
288 s := z.String()
289 if s != test.out {
290 t.Errorf("#%da got %s; want %s", i, s, test.out)
291 }
292 }
293
294 s := fmt.Sprintf(format(test.base), z)
295 if s != test.out {
296 t.Errorf("#%db got %s; want %s", i, s, test.out)
297 }
298 }
299 }
300
301 func TestSetString(t *testing.T) {
302 tmp := new(Int)
303 for i, test := range stringTests {
304 n1, ok1 := new(Int).SetString(test.in, test.base)
305 n2, ok2 := tmp.SetString(test.in, test.base)
306 expected := NewInt(test.val)
307 if ok1 != test.ok || ok2 != test.ok {
308 t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
309 continue
310 }
311 if !ok1 || !ok2 {
312 continue
313 }
314
315 if ok1 && !isNormalized(n1) {
316 t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
317 }
318 if ok2 && !isNormalized(n2) {
319 t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
320 }
321
322 if n1.Cmp(expected) != 0 {
323 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
324 }
325 if n2.Cmp(expected) != 0 {
326 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
327 }
328 }
329 }
330
331 var formatTests = []struct {
332 input string
333 format string
334 output string
335 }{
336 {"<nil>", "%x", "<nil>"},
337 {"<nil>", "%#x", "<nil>"},
338 {"<nil>", "%#y", "%!y(big.Int=<nil>)"},
339
340 {"10", "%b", "1010"},
341 {"10", "%o", "12"},
342 {"10", "%d", "10"},
343 {"10", "%v", "10"},
344 {"10", "%x", "a"},
345 {"10", "%X", "A"},
346 {"-10", "%X", "-A"},
347 {"10", "%y", "%!y(big.Int=10)"},
348 {"-10", "%y", "%!y(big.Int=-10)"},
349
350 {"10", "%#b", "1010"},
351 {"10", "%#o", "012"},
352 {"10", "%#d", "10"},
353 {"10", "%#v", "10"},
354 {"10", "%#x", "0xa"},
355 {"10", "%#X", "0XA"},
356 {"-10", "%#X", "-0XA"},
357 {"10", "%#y", "%!y(big.Int=10)"},
358 {"-10", "%#y", "%!y(big.Int=-10)"},
359
360 {"1234", "%d", "1234"},
361 {"1234", "%3d", "1234"},
362 {"1234", "%4d", "1234"},
363 {"-1234", "%d", "-1234"},
364 {"1234", "% 5d", " 1234"},
365 {"1234", "%+5d", "+1234"},
366 {"1234", "%-5d", "1234 "},
367 {"1234", "%x", "4d2"},
368 {"1234", "%X", "4D2"},
369 {"-1234", "%3x", "-4d2"},
370 {"-1234", "%4x", "-4d2"},
371 {"-1234", "%5x", " -4d2"},
372 {"-1234", "%-5x", "-4d2 "},
373 {"1234", "%03d", "1234"},
374 {"1234", "%04d", "1234"},
375 {"1234", "%05d", "01234"},
376 {"1234", "%06d", "001234"},
377 {"-1234", "%06d", "-01234"},
378 {"1234", "%+06d", "+01234"},
379 {"1234", "% 06d", " 01234"},
380 {"1234", "%-6d", "1234 "},
381 {"1234", "%-06d", "1234 "},
382 {"-1234", "%-06d", "-1234 "},
383
384 {"1234", "%.3d", "1234"},
385 {"1234", "%.4d", "1234"},
386 {"1234", "%.5d", "01234"},
387 {"1234", "%.6d", "001234"},
388 {"-1234", "%.3d", "-1234"},
389 {"-1234", "%.4d", "-1234"},
390 {"-1234", "%.5d", "-01234"},
391 {"-1234", "%.6d", "-001234"},
392
393 {"1234", "%8.3d", " 1234"},
394 {"1234", "%8.4d", " 1234"},
395 {"1234", "%8.5d", " 01234"},
396 {"1234", "%8.6d", " 001234"},
397 {"-1234", "%8.3d", " -1234"},
398 {"-1234", "%8.4d", " -1234"},
399 {"-1234", "%8.5d", " -01234"},
400 {"-1234", "%8.6d", " -001234"},
401
402 {"1234", "%+8.3d", " +1234"},
403 {"1234", "%+8.4d", " +1234"},
404 {"1234", "%+8.5d", " +01234"},
405 {"1234", "%+8.6d", " +001234"},
406 {"-1234", "%+8.3d", " -1234"},
407 {"-1234", "%+8.4d", " -1234"},
408 {"-1234", "%+8.5d", " -01234"},
409 {"-1234", "%+8.6d", " -001234"},
410
411 {"1234", "% 8.3d", " 1234"},
412 {"1234", "% 8.4d", " 1234"},
413 {"1234", "% 8.5d", " 01234"},
414 {"1234", "% 8.6d", " 001234"},
415 {"-1234", "% 8.3d", " -1234"},
416 {"-1234", "% 8.4d", " -1234"},
417 {"-1234", "% 8.5d", " -01234"},
418 {"-1234", "% 8.6d", " -001234"},
419
420 {"1234", "%.3x", "4d2"},
421 {"1234", "%.4x", "04d2"},
422 {"1234", "%.5x", "004d2"},
423 {"1234", "%.6x", "0004d2"},
424 {"-1234", "%.3x", "-4d2"},
425 {"-1234", "%.4x", "-04d2"},
426 {"-1234", "%.5x", "-004d2"},
427 {"-1234", "%.6x", "-0004d2"},
428
429 {"1234", "%8.3x", " 4d2"},
430 {"1234", "%8.4x", " 04d2"},
431 {"1234", "%8.5x", " 004d2"},
432 {"1234", "%8.6x", " 0004d2"},
433 {"-1234", "%8.3x", " -4d2"},
434 {"-1234", "%8.4x", " -04d2"},
435 {"-1234", "%8.5x", " -004d2"},
436 {"-1234", "%8.6x", " -0004d2"},
437
438 {"1234", "%+8.3x", " +4d2"},
439 {"1234", "%+8.4x", " +04d2"},
440 {"1234", "%+8.5x", " +004d2"},
441 {"1234", "%+8.6x", " +0004d2"},
442 {"-1234", "%+8.3x", " -4d2"},
443 {"-1234", "%+8.4x", " -04d2"},
444 {"-1234", "%+8.5x", " -004d2"},
445 {"-1234", "%+8.6x", " -0004d2"},
446
447 {"1234", "% 8.3x", " 4d2"},
448 {"1234", "% 8.4x", " 04d2"},
449 {"1234", "% 8.5x", " 004d2"},
450 {"1234", "% 8.6x", " 0004d2"},
451 {"1234", "% 8.7x", " 00004d2"},
452 {"1234", "% 8.8x", " 000004d2"},
453 {"-1234", "% 8.3x", " -4d2"},
454 {"-1234", "% 8.4x", " -04d2"},
455 {"-1234", "% 8.5x", " -004d2"},
456 {"-1234", "% 8.6x", " -0004d2"},
457 {"-1234", "% 8.7x", "-00004d2"},
458 {"-1234", "% 8.8x", "-000004d2"},
459
460 {"1234", "%-8.3d", "1234 "},
461 {"1234", "%-8.4d", "1234 "},
462 {"1234", "%-8.5d", "01234 "},
463 {"1234", "%-8.6d", "001234 "},
464 {"1234", "%-8.7d", "0001234 "},
465 {"1234", "%-8.8d", "00001234"},
466 {"-1234", "%-8.3d", "-1234 "},
467 {"-1234", "%-8.4d", "-1234 "},
468 {"-1234", "%-8.5d", "-01234 "},
469 {"-1234", "%-8.6d", "-001234 "},
470 {"-1234", "%-8.7d", "-0001234"},
471 {"-1234", "%-8.8d", "-00001234"},
472
473 {"16777215", "%b", "111111111111111111111111"},
474
475 {"0", "%.d", ""},
476 {"0", "%.0d", ""},
477 {"0", "%3.d", ""},
478 }
479
480 func TestFormat(t *testing.T) {
481 for i, test := range formatTests {
482 var x *Int
483 if test.input != "<nil>" {
484 var ok bool
485 x, ok = new(Int).SetString(test.input, 0)
486 if !ok {
487 t.Errorf("#%d failed reading input %s", i, test.input)
488 }
489 }
490 output := fmt.Sprintf(test.format, x)
491 if output != test.output {
492 t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output)
493 }
494 }
495 }
496
497 var scanTests = []struct {
498 input string
499 format string
500 output string
501 remaining int
502 }{
503 {"1010", "%b", "10", 0},
504 {"0b1010", "%v", "10", 0},
505 {"12", "%o", "10", 0},
506 {"012", "%v", "10", 0},
507 {"10", "%d", "10", 0},
508 {"10", "%v", "10", 0},
509 {"a", "%x", "10", 0},
510 {"0xa", "%v", "10", 0},
511 {"A", "%X", "10", 0},
512 {"-A", "%X", "-10", 0},
513 {"+0b1011001", "%v", "89", 0},
514 {"0xA", "%v", "10", 0},
515 {"0 ", "%v", "0", 1},
516 {"2+3", "%v", "2", 2},
517 {"0XABC 12", "%v", "2748", 3},
518 }
519
520 func TestScan(t *testing.T) {
521 var buf bytes.Buffer
522 for i, test := range scanTests {
523 x := new(Int)
524 buf.Reset()
525 buf.WriteString(test.input)
526 if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
527 t.Errorf("#%d error: %s", i, err.String())
528 }
529 if x.String() != test.output {
530 t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
531 }
532 if buf.Len() != test.remaining {
533 t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
534 }
535 }
536 }
537
538
539 var divisionSignsTests = []struct {
540 x, y int64
541 q, r int64
542 d, m int64
543 }{
544 {5, 3, 1, 2, 1, 2},
545 {-5, 3, -1, -2, -2, 1},
546 {5, -3, -1, 2, -1, 2},
547 {-5, -3, 1, -2, 2, 1},
548 {1, 2, 0, 1, 0, 1},
549 {8, 4, 2, 0, 2, 0},
550 }
551
552 func TestDivisionSigns(t *testing.T) {
553 for i, test := range divisionSignsTests {
554 x := NewInt(test.x)
555 y := NewInt(test.y)
556 q := NewInt(test.q)
557 r := NewInt(test.r)
558 d := NewInt(test.d)
559 m := NewInt(test.m)
560
561 q1 := new(Int).Quo(x, y)
562 r1 := new(Int).Rem(x, y)
563 if !isNormalized(q1) {
564 t.Errorf("#%d Quo: %v is not normalized", i, *q1)
565 }
566 if !isNormalized(r1) {
567 t.Errorf("#%d Rem: %v is not normalized", i, *r1)
568 }
569 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
570 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
571 }
572
573 q2, r2 := new(Int).QuoRem(x, y, new(Int))
574 if !isNormalized(q2) {
575 t.Errorf("#%d Quo: %v is not normalized", i, *q2)
576 }
577 if !isNormalized(r2) {
578 t.Errorf("#%d Rem: %v is not normalized", i, *r2)
579 }
580 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
581 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
582 }
583
584 d1 := new(Int).Div(x, y)
585 m1 := new(Int).Mod(x, y)
586 if !isNormalized(d1) {
587 t.Errorf("#%d Div: %v is not normalized", i, *d1)
588 }
589 if !isNormalized(m1) {
590 t.Errorf("#%d Mod: %v is not normalized", i, *m1)
591 }
592 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
593 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
594 }
595
596 d2, m2 := new(Int).DivMod(x, y, new(Int))
597 if !isNormalized(d2) {
598 t.Errorf("#%d Div: %v is not normalized", i, *d2)
599 }
600 if !isNormalized(m2) {
601 t.Errorf("#%d Mod: %v is not normalized", i, *m2)
602 }
603 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
604 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
605 }
606 }
607 }
608
609 func checkSetBytes(b []byte) bool {
610 hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
611 hex2 := hex.EncodeToString(b)
612
613 for len(hex1) < len(hex2) {
614 hex1 = "0" + hex1
615 }
616
617 for len(hex1) > len(hex2) {
618 hex2 = "0" + hex2
619 }
620
621 return hex1 == hex2
622 }
623
624 func TestSetBytes(t *testing.T) {
625 if err := quick.Check(checkSetBytes, nil); err != nil {
626 t.Error(err)
627 }
628 }
629
630 func checkBytes(b []byte) bool {
631 b2 := new(Int).SetBytes(b).Bytes()
632 return bytes.Compare(b, b2) == 0
633 }
634
635 func TestBytes(t *testing.T) {
636 if err := quick.Check(checkSetBytes, nil); err != nil {
637 t.Error(err)
638 }
639 }
640
641 func checkQuo(x, y []byte) bool {
642 u := new(Int).SetBytes(x)
643 v := new(Int).SetBytes(y)
644
645 if len(v.abs) == 0 {
646 return true
647 }
648
649 r := new(Int)
650 q, r := new(Int).QuoRem(u, v, r)
651
652 if r.Cmp(v) >= 0 {
653 return false
654 }
655
656 uprime := new(Int).Set(q)
657 uprime.Mul(uprime, v)
658 uprime.Add(uprime, r)
659
660 return uprime.Cmp(u) == 0
661 }
662
663 var quoTests = []struct {
664 x, y string
665 q, r string
666 }{
667 {
668 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
669 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
670 "50911",
671 "1",
672 },
673 {
674 "11510768301994997771168",
675 "1328165573307167369775",
676 "8",
677 "885443715537658812968",
678 },
679 }
680
681 func TestQuo(t *testing.T) {
682 if err := quick.Check(checkQuo, nil); err != nil {
683 t.Error(err)
684 }
685
686 for i, test := range quoTests {
687 x, _ := new(Int).SetString(test.x, 10)
688 y, _ := new(Int).SetString(test.y, 10)
689 expectedQ, _ := new(Int).SetString(test.q, 10)
690 expectedR, _ := new(Int).SetString(test.r, 10)
691
692 r := new(Int)
693 q, r := new(Int).QuoRem(x, y, r)
694
695 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
696 t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
697 }
698 }
699 }
700
701 func TestQuoStepD6(t *testing.T) {
702
703
704
705 u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
706 v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
707
708 r := new(Int)
709 q, r := new(Int).QuoRem(u, v, r)
710 const expectedQ64 = "18446744073709551613"
711 const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
712 const expectedQ32 = "4294967293"
713 const expectedR32 = "39614081266355540837921718287"
714 if q.String() != expectedQ64 && q.String() != expectedQ32 ||
715 r.String() != expectedR64 && r.String() != expectedR32 {
716 t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
717 }
718 }
719
720 var bitLenTests = []struct {
721 in string
722 out int
723 }{
724 {"-1", 1},
725 {"0", 0},
726 {"1", 1},
727 {"2", 2},
728 {"4", 3},
729 {"0xabc", 12},
730 {"0x8000", 16},
731 {"0x80000000", 32},
732 {"0x800000000000", 48},
733 {"0x8000000000000000", 64},
734 {"0x80000000000000000000", 80},
735 {"-0x4000000000000000000000", 87},
736 }
737
738 func TestBitLen(t *testing.T) {
739 for i, test := range bitLenTests {
740 x, ok := new(Int).SetString(test.in, 0)
741 if !ok {
742 t.Errorf("#%d test input invalid: %s", i, test.in)
743 continue
744 }
745
746 if n := x.BitLen(); n != test.out {
747 t.Errorf("#%d got %d want %d", i, n, test.out)
748 }
749 }
750 }
751
752 var expTests = []struct {
753 x, y, m string
754 out string
755 }{
756 {"5", "0", "", "1"},
757 {"-5", "0", "", "-1"},
758 {"5", "1", "", "5"},
759 {"-5", "1", "", "-5"},
760 {"-2", "3", "2", "0"},
761 {"5", "2", "", "25"},
762 {"1", "65537", "2", "1"},
763 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
764 {"0x8000000000000000", "2", "6719", "4944"},
765 {"0x8000000000000000", "3", "6719", "5447"},
766 {"0x8000000000000000", "1000", "6719", "1603"},
767 {"0x8000000000000000", "1000000", "6719", "3199"},
768 {
769 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
770 "298472983472983471903246121093472394872319615612417471234712061",
771 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
772 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
773 },
774 }
775
776 func TestExp(t *testing.T) {
777 for i, test := range expTests {
778 x, ok1 := new(Int).SetString(test.x, 0)
779 y, ok2 := new(Int).SetString(test.y, 0)
780 out, ok3 := new(Int).SetString(test.out, 0)
781
782 var ok4 bool
783 var m *Int
784
785 if len(test.m) == 0 {
786 m, ok4 = nil, true
787 } else {
788 m, ok4 = new(Int).SetString(test.m, 0)
789 }
790
791 if !ok1 || !ok2 || !ok3 || !ok4 {
792 t.Errorf("#%d: error in input", i)
793 continue
794 }
795
796 z := y.Exp(x, y, m)
797 if !isNormalized(z) {
798 t.Errorf("#%d: %v is not normalized", i, *z)
799 }
800 if z.Cmp(out) != 0 {
801 t.Errorf("#%d: got %s want %s", i, z, out)
802 }
803 }
804 }
805
806 func checkGcd(aBytes, bBytes []byte) bool {
807 a := new(Int).SetBytes(aBytes)
808 b := new(Int).SetBytes(bBytes)
809
810 x := new(Int)
811 y := new(Int)
812 d := new(Int)
813
814 GcdInt(d, x, y, a, b)
815 x.Mul(x, a)
816 y.Mul(y, b)
817 x.Add(x, y)
818
819 return x.Cmp(d) == 0
820 }
821
822 var gcdTests = []struct {
823 a, b int64
824 d, x, y int64
825 }{
826 {120, 23, 1, -9, 47},
827 }
828
829 func TestGcd(t *testing.T) {
830 for i, test := range gcdTests {
831 a := NewInt(test.a)
832 b := NewInt(test.b)
833
834 x := new(Int)
835 y := new(Int)
836 d := new(Int)
837
838 expectedX := NewInt(test.x)
839 expectedY := NewInt(test.y)
840 expectedD := NewInt(test.d)
841
842 GcdInt(d, x, y, a, b)
843
844 if expectedX.Cmp(x) != 0 ||
845 expectedY.Cmp(y) != 0 ||
846 expectedD.Cmp(d) != 0 {
847 t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
848 }
849 }
850
851 quick.Check(checkGcd, nil)
852 }
853
854 var primes = []string{
855 "2",
856 "3",
857 "5",
858 "7",
859 "11",
860
861 "13756265695458089029",
862 "13496181268022124907",
863 "10953742525620032441",
864 "17908251027575790097",
865
866
867 "18699199384836356663",
868
869 "98920366548084643601728869055592650835572950932266967461790948584315647051443",
870 "94560208308847015747498523884063394671606671904944666360068158221458669711639",
871
872
873 "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
874 "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
875 "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
876 "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
877 }
878
879 var composites = []string{
880 "21284175091214687912771199898307297748211672914763848041968395774954376176754",
881 "6084766654921918907427900243509372380954290099172559290432744450051395395951",
882 "84594350493221918389213352992032324280367711247940675652888030554255915464401",
883 "82793403787388584738507275144194252681",
884 }
885
886 func TestProbablyPrime(t *testing.T) {
887 nreps := 20
888 if testing.Short() {
889 nreps = 1
890 }
891 for i, s := range primes {
892 p, _ := new(Int).SetString(s, 10)
893 if !ProbablyPrime(p, nreps) {
894 t.Errorf("#%d prime found to be non-prime (%s)", i, s)
895 }
896 }
897
898 for i, s := range composites {
899 c, _ := new(Int).SetString(s, 10)
900 if ProbablyPrime(c, nreps) {
901 t.Errorf("#%d composite found to be prime (%s)", i, s)
902 }
903 if testing.Short() {
904 break
905 }
906 }
907 }
908
909 type intShiftTest struct {
910 in string
911 shift uint
912 out string
913 }
914
915 var rshTests = []intShiftTest{
916 {"0", 0, "0"},
917 {"-0", 0, "0"},
918 {"0", 1, "0"},
919 {"0", 2, "0"},
920 {"1", 0, "1"},
921 {"1", 1, "0"},
922 {"1", 2, "0"},
923 {"2", 0, "2"},
924 {"2", 1, "1"},
925 {"-1", 0, "-1"},
926 {"-1", 1, "-1"},
927 {"-1", 10, "-1"},
928 {"-100", 2, "-25"},
929 {"-100", 3, "-13"},
930 {"-100", 100, "-1"},
931 {"4294967296", 0, "4294967296"},
932 {"4294967296", 1, "2147483648"},
933 {"4294967296", 2, "1073741824"},
934 {"18446744073709551616", 0, "18446744073709551616"},
935 {"18446744073709551616", 1, "9223372036854775808"},
936 {"18446744073709551616", 2, "4611686018427387904"},
937 {"18446744073709551616", 64, "1"},
938 {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
939 {"340282366920938463463374607431768211456", 128, "1"},
940 }
941
942 func TestRsh(t *testing.T) {
943 for i, test := range rshTests {
944 in, _ := new(Int).SetString(test.in, 10)
945 expected, _ := new(Int).SetString(test.out, 10)
946 out := new(Int).Rsh(in, test.shift)
947
948 if !isNormalized(out) {
949 t.Errorf("#%d: %v is not normalized", i, *out)
950 }
951 if out.Cmp(expected) != 0 {
952 t.Errorf("#%d: got %s want %s", i, out, expected)
953 }
954 }
955 }
956
957 func TestRshSelf(t *testing.T) {
958 for i, test := range rshTests {
959 z, _ := new(Int).SetString(test.in, 10)
960 expected, _ := new(Int).SetString(test.out, 10)
961 z.Rsh(z, test.shift)
962
963 if !isNormalized(z) {
964 t.Errorf("#%d: %v is not normalized", i, *z)
965 }
966 if z.Cmp(expected) != 0 {
967 t.Errorf("#%d: got %s want %s", i, z, expected)
968 }
969 }
970 }
971
972 var lshTests = []intShiftTest{
973 {"0", 0, "0"},
974 {"0", 1, "0"},
975 {"0", 2, "0"},
976 {"1", 0, "1"},
977 {"1", 1, "2"},
978 {"1", 2, "4"},
979 {"2", 0, "2"},
980 {"2", 1, "4"},
981 {"2", 2, "8"},
982 {"-87", 1, "-174"},
983 {"4294967296", 0, "4294967296"},
984 {"4294967296", 1, "8589934592"},
985 {"4294967296", 2, "17179869184"},
986 {"18446744073709551616", 0, "18446744073709551616"},
987 {"9223372036854775808", 1, "18446744073709551616"},
988 {"4611686018427387904", 2, "18446744073709551616"},
989 {"1", 64, "18446744073709551616"},
990 {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
991 {"1", 128, "340282366920938463463374607431768211456"},
992 }
993
994 func TestLsh(t *testing.T) {
995 for i, test := range lshTests {
996 in, _ := new(Int).SetString(test.in, 10)
997 expected, _ := new(Int).SetString(test.out, 10)
998 out := new(Int).Lsh(in, test.shift)
999
1000 if !isNormalized(out) {
1001 t.Errorf("#%d: %v is not normalized", i, *out)
1002 }
1003 if out.Cmp(expected) != 0 {
1004 t.Errorf("#%d: got %s want %s", i, out, expected)
1005 }
1006 }
1007 }
1008
1009 func TestLshSelf(t *testing.T) {
1010 for i, test := range lshTests {
1011 z, _ := new(Int).SetString(test.in, 10)
1012 expected, _ := new(Int).SetString(test.out, 10)
1013 z.Lsh(z, test.shift)
1014
1015 if !isNormalized(z) {
1016 t.Errorf("#%d: %v is not normalized", i, *z)
1017 }
1018 if z.Cmp(expected) != 0 {
1019 t.Errorf("#%d: got %s want %s", i, z, expected)
1020 }
1021 }
1022 }
1023
1024 func TestLshRsh(t *testing.T) {
1025 for i, test := range rshTests {
1026 in, _ := new(Int).SetString(test.in, 10)
1027 out := new(Int).Lsh(in, test.shift)
1028 out = out.Rsh(out, test.shift)
1029
1030 if !isNormalized(out) {
1031 t.Errorf("#%d: %v is not normalized", i, *out)
1032 }
1033 if in.Cmp(out) != 0 {
1034 t.Errorf("#%d: got %s want %s", i, out, in)
1035 }
1036 }
1037 for i, test := range lshTests {
1038 in, _ := new(Int).SetString(test.in, 10)
1039 out := new(Int).Lsh(in, test.shift)
1040 out.Rsh(out, test.shift)
1041
1042 if !isNormalized(out) {
1043 t.Errorf("#%d: %v is not normalized", i, *out)
1044 }
1045 if in.Cmp(out) != 0 {
1046 t.Errorf("#%d: got %s want %s", i, out, in)
1047 }
1048 }
1049 }
1050
1051 var int64Tests = []int64{
1052 0,
1053 1,
1054 -1,
1055 4294967295,
1056 -4294967295,
1057 4294967296,
1058 -4294967296,
1059 9223372036854775807,
1060 -9223372036854775807,
1061 -9223372036854775808,
1062 }
1063
1064 func TestInt64(t *testing.T) {
1065 for i, testVal := range int64Tests {
1066 in := NewInt(testVal)
1067 out := in.Int64()
1068
1069 if out != testVal {
1070 t.Errorf("#%d got %d want %d", i, out, testVal)
1071 }
1072 }
1073 }
1074
1075 var bitwiseTests = []struct {
1076 x, y string
1077 and, or, xor, andNot string
1078 }{
1079 {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1080 {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1081 {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1082 {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1083 {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1084 {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1085 {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1086 {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1087 {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1088 {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1089 {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1090 {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1091 {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1092 {
1093 "0x1000009dc6e3d9822cba04129bcbe3401",
1094 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1095 "0x1000001186210100001000009048c2001",
1096 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1097 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1098 "0x8c40c2d8822caa04120b8321400",
1099 },
1100 {
1101 "0x1000009dc6e3d9822cba04129bcbe3401",
1102 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1103 "0x8c40c2d8822caa04120b8321401",
1104 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1105 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1106 "0x1000001186210100001000009048c2000",
1107 },
1108 {
1109 "-0x1000009dc6e3d9822cba04129bcbe3401",
1110 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1111 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1112 "-0x1000001186210100001000009048c2001",
1113 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1114 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1115 },
1116 }
1117
1118 type bitFun func(z, x, y *Int) *Int
1119
1120 func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1121 expected := new(Int)
1122 expected.SetString(exp, 0)
1123
1124 out := f(new(Int), x, y)
1125 if out.Cmp(expected) != 0 {
1126 t.Errorf("%s: got %s want %s", msg, out, expected)
1127 }
1128 }
1129
1130 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
1131 self := new(Int)
1132 self.Set(x)
1133 expected := new(Int)
1134 expected.SetString(exp, 0)
1135
1136 self = f(self, self, y)
1137 if self.Cmp(expected) != 0 {
1138 t.Errorf("%s: got %s want %s", msg, self, expected)
1139 }
1140 }
1141
1142 func altBit(x *Int, i int) uint {
1143 z := new(Int).Rsh(x, uint(i))
1144 z = z.And(z, NewInt(1))
1145 if z.Cmp(new(Int)) != 0 {
1146 return 1
1147 }
1148 return 0
1149 }
1150
1151 func altSetBit(z *Int, x *Int, i int, b uint) *Int {
1152 one := NewInt(1)
1153 m := one.Lsh(one, uint(i))
1154 switch b {
1155 case 1:
1156 return z.Or(x, m)
1157 case 0:
1158 return z.AndNot(x, m)
1159 }
1160 panic("set bit is not 0 or 1")
1161 }
1162
1163 func testBitset(t *testing.T, x *Int) {
1164 n := x.BitLen()
1165 z := new(Int).Set(x)
1166 z1 := new(Int).Set(x)
1167 for i := 0; i < n+10; i++ {
1168 old := z.Bit(i)
1169 old1 := altBit(z1, i)
1170 if old != old1 {
1171 t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1172 }
1173 z := new(Int).SetBit(z, i, 1)
1174 z1 := altSetBit(new(Int), z1, i, 1)
1175 if z.Bit(i) == 0 {
1176 t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1177 }
1178 if z.Cmp(z1) != 0 {
1179 t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1180 }
1181 z.SetBit(z, i, 0)
1182 altSetBit(z1, z1, i, 0)
1183 if z.Bit(i) != 0 {
1184 t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1185 }
1186 if z.Cmp(z1) != 0 {
1187 t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1188 }
1189 altSetBit(z1, z1, i, old)
1190 z.SetBit(z, i, old)
1191 if z.Cmp(z1) != 0 {
1192 t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1193 }
1194 }
1195 if z.Cmp(x) != 0 {
1196 t.Errorf("bitset: got %s want %s", z, x)
1197 }
1198 }
1199
1200 var bitsetTests = []struct {
1201 x string
1202 i int
1203 b uint
1204 }{
1205 {"0", 0, 0},
1206 {"0", 200, 0},
1207 {"1", 0, 1},
1208 {"1", 1, 0},
1209 {"-1", 0, 1},
1210 {"-1", 200, 1},
1211 {"0x2000000000000000000000000000", 108, 0},
1212 {"0x2000000000000000000000000000", 109, 1},
1213 {"0x2000000000000000000000000000", 110, 0},
1214 {"-0x2000000000000000000000000001", 108, 1},
1215 {"-0x2000000000000000000000000001", 109, 0},
1216 {"-0x2000000000000000000000000001", 110, 1},
1217 }
1218
1219 func TestBitSet(t *testing.T) {
1220 for _, test := range bitwiseTests {
1221 x := new(Int)
1222 x.SetString(test.x, 0)
1223 testBitset(t, x)
1224 x = new(Int)
1225 x.SetString(test.y, 0)
1226 testBitset(t, x)
1227 }
1228 for i, test := range bitsetTests {
1229 x := new(Int)
1230 x.SetString(test.x, 0)
1231 b := x.Bit(test.i)
1232 if b != test.b {
1233
1234 t.Errorf("#%d want %v got %v", i, test.b, b)
1235 }
1236 }
1237 }
1238
1239 func BenchmarkBitset(b *testing.B) {
1240 z := new(Int)
1241 z.SetBit(z, 512, 1)
1242 b.ResetTimer()
1243 b.StartTimer()
1244 for i := b.N - 1; i >= 0; i-- {
1245 z.SetBit(z, i&512, 1)
1246 }
1247 }
1248
1249 func BenchmarkBitsetNeg(b *testing.B) {
1250 z := NewInt(-1)
1251 z.SetBit(z, 512, 0)
1252 b.ResetTimer()
1253 b.StartTimer()
1254 for i := b.N - 1; i >= 0; i-- {
1255 z.SetBit(z, i&512, 0)
1256 }
1257 }
1258
1259 func BenchmarkBitsetOrig(b *testing.B) {
1260 z := new(Int)
1261 altSetBit(z, z, 512, 1)
1262 b.ResetTimer()
1263 b.StartTimer()
1264 for i := b.N - 1; i >= 0; i-- {
1265 altSetBit(z, z, i&512, 1)
1266 }
1267 }
1268
1269 func BenchmarkBitsetNegOrig(b *testing.B) {
1270 z := NewInt(-1)
1271 altSetBit(z, z, 512, 0)
1272 b.ResetTimer()
1273 b.StartTimer()
1274 for i := b.N - 1; i >= 0; i-- {
1275 altSetBit(z, z, i&512, 0)
1276 }
1277 }
1278
1279 func TestBitwise(t *testing.T) {
1280 x := new(Int)
1281 y := new(Int)
1282 for _, test := range bitwiseTests {
1283 x.SetString(test.x, 0)
1284 y.SetString(test.y, 0)
1285
1286 testBitFun(t, "and", (*Int).And, x, y, test.and)
1287 testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
1288 testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1289 testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
1290 testBitFun(t, "or", (*Int).Or, x, y, test.or)
1291 testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
1292 testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
1293 testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
1294 }
1295 }
1296
1297 var notTests = []struct {
1298 in string
1299 out string
1300 }{
1301 {"0", "-1"},
1302 {"1", "-2"},
1303 {"7", "-8"},
1304 {"0", "-1"},
1305 {"-81910", "81909"},
1306 {
1307 "298472983472983471903246121093472394872319615612417471234712061",
1308 "-298472983472983471903246121093472394872319615612417471234712062",
1309 },
1310 }
1311
1312 func TestNot(t *testing.T) {
1313 in := new(Int)
1314 out := new(Int)
1315 expected := new(Int)
1316 for i, test := range notTests {
1317 in.SetString(test.in, 10)
1318 expected.SetString(test.out, 10)
1319 out = out.Not(in)
1320 if out.Cmp(expected) != 0 {
1321 t.Errorf("#%d: got %s want %s", i, out, expected)
1322 }
1323 out = out.Not(out)
1324 if out.Cmp(in) != 0 {
1325 t.Errorf("#%d: got %s want %s", i, out, in)
1326 }
1327 }
1328 }
1329
1330 var modInverseTests = []struct {
1331 element string
1332 prime string
1333 }{
1334 {"1", "7"},
1335 {"1", "13"},
1336 {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1337 }
1338
1339 func TestModInverse(t *testing.T) {
1340 var element, prime Int
1341 one := NewInt(1)
1342 for i, test := range modInverseTests {
1343 (&element).SetString(test.element, 10)
1344 (&prime).SetString(test.prime, 10)
1345 inverse := new(Int).ModInverse(&element, &prime)
1346 inverse.Mul(inverse, &element)
1347 inverse.Mod(inverse, &prime)
1348 if inverse.Cmp(one) != 0 {
1349 t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
1350 }
1351 }
1352 }
1353
1354
1355 var gobEncodingTests = []string{
1356 "0",
1357 "1",
1358 "2",
1359 "10",
1360 "42",
1361 "1234567890",
1362 "298472983472983471903246121093472394872319615612417471234712061",
1363 }
1364
1365 func TestIntGobEncoding(t *testing.T) {
1366 var medium bytes.Buffer
1367 enc := gob.NewEncoder(&medium)
1368 dec := gob.NewDecoder(&medium)
1369 for i, test := range gobEncodingTests {
1370 for j := 0; j < 2; j++ {
1371 medium.Reset()
1372 stest := test
1373 if j != 0 {
1374
1375 stest = "-" + test
1376 }
1377 var tx Int
1378 tx.SetString(stest, 10)
1379 if err := enc.Encode(&tx); err != nil {
1380 t.Errorf("#%d%c: encoding failed: %s", i, 'a'+j, err)
1381 }
1382 var rx Int
1383 if err := dec.Decode(&rx); err != nil {
1384 t.Errorf("#%d%c: decoding failed: %s", i, 'a'+j, err)
1385 }
1386 if rx.Cmp(&tx) != 0 {
1387 t.Errorf("#%d%c: transmission failed: got %s want %s", i, 'a'+j, &rx, &tx)
1388 }
1389 }
1390 }
1391 }