Source file
src/math/big/nat.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14 package big
15
16 import (
17 "encoding/binary"
18 "math/bits"
19 "math/rand"
20 "sync"
21 )
22
23
24
25
26
27
28
29
30
31
32
33
34 type nat []Word
35
36 var (
37 natOne = nat{1}
38 natTwo = nat{2}
39 natFive = nat{5}
40 natTen = nat{10}
41 )
42
43 func (z nat) clear() {
44 for i := range z {
45 z[i] = 0
46 }
47 }
48
49 func (z nat) norm() nat {
50 i := len(z)
51 for i > 0 && z[i-1] == 0 {
52 i--
53 }
54 return z[0:i]
55 }
56
57 func (z nat) make(n int) nat {
58 if n <= cap(z) {
59 return z[:n]
60 }
61 if n == 1 {
62
63 return make(nat, 1)
64 }
65
66
67 const e = 4
68 return make(nat, n, n+e)
69 }
70
71 func (z nat) setWord(x Word) nat {
72 if x == 0 {
73 return z[:0]
74 }
75 z = z.make(1)
76 z[0] = x
77 return z
78 }
79
80 func (z nat) setUint64(x uint64) nat {
81
82 if w := Word(x); uint64(w) == x {
83 return z.setWord(w)
84 }
85
86 z = z.make(2)
87 z[1] = Word(x >> 32)
88 z[0] = Word(x)
89 return z
90 }
91
92 func (z nat) set(x nat) nat {
93 z = z.make(len(x))
94 copy(z, x)
95 return z
96 }
97
98 func (z nat) add(x, y nat) nat {
99 m := len(x)
100 n := len(y)
101
102 switch {
103 case m < n:
104 return z.add(y, x)
105 case m == 0:
106
107 return z[:0]
108 case n == 0:
109
110 return z.set(x)
111 }
112
113
114 z = z.make(m + 1)
115 c := addVV(z[0:n], x, y)
116 if m > n {
117 c = addVW(z[n:m], x[n:], c)
118 }
119 z[m] = c
120
121 return z.norm()
122 }
123
124 func (z nat) sub(x, y nat) nat {
125 m := len(x)
126 n := len(y)
127
128 switch {
129 case m < n:
130 panic("underflow")
131 case m == 0:
132
133 return z[:0]
134 case n == 0:
135
136 return z.set(x)
137 }
138
139
140 z = z.make(m)
141 c := subVV(z[0:n], x, y)
142 if m > n {
143 c = subVW(z[n:], x[n:], c)
144 }
145 if c != 0 {
146 panic("underflow")
147 }
148
149 return z.norm()
150 }
151
152 func (x nat) cmp(y nat) (r int) {
153 m := len(x)
154 n := len(y)
155 if m != n || m == 0 {
156 switch {
157 case m < n:
158 r = -1
159 case m > n:
160 r = 1
161 }
162 return
163 }
164
165 i := m - 1
166 for i > 0 && x[i] == y[i] {
167 i--
168 }
169
170 switch {
171 case x[i] < y[i]:
172 r = -1
173 case x[i] > y[i]:
174 r = 1
175 }
176 return
177 }
178
179 func (z nat) mulAddWW(x nat, y, r Word) nat {
180 m := len(x)
181 if m == 0 || y == 0 {
182 return z.setWord(r)
183 }
184
185
186 z = z.make(m + 1)
187 z[m] = mulAddVWW(z[0:m], x, y, r)
188
189 return z.norm()
190 }
191
192
193
194 func basicMul(z, x, y nat) {
195 z[0 : len(x)+len(y)].clear()
196 for i, d := range y {
197 if d != 0 {
198 z[len(x)+i] = addMulVVW(z[i:i+len(x)], x, d)
199 }
200 }
201 }
202
203
204
205
206
207
208
209
210
211
212 func (z nat) montgomery(x, y, m nat, k Word, n int) nat {
213
214
215
216
217 if len(x) != n || len(y) != n || len(m) != n {
218 panic("math/big: mismatched montgomery number lengths")
219 }
220 z = z.make(n * 2)
221 z.clear()
222 var c Word
223 for i := 0; i < n; i++ {
224 d := y[i]
225 c2 := addMulVVW(z[i:n+i], x, d)
226 t := z[i] * k
227 c3 := addMulVVW(z[i:n+i], m, t)
228 cx := c + c2
229 cy := cx + c3
230 z[n+i] = cy
231 if cx < c2 || cy < c3 {
232 c = 1
233 } else {
234 c = 0
235 }
236 }
237 if c != 0 {
238 subVV(z[:n], z[n:], m)
239 } else {
240 copy(z[:n], z[n:])
241 }
242 return z[:n]
243 }
244
245
246
247 func karatsubaAdd(z, x nat, n int) {
248 if c := addVV(z[0:n], z, x); c != 0 {
249 addVW(z[n:n+n>>1], z[n:], c)
250 }
251 }
252
253
254 func karatsubaSub(z, x nat, n int) {
255 if c := subVV(z[0:n], z, x); c != 0 {
256 subVW(z[n:n+n>>1], z[n:], c)
257 }
258 }
259
260
261
262
263 var karatsubaThreshold = 40
264
265
266
267
268
269 func karatsuba(z, x, y nat) {
270 n := len(y)
271
272
273
274
275 if n&1 != 0 || n < karatsubaThreshold || n < 2 {
276 basicMul(z, x, y)
277 return
278 }
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305 n2 := n >> 1
306 x1, x0 := x[n2:], x[0:n2]
307 y1, y0 := y[n2:], y[0:n2]
308
309
310
311
312
313
314
315
316
317
318
319 karatsuba(z, x0, y0)
320 karatsuba(z[n:], x1, y1)
321
322
323 s := 1
324 xd := z[2*n : 2*n+n2]
325 if subVV(xd, x1, x0) != 0 {
326 s = -s
327 subVV(xd, x0, x1)
328 }
329
330
331 yd := z[2*n+n2 : 3*n]
332 if subVV(yd, y0, y1) != 0 {
333 s = -s
334 subVV(yd, y1, y0)
335 }
336
337
338
339 p := z[n*3:]
340 karatsuba(p, xd, yd)
341
342
343
344 r := z[n*4:]
345 copy(r, z[:n*2])
346
347
348
349
350
351
352
353
354
355 karatsubaAdd(z[n2:], r, n)
356 karatsubaAdd(z[n2:], r[n:], n)
357 if s > 0 {
358 karatsubaAdd(z[n2:], p, n)
359 } else {
360 karatsubaSub(z[n2:], p, n)
361 }
362 }
363
364
365
366
367
368
369
370 func alias(x, y nat) bool {
371 return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
372 }
373
374
375
376
377 func addAt(z, x nat, i int) {
378 if n := len(x); n > 0 {
379 if c := addVV(z[i:i+n], z[i:], x); c != 0 {
380 j := i + n
381 if j < len(z) {
382 addVW(z[j:], z[j:], c)
383 }
384 }
385 }
386 }
387
388 func max(x, y int) int {
389 if x > y {
390 return x
391 }
392 return y
393 }
394
395
396
397
398
399 func karatsubaLen(n, threshold int) int {
400 i := uint(0)
401 for n > threshold {
402 n >>= 1
403 i++
404 }
405 return n << i
406 }
407
408 func (z nat) mul(x, y nat) nat {
409 m := len(x)
410 n := len(y)
411
412 switch {
413 case m < n:
414 return z.mul(y, x)
415 case m == 0 || n == 0:
416 return z[:0]
417 case n == 1:
418 return z.mulAddWW(x, y[0], 0)
419 }
420
421
422
423 if alias(z, x) || alias(z, y) {
424 z = nil
425 }
426
427
428 if n < karatsubaThreshold {
429 z = z.make(m + n)
430 basicMul(z, x, y)
431 return z.norm()
432 }
433
434
435
436
437
438
439
440
441 k := karatsubaLen(n, karatsubaThreshold)
442
443
444
445 x0 := x[0:k]
446 y0 := y[0:k]
447 z = z.make(max(6*k, m+n))
448 karatsuba(z, x0, y0)
449 z = z[0 : m+n]
450 z[2*k:].clear()
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465 if k < n || m != n {
466 tp := getNat(3 * k)
467 t := *tp
468
469
470 x0 := x0.norm()
471 y1 := y[k:]
472 t = t.mul(x0, y1)
473 addAt(z, t, k)
474
475
476 y0 := y0.norm()
477 for i := k; i < len(x); i += k {
478 xi := x[i:]
479 if len(xi) > k {
480 xi = xi[:k]
481 }
482 xi = xi.norm()
483 t = t.mul(xi, y0)
484 addAt(z, t, i)
485 t = t.mul(xi, y1)
486 addAt(z, t, i+k)
487 }
488
489 putNat(tp)
490 }
491
492 return z.norm()
493 }
494
495
496
497
498
499 func basicSqr(z, x nat) {
500 n := len(x)
501 tp := getNat(2 * n)
502 t := *tp
503 t.clear()
504 z[1], z[0] = mulWW(x[0], x[0])
505 for i := 1; i < n; i++ {
506 d := x[i]
507
508 z[2*i+1], z[2*i] = mulWW(d, d)
509
510 t[2*i] = addMulVVW(t[i:2*i], x[0:i], d)
511 }
512 t[2*n-1] = shlVU(t[1:2*n-1], t[1:2*n-1], 1)
513 addVV(z, z, t)
514 putNat(tp)
515 }
516
517
518
519
520
521
522 func karatsubaSqr(z, x nat) {
523 n := len(x)
524
525 if n&1 != 0 || n < karatsubaSqrThreshold || n < 2 {
526 basicSqr(z[:2*n], x)
527 return
528 }
529
530 n2 := n >> 1
531 x1, x0 := x[n2:], x[0:n2]
532
533 karatsubaSqr(z, x0)
534 karatsubaSqr(z[n:], x1)
535
536
537 xd := z[2*n : 2*n+n2]
538 if subVV(xd, x1, x0) != 0 {
539 subVV(xd, x0, x1)
540 }
541
542 p := z[n*3:]
543 karatsubaSqr(p, xd)
544
545 r := z[n*4:]
546 copy(r, z[:n*2])
547
548 karatsubaAdd(z[n2:], r, n)
549 karatsubaAdd(z[n2:], r[n:], n)
550 karatsubaSub(z[n2:], p, n)
551 }
552
553
554
555
556 var basicSqrThreshold = 20
557 var karatsubaSqrThreshold = 260
558
559
560 func (z nat) sqr(x nat) nat {
561 n := len(x)
562 switch {
563 case n == 0:
564 return z[:0]
565 case n == 1:
566 d := x[0]
567 z = z.make(2)
568 z[1], z[0] = mulWW(d, d)
569 return z.norm()
570 }
571
572 if alias(z, x) {
573 z = nil
574 }
575
576 if n < basicSqrThreshold {
577 z = z.make(2 * n)
578 basicMul(z, x, x)
579 return z.norm()
580 }
581 if n < karatsubaSqrThreshold {
582 z = z.make(2 * n)
583 basicSqr(z, x)
584 return z.norm()
585 }
586
587
588
589
590
591
592 k := karatsubaLen(n, karatsubaSqrThreshold)
593
594 x0 := x[0:k]
595 z = z.make(max(6*k, 2*n))
596 karatsubaSqr(z, x0)
597 z = z[0 : 2*n]
598 z[2*k:].clear()
599
600 if k < n {
601 tp := getNat(2 * k)
602 t := *tp
603 x0 := x0.norm()
604 x1 := x[k:]
605 t = t.mul(x0, x1)
606 addAt(z, t, k)
607 addAt(z, t, k)
608 t = t.sqr(x1)
609 addAt(z, t, 2*k)
610 putNat(tp)
611 }
612
613 return z.norm()
614 }
615
616
617
618 func (z nat) mulRange(a, b uint64) nat {
619 switch {
620 case a == 0:
621
622 return z.setUint64(0)
623 case a > b:
624 return z.setUint64(1)
625 case a == b:
626 return z.setUint64(a)
627 case a+1 == b:
628 return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b))
629 }
630 m := (a + b) / 2
631 return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
632 }
633
634
635
636 func getNat(n int) *nat {
637 var z *nat
638 if v := natPool.Get(); v != nil {
639 z = v.(*nat)
640 }
641 if z == nil {
642 z = new(nat)
643 }
644 *z = z.make(n)
645 return z
646 }
647
648 func putNat(x *nat) {
649 natPool.Put(x)
650 }
651
652 var natPool sync.Pool
653
654
655 func (x nat) bitLen() int {
656 if i := len(x) - 1; i >= 0 {
657 return i*_W + bits.Len(uint(x[i]))
658 }
659 return 0
660 }
661
662
663
664 func (x nat) trailingZeroBits() uint {
665 if len(x) == 0 {
666 return 0
667 }
668 var i uint
669 for x[i] == 0 {
670 i++
671 }
672
673 return i*_W + uint(bits.TrailingZeros(uint(x[i])))
674 }
675
676 func same(x, y nat) bool {
677 return len(x) == len(y) && len(x) > 0 && &x[0] == &y[0]
678 }
679
680
681 func (z nat) shl(x nat, s uint) nat {
682 if s == 0 {
683 if same(z, x) {
684 return z
685 }
686 if !alias(z, x) {
687 return z.set(x)
688 }
689 }
690
691 m := len(x)
692 if m == 0 {
693 return z[:0]
694 }
695
696
697 n := m + int(s/_W)
698 z = z.make(n + 1)
699 z[n] = shlVU(z[n-m:n], x, s%_W)
700 z[0 : n-m].clear()
701
702 return z.norm()
703 }
704
705
706 func (z nat) shr(x nat, s uint) nat {
707 if s == 0 {
708 if same(z, x) {
709 return z
710 }
711 if !alias(z, x) {
712 return z.set(x)
713 }
714 }
715
716 m := len(x)
717 n := m - int(s/_W)
718 if n <= 0 {
719 return z[:0]
720 }
721
722
723 z = z.make(n)
724 shrVU(z, x[m-n:], s%_W)
725
726 return z.norm()
727 }
728
729 func (z nat) setBit(x nat, i uint, b uint) nat {
730 j := int(i / _W)
731 m := Word(1) << (i % _W)
732 n := len(x)
733 switch b {
734 case 0:
735 z = z.make(n)
736 copy(z, x)
737 if j >= n {
738
739 return z
740 }
741 z[j] &^= m
742 return z.norm()
743 case 1:
744 if j >= n {
745 z = z.make(j + 1)
746 z[n:].clear()
747 } else {
748 z = z.make(n)
749 }
750 copy(z, x)
751 z[j] |= m
752
753 return z
754 }
755 panic("set bit is not 0 or 1")
756 }
757
758
759 func (x nat) bit(i uint) uint {
760 j := i / _W
761 if j >= uint(len(x)) {
762 return 0
763 }
764
765 return uint(x[j] >> (i % _W) & 1)
766 }
767
768
769
770 func (x nat) sticky(i uint) uint {
771 j := i / _W
772 if j >= uint(len(x)) {
773 if len(x) == 0 {
774 return 0
775 }
776 return 1
777 }
778
779 for _, x := range x[:j] {
780 if x != 0 {
781 return 1
782 }
783 }
784 if x[j]<<(_W-i%_W) != 0 {
785 return 1
786 }
787 return 0
788 }
789
790 func (z nat) and(x, y nat) nat {
791 m := len(x)
792 n := len(y)
793 if m > n {
794 m = n
795 }
796
797
798 z = z.make(m)
799 for i := 0; i < m; i++ {
800 z[i] = x[i] & y[i]
801 }
802
803 return z.norm()
804 }
805
806 func (z nat) andNot(x, y nat) nat {
807 m := len(x)
808 n := len(y)
809 if n > m {
810 n = m
811 }
812
813
814 z = z.make(m)
815 for i := 0; i < n; i++ {
816 z[i] = x[i] &^ y[i]
817 }
818 copy(z[n:m], x[n:m])
819
820 return z.norm()
821 }
822
823 func (z nat) or(x, y nat) nat {
824 m := len(x)
825 n := len(y)
826 s := x
827 if m < n {
828 n, m = m, n
829 s = y
830 }
831
832
833 z = z.make(m)
834 for i := 0; i < n; i++ {
835 z[i] = x[i] | y[i]
836 }
837 copy(z[n:m], s[n:m])
838
839 return z.norm()
840 }
841
842 func (z nat) xor(x, y nat) nat {
843 m := len(x)
844 n := len(y)
845 s := x
846 if m < n {
847 n, m = m, n
848 s = y
849 }
850
851
852 z = z.make(m)
853 for i := 0; i < n; i++ {
854 z[i] = x[i] ^ y[i]
855 }
856 copy(z[n:m], s[n:m])
857
858 return z.norm()
859 }
860
861
862
863 func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
864 if alias(z, limit) {
865 z = nil
866 }
867 z = z.make(len(limit))
868
869 bitLengthOfMSW := uint(n % _W)
870 if bitLengthOfMSW == 0 {
871 bitLengthOfMSW = _W
872 }
873 mask := Word((1 << bitLengthOfMSW) - 1)
874
875 for {
876 switch _W {
877 case 32:
878 for i := range z {
879 z[i] = Word(rand.Uint32())
880 }
881 case 64:
882 for i := range z {
883 z[i] = Word(rand.Uint32()) | Word(rand.Uint32())<<32
884 }
885 default:
886 panic("unknown word size")
887 }
888 z[len(limit)-1] &= mask
889 if z.cmp(limit) < 0 {
890 break
891 }
892 }
893
894 return z.norm()
895 }
896
897
898
899 func (z nat) expNN(x, y, m nat) nat {
900 if alias(z, x) || alias(z, y) {
901
902 z = nil
903 }
904
905
906 if len(m) == 1 && m[0] == 1 {
907 return z.setWord(0)
908 }
909
910
911
912 if len(y) == 0 {
913 return z.setWord(1)
914 }
915
916
917
918 if len(y) == 1 && y[0] == 1 && len(m) != 0 {
919 _, z = nat(nil).div(z, x, m)
920 return z
921 }
922
923
924 if len(m) != 0 {
925
926 z = z.make(len(m))
927 }
928 z = z.set(x)
929
930
931
932
933
934
935 if x.cmp(natOne) > 0 && len(y) > 1 && len(m) > 0 {
936 if m[0]&1 == 1 {
937 return z.expNNMontgomery(x, y, m)
938 }
939 return z.expNNWindowed(x, y, m)
940 }
941
942 v := y[len(y)-1]
943 shift := nlz(v) + 1
944 v <<= shift
945 var q nat
946
947 const mask = 1 << (_W - 1)
948
949
950
951
952
953 w := _W - int(shift)
954
955
956 var zz, r nat
957 for j := 0; j < w; j++ {
958 zz = zz.sqr(z)
959 zz, z = z, zz
960
961 if v&mask != 0 {
962 zz = zz.mul(z, x)
963 zz, z = z, zz
964 }
965
966 if len(m) != 0 {
967 zz, r = zz.div(r, z, m)
968 zz, r, q, z = q, z, zz, r
969 }
970
971 v <<= 1
972 }
973
974 for i := len(y) - 2; i >= 0; i-- {
975 v = y[i]
976
977 for j := 0; j < _W; j++ {
978 zz = zz.sqr(z)
979 zz, z = z, zz
980
981 if v&mask != 0 {
982 zz = zz.mul(z, x)
983 zz, z = z, zz
984 }
985
986 if len(m) != 0 {
987 zz, r = zz.div(r, z, m)
988 zz, r, q, z = q, z, zz, r
989 }
990
991 v <<= 1
992 }
993 }
994
995 return z.norm()
996 }
997
998
999 func (z nat) expNNWindowed(x, y, m nat) nat {
1000
1001
1002 var zz, r nat
1003
1004 const n = 4
1005
1006 var powers [1 << n]nat
1007 powers[0] = natOne
1008 powers[1] = x
1009 for i := 2; i < 1<<n; i += 2 {
1010 p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
1011 *p = p.sqr(*p2)
1012 zz, r = zz.div(r, *p, m)
1013 *p, r = r, *p
1014 *p1 = p1.mul(*p, x)
1015 zz, r = zz.div(r, *p1, m)
1016 *p1, r = r, *p1
1017 }
1018
1019 z = z.setWord(1)
1020
1021 for i := len(y) - 1; i >= 0; i-- {
1022 yi := y[i]
1023 for j := 0; j < _W; j += n {
1024 if i != len(y)-1 || j != 0 {
1025
1026
1027
1028 zz = zz.sqr(z)
1029 zz, z = z, zz
1030 zz, r = zz.div(r, z, m)
1031 z, r = r, z
1032
1033 zz = zz.sqr(z)
1034 zz, z = z, zz
1035 zz, r = zz.div(r, z, m)
1036 z, r = r, z
1037
1038 zz = zz.sqr(z)
1039 zz, z = z, zz
1040 zz, r = zz.div(r, z, m)
1041 z, r = r, z
1042
1043 zz = zz.sqr(z)
1044 zz, z = z, zz
1045 zz, r = zz.div(r, z, m)
1046 z, r = r, z
1047 }
1048
1049 zz = zz.mul(z, powers[yi>>(_W-n)])
1050 zz, z = z, zz
1051 zz, r = zz.div(r, z, m)
1052 z, r = r, z
1053
1054 yi <<= n
1055 }
1056 }
1057
1058 return z.norm()
1059 }
1060
1061
1062
1063 func (z nat) expNNMontgomery(x, y, m nat) nat {
1064 numWords := len(m)
1065
1066
1067
1068 if len(x) > numWords {
1069 _, x = nat(nil).div(nil, x, m)
1070
1071 }
1072 if len(x) < numWords {
1073 rr := make(nat, numWords)
1074 copy(rr, x)
1075 x = rr
1076 }
1077
1078
1079
1080
1081 k0 := 2 - m[0]
1082 t := m[0] - 1
1083 for i := 1; i < _W; i <<= 1 {
1084 t *= t
1085 k0 *= (t + 1)
1086 }
1087 k0 = -k0
1088
1089
1090 RR := nat(nil).setWord(1)
1091 zz := nat(nil).shl(RR, uint(2*numWords*_W))
1092 _, RR = nat(nil).div(RR, zz, m)
1093 if len(RR) < numWords {
1094 zz = zz.make(numWords)
1095 copy(zz, RR)
1096 RR = zz
1097 }
1098
1099 one := make(nat, numWords)
1100 one[0] = 1
1101
1102 const n = 4
1103
1104 var powers [1 << n]nat
1105 powers[0] = powers[0].montgomery(one, RR, m, k0, numWords)
1106 powers[1] = powers[1].montgomery(x, RR, m, k0, numWords)
1107 for i := 2; i < 1<<n; i++ {
1108 powers[i] = powers[i].montgomery(powers[i-1], powers[1], m, k0, numWords)
1109 }
1110
1111
1112 z = z.make(numWords)
1113 copy(z, powers[0])
1114
1115 zz = zz.make(numWords)
1116
1117
1118 for i := len(y) - 1; i >= 0; i-- {
1119 yi := y[i]
1120 for j := 0; j < _W; j += n {
1121 if i != len(y)-1 || j != 0 {
1122 zz = zz.montgomery(z, z, m, k0, numWords)
1123 z = z.montgomery(zz, zz, m, k0, numWords)
1124 zz = zz.montgomery(z, z, m, k0, numWords)
1125 z = z.montgomery(zz, zz, m, k0, numWords)
1126 }
1127 zz = zz.montgomery(z, powers[yi>>(_W-n)], m, k0, numWords)
1128 z, zz = zz, z
1129 yi <<= n
1130 }
1131 }
1132
1133 zz = zz.montgomery(z, one, m, k0, numWords)
1134
1135
1136
1137 if zz.cmp(m) >= 0 {
1138
1139
1140
1141
1142
1143
1144
1145 zz = zz.sub(zz, m)
1146 if zz.cmp(m) >= 0 {
1147 _, zz = nat(nil).div(nil, zz, m)
1148 }
1149 }
1150
1151 return zz.norm()
1152 }
1153
1154
1155
1156
1157
1158 func (z nat) bytes(buf []byte) (i int) {
1159 i = len(buf)
1160 for _, d := range z {
1161 for j := 0; j < _S; j++ {
1162 i--
1163 if i >= 0 {
1164 buf[i] = byte(d)
1165 } else if byte(d) != 0 {
1166 panic("math/big: buffer too small to fit value")
1167 }
1168 d >>= 8
1169 }
1170 }
1171
1172 if i < 0 {
1173 i = 0
1174 }
1175 for i < len(buf) && buf[i] == 0 {
1176 i++
1177 }
1178
1179 return
1180 }
1181
1182
1183 func bigEndianWord(buf []byte) Word {
1184 if _W == 64 {
1185 return Word(binary.BigEndian.Uint64(buf))
1186 }
1187 return Word(binary.BigEndian.Uint32(buf))
1188 }
1189
1190
1191
1192 func (z nat) setBytes(buf []byte) nat {
1193 z = z.make((len(buf) + _S - 1) / _S)
1194
1195 i := len(buf)
1196 for k := 0; i >= _S; k++ {
1197 z[k] = bigEndianWord(buf[i-_S : i])
1198 i -= _S
1199 }
1200 if i > 0 {
1201 var d Word
1202 for s := uint(0); i > 0; s += 8 {
1203 d |= Word(buf[i-1]) << s
1204 i--
1205 }
1206 z[len(z)-1] = d
1207 }
1208
1209 return z.norm()
1210 }
1211
1212
1213 func (z nat) sqrt(x nat) nat {
1214 if x.cmp(natOne) <= 0 {
1215 return z.set(x)
1216 }
1217 if alias(z, x) {
1218 z = nil
1219 }
1220
1221
1222
1223
1224
1225
1226 var z1, z2 nat
1227 z1 = z
1228 z1 = z1.setUint64(1)
1229 z1 = z1.shl(z1, uint(x.bitLen()+1)/2)
1230 for n := 0; ; n++ {
1231 z2, _ = z2.div(nil, x, z1)
1232 z2 = z2.add(z2, z1)
1233 z2 = z2.shr(z2, 1)
1234 if z2.cmp(z1) >= 0 {
1235
1236
1237 if n&1 == 0 {
1238 return z1
1239 }
1240 return z.set(z1)
1241 }
1242 z1, z2 = z2, z1
1243 }
1244 }
1245
View as plain text