botan.math.bigint.bigint source code

1 /**
2 * BigInt
3 * 
4 * Copyright:
5 * (C) 1999-2008,2012 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *    2007 FlexSecure
8 *
9 * License:
10 * Botan is released under the Simplified BSD License (see LICENSE.md)
11 */
12 module botan.math.bigint.bigint;
13 
14 import botan.constants;
15 public import botan.math.mp.mp_types;
16 public import botan.utils.types;
17 import botan.constants;
18 import botan.rng.rng;
19 import memutils.vector;
20 import botan.utils.charset;
21 import botan.codec.hex;
22 import botan.math.bigint.divide;
23 import botan.math.mp.mp_core;
24 import botan.utils.get_byte;
25 import botan.utils.parsing;
26 import botan.utils.rounding;
27 import botan.utils.parsing;
28 import botan.utils.bit_ops;
29 import std.algorithm;
30 import std.traits : isNumeric;
31 
32 /**
33 * Arbitrary precision integer
34 */
35 struct BigInt
36 {
37 public:
38     /*
39     * Write the BigInt into a vector
40     */
41     Vector!char toVector(Base base = Decimal) const
42     {
43         Vector!ubyte buffer = BigInt.encode(this, base);
44         Vector!char ret;
45         size_t skip = 0;
46         while(skip < buffer.length && buffer[skip] == '0')
47             ++skip;
48         ret[] = cast(char[])(buffer.ptr + skip)[0 .. buffer.length - skip];
49         return ret.move();
50     }
51 
52     /*
53     * Write the BigInt into a string
54     */
55     string toString(Base base = Decimal) const
56     {
57         auto vec = toVector(base);
58         //logTrace("toString: ", vec[]);
59         return (vec[]).idup;
60     }
61     alias Base = int;
62     /**
63     * Base enumerator for encoding and decoding
64     */
65     enum : Base { Decimal = 10, Hexadecimal = 16, Binary = 256 }
66 
67     alias Sign = bool;
68     /**
69     * Sign symbol definitions for positive and negative numbers
70     */
71     enum : Sign { Negative = 0, Positive = 1 }
72 
73     /**
74     * DivideByZero Exception
75     */
76     class DivideByZero : Exception
77     { 
78         this() {
79             super("BigInt divide by zero");
80         }
81     }
82 
83     /**
84     * Create BigInt from any integer
85     * Params:
86     *  n = initial value of this BigInt
87     */
88     this(T)(T n)
89         if (isNumeric!T)
90     {
91         import std.algorithm : max;
92         if (n == 0)
93             return;
94         const size_t limbs_needed = std.algorithm.max(1, T.sizeof / word.sizeof);
95         m_reg.resize(4*limbs_needed);
96         foreach (size_t i; 0 .. limbs_needed)
97             m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
98     }
99 
100     @disable this(this);
101 
102     /// Move constructor
103     ref BigInt opAssign(size_t other)
104     {
105         BigInt bigInt = BigInt(other);
106         this.swap(bigInt);
107         
108         return this;
109     }
110 
111 	/// Copy constructor
112 	void load()(auto ref BigInt other) {
113 		m_reg[] = other.m_reg[];
114 		m_signedness = other.m_signedness;
115 	}
116 
117     /**
118     * Create BigInt from a string. If the string starts with 0x the
119     * rest of the string will be interpreted as hexadecimal digits.
120     * Otherwise, it will be interpreted as a decimal number.
121     *
122     * Params:
123     *  str = the string to parse for an integer value
124     */
125     this(in string str)
126     {
127         Base base = Decimal;
128         size_t markers = 0;
129         bool negative = false;
130         
131         if (str.length > 0 && str[0] == '-')
132         {
133             markers += 1;
134             negative = true;
135         }
136         
137         if (str.length > markers + 2 && str[markers     ] == '0' &&
138         str[markers + 1] == 'x')
139         {
140             markers += 2;
141             base = Hexadecimal;
142         }
143         auto contents = decode(cast(const(ubyte)*)(str.ptr) + markers, str.length - markers, base);
144         this.swap( contents );
145 
146         if (negative) setSign(Negative);
147         else          setSign(Positive);
148     }
149 
150     /**
151     * Create a BigInt from an integer in a ubyte array
152     * Params:
153     *  input = the ubyte array holding the value
154     *  length = size of buf
155     *  base = is the number base of the integer in buf
156     */
157     this(const(ubyte)* input, size_t length, Base base = Binary)
158     {
159         auto contents = decode(input, length, base);
160         this.swap( contents );
161     }
162 
163     /**
164     * Create a random BigInt of the specified size
165     * Params:
166     *  rng = random number generator
167     *  bits = size in bits
168     *  set_high_bit = if true, the highest bit is always set
169     */
170     this(RandomNumberGenerator rng, size_t bits, bool set_high_bit = true)
171     {
172         randomize(rng, bits, set_high_bit);
173     }
174     /**
175     * Create BigInt of specified size, all zeros
176     * Params:
177     *  s = the sign
178     *  size = of the internal register in words
179     */
180     this(Sign s, size_t size)
181     {
182         m_reg.resize(roundUp!size_t(size, 8));
183         m_signedness = s;
184     }
185 
186     /**
187     * Move constructor
188     */
189     this()(auto ref BigInt other)
190     {
191         this.swap(other);
192     }    
193 
194     this(ALLOC)(auto const ref Vector!(ubyte, ALLOC) payload, in Sign sign) {
195         this(payload.ptr, payload.length, sig_words);
196     }
197 
198     this(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) payload, in Sign sign) {
199         this(payload.ptr, payload.length, sig_words);
200     }
201 
202     this()(auto ref SecureVector!word reg, Sign sign) {
203         import std.algorithm : swap;
204         m_reg.swap(reg);
205         swap(m_signedness, sign);
206     }
207 
208 	void reserve(size_t n) {
209 		m_reg.reserve(n);
210 	}
211 
212     /**
213     * Move assignment
214     */
215     void opAssign()(auto ref BigInt other)
216     {
217 		this.swap(other);
218     }
219 
220     /**
221     * Copy assignment
222     */
223     // BigInt operator=(const ref BigInt) = default;
224 
225     /**
226     * Swap this value with another
227     * Params:
228     *  other = BigInt to swap values with
229     */
230     void swap()(auto ref BigInt other)
231     {
232 		m_reg.swap(other.m_reg);
233 
234         .swap(m_signedness, other.m_signedness);
235     }
236 
237     void swapReg(ref SecureVector!word reg)
238     {
239         m_reg.swap(reg);
240     }
241 
242     /**
243     * += operator
244     * Params:
245     *  y = the BigInt to add to this
246     */
247     void opOpAssign(string op)(auto const ref BigInt y)
248         if (op == "+")
249     {
250         const size_t x_sw = sigWords(), y_sw = y.sigWords();
251         
252         const size_t reg_size = std.algorithm.max(x_sw, y_sw) + 1;
253         growTo(reg_size);
254         
255         if (sign() == y.sign())
256             bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw);
257         else
258         {
259             int relative_size = bigint_cmp(mutablePtr(), x_sw, y.ptr, y_sw);
260             
261             if (relative_size < 0)
262 			{               
263 				SecureVector!word z = SecureVector!word(reg_size - 1);
264 				bigint_sub3(z.ptr, y.ptr, reg_size - 1, mutablePtr(), x_sw);
265 				m_reg[] = z;
266                 setSign(y.sign());
267             }
268             else if (relative_size == 0)
269             {
270                 zeroise(m_reg);
271 		        setSign(Positive);
272             }
273             else if (relative_size > 0) 
274                 bigint_sub2(mutablePtr(), x_sw, y.ptr, y_sw);
275         }
276         
277     }
278 
279     void opOpAssign(string op)(in word y)
280         if (op == "+")
281     {
282         this += BigInt(y);
283     }
284 
285     /**
286     * -= operator
287     * Params:
288     *  y = the BigInt to subtract from this
289     */
290     void opOpAssign(string op)(auto const ref BigInt y)
291         if (op == "-")
292     {
293         const size_t x_sw = sigWords(), y_sw = y.sigWords();
294         
295         int relative_size = bigint_cmp(mutablePtr(), x_sw, y.ptr, y_sw);
296         
297         const size_t reg_size = std.algorithm.max(x_sw, y_sw) + 1;
298         growTo(reg_size);
299         
300         if (relative_size < 0)
301         {
302             if (sign() == y.sign())
303                 bigint_sub2_rev(mutablePtr(), y.ptr, y_sw);
304             else
305                 bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw);
306             
307             setSign(y.reverseSign());
308         }
309         else if (relative_size == 0)
310         {
311             if (sign() == y.sign())
312             {
313                 clear();
314                 setSign(Positive);
315             }
316             else
317                 bigint_shl1(mutablePtr(), x_sw, 0, 1);
318         }
319         else if (relative_size > 0)
320         {
321             if (sign() == y.sign())
322                 bigint_sub2(mutablePtr(), x_sw, y.ptr, y_sw);
323             else
324                 bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw);
325         }
326     }
327 
328 
329     void opOpAssign(string op)(in word y)
330         if (op == "-")
331     {
332         this -= BigInt(y);
333     }
334 
335 
336     /**
337     * *= operator
338     * Params:
339     *  y = the BigInt to multiply with this
340     */
341     void opOpAssign(string op)(const ref BigInt y)
342         if (op == "*")
343     {
344         const size_t x_sw = sigWords(), y_sw = y.sigWords();
345         setSign((sign() == y.sign()) ? Positive : Negative);
346         
347         if (x_sw == 0 || y_sw == 0)
348         {
349             clear();
350             setSign(Positive);
351         }
352         else if (x_sw == 1 && y_sw)
353         {
354             growTo(y_sw + 2);
355             bigint_linmul3(mutablePtr(), y.ptr, y_sw, wordAt(0));
356         }
357         else if (y_sw == 1 && x_sw)
358         {
359             growTo(x_sw + 2);
360             bigint_linmul2(mutablePtr(), x_sw, y.wordAt(0));
361         }
362         else
363         {
364             growTo(size() + y.length);
365             
366             SecureVector!word z = SecureVector!word(mutablePtr()[0 .. x_sw]);
367             SecureVector!word workspace = SecureVector!word(size());
368             
369             bigint_mul(mutablePtr(), size(), workspace.ptr, z.ptr, z.length, x_sw, y.ptr, y.length, y_sw);
370         }
371     }
372 
373 
374     void opOpAssign(string op)(in word y)
375         if (op == "*")
376     {
377         const BigInt b_y = BigInt(y);
378         this *= b_y;
379     }
380 
381     /**
382     * /= operator
383     * Params:
384     *   y = the BigInt to divide this by
385     */
386     void opOpAssign(string op)(auto const ref BigInt y)
387         if (op == "/")
388     {
389         if (y.sigWords() == 1 && isPowerOf2(y.wordAt(0)))
390             this >>= (y.bits() - 1);
391         else
392             this = this / y;
393     }
394 
395 
396     void opOpAssign(string op)(in word y)
397         if (op == "/")
398     {
399         this /= BigInt(y);
400     }
401 
402 
403     /**
404     * Modulo operator
405     * Params:
406     *  mod = the modulus to reduce this by
407     */
408     void opOpAssign(string op)(auto const ref BigInt mod)
409         if (op == "%")
410     {
411         this = this % mod;
412     }
413 
414     /**
415     * Modulo operator
416     * Params:
417     *  mod = the modulus (word) to reduce this by
418     */
419     void opOpAssign(string op)(word mod)
420         if (op == "%")
421     {
422         if (mod == 0)
423             throw new DivideByZero();
424         if (isPowerOf2(mod))
425         {
426             word result = (wordAt(0) & (mod - 1));
427             clear();
428             growTo(2);
429             m_reg[0] = result;
430             return;
431         }
432         
433         word remainder = 0;
434         
435         for (size_t j = sigWords(); j > 0; --j)
436             remainder = bigint_modop(remainder, wordAt(j-1), mod);
437         clear();
438         growTo(2);
439         
440         if (remainder && sign() == Negative)
441             m_reg[0] = mod - remainder;
442         else
443             m_reg[0] = remainder;
444         
445         setSign(Positive);
446     }
447 
448 
449     /**
450     * Left shift operator
451     * Params:
452     *  shift = the number of bits to shift this left by
453     */
454     void opOpAssign(string op)(size_t shift)
455         if (op == "<<")
456     {
457         if (shift)
458         {
459             const size_t shift_words = shift / MP_WORD_BITS;
460             const size_t shift_bits  = shift % MP_WORD_BITS;
461             const size_t words = sigWords();
462             
463             growTo(words + shift_words + (shift_bits ? 1 : 0));
464             bigint_shl1(mutablePtr(), words, shift_words, shift_bits);
465         }
466         
467     }
468 
469     /**
470     * Right shift operator
471     * Params:
472     *  shift = the number of bits to shift this right by
473     */
474     void opOpAssign(string op)(size_t shift)
475         if (op == ">>")
476     {
477         if (shift)
478         {
479             const size_t shift_words = shift / MP_WORD_BITS;
480             const size_t shift_bits  = shift % MP_WORD_BITS;
481             
482             bigint_shr1(mutablePtr(), sigWords(), shift_words, shift_bits);
483             if (isZero())
484                 setSign(Positive);
485         }
486     }
487 
488     /**
489     * Increment operator
490     */
491     ref BigInt opUnary(string op)() if (op == "++") { this += BigInt(1); return this; }
492 
493     /**
494     * Decrement operator
495     */
496     ref BigInt opUnary(string op)() if (op == "--") { this -= BigInt(1); return this; }
497 
498     /**
499     * Unary negation operator
500     * Returns: negative this
501     */
502     BigInt opUnary(string op)() const
503         if (op == "-")
504     {
505         BigInt ret = this.dup;
506         ret.flipSign();
507         return ret;
508     }
509 
510     /**
511     * bool cast
512     * Returns: true iff this is not zero, otherwise false
513     */
514     T opCast(T : bool)() const { return isNonzero(); }
515 
516     T opCast(T : BigInt)() const { return *cast(BigInt*)&this; }
517 
518     /**
519     * Zeroize the BigInt. The size of the underlying register is not
520     * modified.
521     */
522     void clear() 
523     { 
524         import core.stdc.string : memset;
525         if (!m_reg.empty){
526             memset(mutablePtr(), 0, word.sizeof*m_reg.length);
527         }
528     }
529 
530     /**
531     * Compare this to another BigInt
532     * Params:
533     *  other = the BigInt value to compare with
534     *  check_signs = include sign in comparison?
535     * Returns: if (this<n) return -1, if (this>n) return 1, if both
536     * values are identical return 0 [like Perl's <=> operator]
537     */
538     int cmp(const ref BigInt other, bool check_signs = true) const
539     {
540         if (check_signs)
541         {
542             if (other.isPositive() && this.isNegative())
543                 return -1;
544             
545             if (other.isNegative() && this.isPositive())
546                 return 1;
547             
548             if (other.isNegative() && this.isNegative())
549                 return (-bigint_cmp(m_reg.ptr, this.sigWords(), other.ptr, other.sigWords()));
550         }
551         
552         return bigint_cmp(m_reg.ptr, this.sigWords(), other.ptr, other.sigWords());
553     }
554     /*
555     * Comparison Operators
556     */
557     bool opEquals()(auto const ref BigInt b) const
558     { return (cmp(b) == 0); }
559 
560     bool opEquals(in size_t n) const
561     { 
562         BigInt b = n;
563         return (cmp(b) == 0); 
564     }
565 
566 
567     int opCmp()(auto const ref BigInt b) const
568     { 
569         return cmp(b);
570     }
571 
572     int opCmp(in size_t n) const
573     { 
574         BigInt b = n; 
575         return cmp(b); 
576     }
577 
578     /**
579     * Test if the integer has an even value
580     * Returns: true if the integer is even, false otherwise
581     */
582     bool isEven() const { return (getBit(0) == 0); }
583 
584     /**
585     * Test if the integer has an odd value
586     * Returns: true if the integer is odd, false otherwise
587     */
588     bool isOdd()  const { return (getBit(0) == 1); }
589 
590     /**
591     * Test if the integer is not zero
592     * Returns: true if the integer is non-zero, false otherwise
593     */
594     bool isNonzero() const { return (!isZero()); }
595 
596     /**
597     * Test if the integer is zero
598     * Returns: true if the integer is zero, false otherwise
599     */
600     bool isZero() const
601     {
602 		return sigWords() == 0;
603     }
604 
605     /**
606     * Set bit at specified position
607     * Params:
608     *  n = bit position to set
609     */
610     void setBit(size_t n)
611     {
612         const size_t which = n / MP_WORD_BITS;
613         const word mask = cast(word)(1) << (n % MP_WORD_BITS);
614         if (which >= size()) growTo(which + 1);
615         m_reg[which] |= mask;
616     }
617 
618     /**
619     * Clear bit at specified position
620     * Params:
621     *  n = bit position to clear
622     */
623     void clearBit(size_t n)
624     {
625         const size_t which = n / MP_WORD_BITS;
626         const word mask = cast(word)(1) << (n % MP_WORD_BITS);
627         if (which < size())
628             m_reg[which] &= ~mask;
629     }
630 
631     /**
632     * Clear all but the lowest n bits
633     * Params:
634     *  n = amount of bits to keep
635     */
636     void maskBits(size_t n)
637     {
638         if (n == 0) { clear(); return; }
639         if (n >= bits()) return;
640 
641         const size_t top_word = n / MP_WORD_BITS;
642         const word mask = ((cast(word)1) << (n % MP_WORD_BITS)) - 1;
643         
644         if (top_word < size())
645             clearMem(&m_reg[top_word+1], size() - (top_word + 1));
646         
647         m_reg[top_word] &= mask;
648     }
649 
650     /**
651     * Return bit value at specified position
652     * Params:
653     *  n = the bit offset to test
654     * Returns: true, if the bit at position n is set, false otherwise
655     */
656     bool getBit(size_t n) const
657     {
658         return ((wordAt(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
659     }
660 
661     /**
662     * Return (a maximum of) 32 bits of the complete value
663     * Params:
664     *  offset = the offset to start extracting
665     *  length = amount of bits to extract (starting at offset)
666     * Returns: the integer extracted from the register starting at
667     * offset with specified length
668     */
669     uint getSubstring(size_t offset, size_t length) const
670     {
671         if (length > 32)
672             throw new InvalidArgument("BigInt.getSubstring: Substring size too big");
673         
674         ulong piece = 0;
675         foreach (size_t i; 0 .. 8)
676         {
677             const ubyte part = byteAt((offset / 8) + (7-i));
678             piece = (piece << 8) | part;
679         }
680         
681         const ulong mask = (cast(ulong)(1) << length) - 1;
682         const size_t shift = (offset % 8);
683         
684         return cast(uint)((piece >> shift) & mask);
685     }
686 
687     /**
688     * Convert this value into a uint, if it is in the range
689     * [0 ... 2**32-1], or otherwise throw new an exception.
690     * Returns: the value as a uint if conversion is possible
691     */
692     uint toUint() const
693     {
694         if (isNegative())
695             throw new EncodingError("BigInt.to_uint: Number is negative");
696         if (bits() >= 32)
697             throw new EncodingError("BigInt.to_uint: Number is too big to convert");
698         
699         uint output = 0;
700         for (uint j = 0; j != 4; ++j)
701             output = (output << 8) | byteAt(3-j);
702         return output;
703     }
704 
705     /**
706     * Params:
707     *  n = the offset to get a ubyte from
708     * Returns: ubyte at offset n
709     */
710     ubyte byteAt(size_t n) const
711     {
712         const size_t WORD_BYTES = (word).sizeof;
713         size_t word_num = n / WORD_BYTES;
714         size_t byte_num = n % WORD_BYTES;
715         if (word_num >= size())
716             return 0;
717         else
718             return get_byte(WORD_BYTES - byte_num - 1, m_reg[word_num]);
719     }
720 
721     /**
722     * Return the word at a specified position of the internal register
723     * Params:
724     *  n = position in the register
725     * Returns: value at position n
726     */
727 	pragma(inline, true)
728     word wordAt(size_t n) const
729     { return ((n < size()) ? m_reg[n] : 0); }
730 
731     /**
732     * Tests if the sign of the integer is negative
733     * Returns: true, iff the integer has a negative sign
734     */
735     bool isNegative() const { return (sign() == Negative); }
736 
737     /**
738     * Tests if the sign of the integer is positive
739     * Returns: true, iff the integer has a positive sign
740     */
741     bool isPositive() const { return (sign() == Positive); }
742 
743     /**
744     * Return the sign of the integer
745     * Returns: the sign of the integer
746     */
747 	pragma(inline, true)
748     Sign sign() const { return (m_signedness); }
749 
750     /**
751     * Returns: the opposite sign of the represented integer value
752     */
753     Sign reverseSign() const
754     {
755         if (sign() == Positive)
756             return Negative;
757         return Positive;
758     }
759 
760     /**
761     * Flip the sign of this BigInt
762     */
763     void flipSign()
764     {
765         setSign(reverseSign());
766     }
767 
768     /**
769     * Set sign of the integer
770     * Params:
771     *  s = new Sign to set
772     */
773     void setSign(Sign s)
774     {
775         if (isZero())
776             m_signedness = Positive;
777         else
778             m_signedness = s;
779     }
780 
781     /**
782     * Returns: absolute (positive) value of this
783     */
784     BigInt abs() const
785     {
786         BigInt ret = this.dup;
787         ret.setSign(Positive);
788         return ret;
789     }
790 
791     /**
792     * Give size of internal register
793     * Returns: size of internal register in words
794     */
795 	pragma(inline, true)
796     size_t size() const { return m_reg.length; }
797 
798     // ditto
799 	pragma(inline, true)
800     size_t length() const { return size(); }
801 
802     /**
803     * Return how many words we need to hold this value
804     * Returns: significant words of the represented integer value
805     */
806     size_t sigWords() const
807     {
808         const word* x = m_reg.ptr;
809         size_t sig = m_reg.length;
810 
811         while (sig && (x[sig-1] == 0))
812             sig--;
813         return sig;
814     }
815 
816     /**
817     * Give ubyte length of the integer
818     * Returns: ubyte length of the represented integer value
819     */
820 	pragma(inline, true)
821     size_t bytes() const
822     {
823         return (bits() + 7) / 8;
824     }
825 
826     /**
827     * Get the bit length of the integer
828     * Returns: bit length of the represented integer value
829     */
830     size_t bits() const
831     {
832         const size_t words = sigWords();
833         if (words == 0)
834             return 0;
835         
836         const size_t full_words = words - 1;
837         return (full_words * MP_WORD_BITS + highBit(wordAt(full_words)));
838     }
839 
840     /**
841     * Return a mutable pointer to the register
842     * Returns: a pointer to the start of the internal register
843     */
844     word* mutablePtr() { return m_reg.ptr; }
845 
846     /**
847     * Return a const pointer to the register
848     * Returns: a pointer to the start of the internal register
849     */
850     @property const(word*) ptr() const { return m_reg.ptr; }
851 
852     /**
853     * Increase internal register buffer to at least n words
854     * Params:
855     *  n = new size of register
856     */
857     void growTo(size_t n)
858     {
859         if (n > size()) {
860 			if (m_reg.capacity < n) m_reg.reserve(n*2);
861             m_reg.resize(roundUp!size_t(n, 8));
862 		}
863     }
864 
865     /**
866     * Fill BigInt with a random number with size of bitsize
867     * If set_high_bit is true, the highest bit will be set, which causes
868     * the entropy to be bits-1. Otherwise the highest bit is randomly choosen
869     * by the rng, causing the entropy to be bits.
870     * 
871     * Params:
872     *  rng = the random number generator to use
873     *  bitsize = number of bits the created random value should have
874     *  set_high_bit = if true, the highest bit is always set
875     */
876     void randomize(RandomNumberGenerator rng, size_t bitsize = 0, bool set_high_bit = true)
877     {
878         setSign(Positive);
879         
880         if (bitsize == 0)
881             clear();
882         else
883         {
884             SecureVector!ubyte array = rng.randomVec((bitsize + 7) / 8);
885 			// Always cut unwanted bits
886             if (bitsize % 8)
887                 array[0] &= 0xFF >> (8 - (bitsize % 8));
888 			// Set the highest bit if wanted
889 			if (set_high_bit)
890 				array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
891             binaryDecode(array.ptr, array.length);
892         }
893     }
894 
895     /**
896     * Store BigInt-value in a given ubyte array
897     * Params:
898     *  output = destination ubyte array for the integer value
899     */
900     void binaryEncode(ubyte* output) const
901     {
902         const size_t sig_bytes = bytes();
903         foreach (size_t i; 0 .. sig_bytes) {
904             output[sig_bytes-i-1] = byteAt(i);
905         }
906     }
907 
908     /**
909     * Read integer value from a ubyte array with given size
910     * Params:
911     *  buf = ubyte array buffer containing the integer
912     *  length = size of buf
913     */
914     void binaryDecode(const(ubyte)* buf, size_t length)
915     {
916         const size_t WORD_BYTES = (word).sizeof;
917         
918         clear();
919         m_reg.resize(roundUp!size_t((length / WORD_BYTES) + 1, 8));
920         foreach (size_t i; 0 .. (length / WORD_BYTES))
921         {
922             const size_t top = length - WORD_BYTES*i;
923             for (size_t j = WORD_BYTES; j > 0; --j)
924                 m_reg[i] = (m_reg[i] << 8) | buf[top - j];
925         }
926         
927         foreach (size_t i; 0 .. (length % WORD_BYTES))
928             m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
929     }
930 
931     /**
932     * Read integer value from a ubyte array (SecureVector!ubyte)
933     * Params:
934     *  buf = the array to load from
935     */
936     void binaryDecode(ALLOC)(auto const ref Vector!(ubyte, ALLOC) buf)
937     {
938         binaryDecode(buf.ptr, buf.length);
939     }
940 
941     /// ditto
942     void binaryDecode(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) buf)
943     {
944         binaryDecode(buf.ptr, buf.length);
945     }
946 
947     /**
948     * Params:
949     *  base = the base to measure the size for
950     * Returns: size of this integer in base base
951     */
952     size_t encodedSize(Base base = Binary) const
953     {
954         static const double LOG_2_BASE_10 = 0.30102999566;
955         
956         if (base == Binary)
957             return bytes();
958         else if (base == Hexadecimal)
959             return 2*bytes();
960         else if (base == Decimal)
961             return cast(size_t)((bits() * LOG_2_BASE_10) + 1);
962         else
963             throw new InvalidArgument("Unknown base for BigInt encoding");
964     }
965 
966     /**
967     * Params:
968     *  rng = a random number generator
969     *  min = the minimum value
970     *  max = the maximum value
971     * Returns: random integer in [min,max$(RPAREN)
972     */
973     static BigInt randomInteger()(RandomNumberGenerator rng, auto const ref BigInt min, auto const ref BigInt max)
974     {
975 		BigInt delta_upper_bound = max - min - 1;
976 
977         if (delta_upper_bound <= 0)
978             throw new InvalidArgument("randomInteger: invalid min/max values");
979 		// Choose x in [0, delta_upper_bound]
980 		BigInt x;
981 		do {
982 			auto bitsize = delta_upper_bound.bits();
983 			x.randomize(rng, bitsize, false);
984 		} while (x > delta_upper_bound);
985 
986 		return min + x;
987     }
988 
989     /**
990     * Create a power of two
991     * Params:
992     *  n = the power of two to create
993     * Returns: bigint representing 2^n
994     */
995     static BigInt powerOf2(size_t n)
996     {
997         BigInt b;
998         b.setBit(n);
999         return b;
1000     }
1001 
1002     /**
1003     * Encode the integer value from a BigInt to an Array of bytes
1004     * Params:
1005     *  n = the BigInt to use as integer source
1006     *  base = number-base of resulting ubyte array representation
1007     * Returns: SecureVector of bytes containing the integer with given base
1008     */
1009     static Vector!ubyte encode()(auto const ref BigInt n, Base base = Binary)
1010     {
1011         Vector!ubyte output = Vector!ubyte(n.encodedSize(base));
1012         encode(output.ptr, n, base);
1013         if (base != Binary)
1014             for (size_t j = 0; j != output.length; ++j)
1015                 if (output[j] == 0)
1016                     output[j] = '0';
1017         return output.move();
1018     }
1019 
1020     /**
1021     * Encode the integer value from a BigInt to a Secure Array of bytes
1022     * Params:
1023     *  n = the BigInt to use as integer source
1024     *  base = number-base of resulting ubyte array representation
1025     * Returns: SecureVector of bytes containing the integer with given base
1026     */
1027     static SecureVector!ubyte encodeLocked()(auto const ref BigInt n, Base base = Binary)
1028     {
1029         SecureVector!ubyte output = SecureVector!ubyte(n.encodedSize(base));
1030         encode(output.ptr, n, base);
1031         if (base != Binary)
1032             for (size_t j = 0; j != output.length; ++j)
1033                 if (output[j] == 0)
1034                     output[j] = '0';
1035         return output.move();
1036     }
1037 
1038     /**
1039     * Encode the integer value from a BigInt to a ubyte array
1040     * Params:
1041     *  output = destination ubyte array for the encoded integer
1042     * value with given base
1043     *  n = the BigInt to use as integer source
1044     *  base = number-base of resulting ubyte array representation
1045     */
1046     static void encode()(ubyte* output, auto const ref BigInt n, Base base = Binary)
1047     {
1048         if (base == Binary)
1049         {
1050             n.binaryEncode(output);
1051         }
1052         else if (base == Hexadecimal)
1053         {
1054             SecureVector!ubyte binary = SecureVector!ubyte(n.encodedSize(Binary));
1055             n.binaryEncode(binary.ptr);
1056             
1057             hexEncode(cast(char*)(output), binary.ptr, binary.length);
1058         }
1059         else if (base == Decimal)
1060         {
1061             BigInt copy = n.dup();
1062             BigInt remainder;
1063             copy.setSign(Positive);
1064             const size_t output_size = n.encodedSize(Decimal);
1065             foreach (size_t j; 0 .. output_size)
1066             {
1067                 auto bi = BigInt(10);
1068                 divide(copy, bi, copy, remainder);
1069                 output[output_size - 1 - j] = digit2char(cast(ubyte)(remainder.wordAt(0)));
1070                 if (copy.isZero())
1071                     break;
1072             }
1073         }
1074         else
1075             throw new InvalidArgument("Unknown BigInt encoding method");
1076     }
1077 
1078     /**
1079     * Create a BigInt from an integer in a ubyte array
1080     * Params:
1081     *  buf = the binary value to load
1082     *  length = size of buf
1083     *  base = number-base of the integer in buf
1084     * Returns: BigInt representing the integer in the ubyte array
1085     */
1086     static BigInt decode(const(ubyte)* buf, size_t length, Base base = Binary)
1087     {
1088         BigInt r;
1089         if (base == Binary)
1090             r.binaryDecode(buf, length);
1091         else if (base == Hexadecimal)
1092         {
1093             SecureVector!ubyte binary;
1094             if (length % 2)
1095             {
1096                 // Handle lack of leading 0
1097                 const char[2] buf0_with_leading_0 = [ '0', cast(char)(buf[0]) ];
1098                 
1099                 binary = hexDecodeLocked(buf0_with_leading_0.ptr, 2);
1100                 binary.reserve(length);
1101                 binary ~= hexDecodeLocked(cast(const(char)*)&buf[1], length - 1, false);
1102             }
1103             else {
1104                 binary = hexDecodeLocked(cast(const(char)*)buf, length, false);
1105             }
1106             r.binaryDecode(binary.ptr, binary.length);
1107         }
1108         else if (base == Decimal)
1109         {
1110             foreach (size_t i; 0 .. length)
1111             {
1112                 if (isSpace(buf[i]))
1113                     continue;
1114                 
1115                 if (!isDigit(buf[i]))
1116                     throw new InvalidArgument("BigInt.decode: " ~ "Invalid character in decimal input");
1117                 
1118                 const ubyte x = char2digit(buf[i]);
1119                 
1120                 if (x >= 10)
1121                     throw new InvalidArgument("BigInt: Invalid decimal string");
1122                 
1123                 r *= 10;
1124                 r += x;
1125             }
1126         }
1127         else
1128             throw new InvalidArgument("Unknown BigInt decoding method");
1129         return r.move;
1130     }
1131 
1132 
1133     /**
1134     * Create a BigInt from an integer in a ubyte array
1135     * Params:
1136     *  buf = the binary value to load
1137     *  base = number-base of the integer in buf
1138     * Returns: BigInt representing the integer in the ubyte array
1139     */
1140     static BigInt decode(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) buf, Base base = Binary)
1141     {
1142         return BigInt.decode(buf.ptr, buf.length, base);
1143     }
1144 
1145     /**
1146     * Create a BigInt from an integer in a ubyte array
1147     * Params:
1148     *  buf = the binary value to load
1149     *  base = number-base of the integer in buf
1150     * Returns: BigInt representing the integer in the ubyte array
1151     */
1152     static BigInt decode(ALLOC)(auto const ref Vector!(ubyte, ALLOC) buf, Base base = Binary)
1153     {
1154         return BigInt.decode(buf.ptr, buf.length, base);
1155     }
1156 
1157     /**
1158     * Encode a BigInt to a ubyte array according to IEEE 1363
1159     * Params:
1160     *  n = the BigInt to encode
1161     *  bytes = the length of the resulting SecureVector!ubyte
1162     * Returns: a SecureVector!ubyte containing the encoded BigInt
1163     */
1164     static SecureVector!ubyte encode1363()(auto const ref BigInt n, size_t bytes)
1165     {
1166         const size_t n_bytes = n.bytes();
1167         if (n_bytes > bytes)
1168             throw new EncodingError("encode1363: n is too large to encode properly");
1169         const size_t leading_0s = bytes - n_bytes;
1170         SecureVector!ubyte output = SecureVector!ubyte(bytes);
1171         encode(output.ptr + leading_0s, n, Binary);
1172         return output;
1173     }
1174 
1175     /*
1176     * Addition Operator
1177     */
1178     BigInt opBinary(string op)(auto const ref BigInt y) const
1179         if (op == "+")
1180     {
1181         const BigInt* x = &this;
1182         const size_t x_sw = x.sigWords(), y_sw = y.sigWords();
1183         
1184         BigInt z = BigInt(x.sign(), std.algorithm.max(x_sw, y_sw) + 1);
1185         
1186         if ((x.sign() == y.sign()))
1187             bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw);
1188         else
1189         {
1190             int relative_size = bigint_cmp(x.ptr, x_sw, y.ptr, y_sw);
1191             
1192             if (relative_size < 0)
1193             {
1194                 bigint_sub3(z.mutablePtr(), y.ptr, y_sw, x.ptr, x_sw);
1195                 z.setSign(y.sign());
1196             }
1197             else if (relative_size == 0)
1198                 z.setSign(BigInt.Positive);
1199             else if (relative_size > 0)
1200                 bigint_sub3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw);
1201         }
1202         return z.move();
1203     }
1204 
1205     BigInt opBinary(string op)(in word y) const
1206         if (op == "+")
1207     {
1208         return this + BigInt(y);
1209     }
1210 
1211     /*
1212     * Subtraction Operator
1213     */
1214     BigInt opBinary(string op)(auto const ref BigInt y) const
1215         if (op == "-")
1216     {
1217         const BigInt* x = &this;
1218         const size_t x_sw = x.sigWords(), y_sw = y.sigWords();
1219         
1220         int relative_size = bigint_cmp(x.ptr, x_sw, y.ptr, y_sw);
1221         
1222         BigInt z = BigInt(BigInt.Positive, std.algorithm.max(x_sw, y_sw) + 1);
1223         
1224         if (relative_size < 0)
1225         {
1226             if (x.sign() == y.sign())
1227                 bigint_sub3(z.mutablePtr(), y.ptr, y_sw, x.ptr, x_sw);
1228             else
1229                 bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw);
1230             z.setSign(y.reverseSign());
1231         }
1232         else if (relative_size == 0)
1233         {
1234             if (x.sign() != y.sign())
1235                 bigint_shl2(z.mutablePtr(), x.ptr, x_sw, 0, 1);
1236         }
1237         else if (relative_size > 0)
1238         {
1239             if (x.sign() == y.sign())
1240                 bigint_sub3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw);
1241             else
1242                 bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw);
1243             z.setSign(x.sign());
1244         }
1245         return z.move();
1246     }
1247 
1248 
1249     BigInt opBinary(string op)(in word y) const
1250         if (op == "-")
1251     {
1252         return this - BigInt(y);
1253     }
1254 
1255     /*
1256     * Multiplication Operator
1257     */
1258     BigInt opBinary(string op)(auto const ref BigInt y) const
1259         if (op == "*")
1260     {
1261         const BigInt* x = &this;
1262         const size_t x_sw = x.sigWords(), y_sw = y.sigWords();
1263         
1264         BigInt z = BigInt(BigInt.Positive, x.length + y.length);
1265         
1266         if (x_sw == 1 && y_sw)
1267             bigint_linmul3(z.mutablePtr(), y.ptr, y_sw, x.wordAt(0));
1268         else if (y_sw == 1 && x_sw)
1269             bigint_linmul3(z.mutablePtr(), x.ptr, x_sw, y.wordAt(0));
1270         else if (x_sw && y_sw)
1271         {
1272             SecureVector!word workspace = SecureVector!word(z.length);
1273             bigint_mul(z.mutablePtr(), z.length, workspace.ptr,
1274                         x.ptr, x.length, x_sw,
1275                         y.ptr, y.length, y_sw);
1276         }
1277         
1278         if (x_sw && y_sw && x.sign() != y.sign())
1279             z.flipSign();
1280         return z.move();
1281     }
1282 
1283 
1284     BigInt opBinary(string op)(in word y) const
1285         if (op == "*")
1286     {
1287         return this * BigInt(y);
1288     }
1289     
1290     /*
1291     * Division Operator
1292     */
1293     BigInt opBinary(string op)(auto const ref BigInt y) const
1294         if (op == "/")
1295     {
1296         const BigInt* x = &this;
1297         BigInt q, r;
1298         divide(*x, y, q, r);
1299         return q.move();
1300     }
1301 
1302 
1303     BigInt opBinary(string op)(in word y) const
1304         if (op == "/")
1305     {
1306         return this / BigInt(y);
1307     }
1308 
1309     /*
1310     * Modulo Operator
1311     */
1312     BigInt opBinary(string op)(auto const ref BigInt mod) const
1313         if (op == "%")
1314     {
1315         const BigInt* n = &this;
1316         if (mod.isZero())
1317             throw new BigInt.DivideByZero();
1318         if (mod.isNegative())
1319             throw new InvalidArgument("BigInt.operator%: modulus must be > 0");
1320         if (n.isPositive() && mod.isPositive() && *n < mod)
1321             return n.dup;
1322         
1323         BigInt q, r;
1324         divide(*n, mod, q, r);
1325         return r.move();
1326     }
1327 
1328     /*
1329     * Modulo Operator
1330     */
1331     word opBinary(string op)(word mod) const
1332         if (op == "%")
1333     {
1334         const BigInt* n = &this;
1335         if (mod == 0)
1336             throw new BigInt.DivideByZero();
1337         
1338         if (isPowerOf2(mod))
1339             return (n.wordAt(0) & (mod - 1));
1340         
1341         word remainder = 0;
1342         
1343         for (size_t j = n.sigWords(); j > 0; --j)
1344             remainder = bigint_modop(remainder, n.wordAt(j-1), mod);
1345         
1346         if (remainder && n.sign() == BigInt.Negative)
1347             return mod - remainder;
1348         return remainder;
1349     }
1350     
1351     /*
1352     * Left Shift Operator
1353     */
1354     BigInt opBinary(string op)(size_t shift) const
1355         if (op == "<<")
1356     {
1357         const BigInt* x = &this;
1358         if (shift == 0)
1359             return x.dup();
1360         
1361         const size_t shift_words = shift / MP_WORD_BITS,
1362             shift_bits  = shift % MP_WORD_BITS;
1363         
1364         const size_t x_sw = x.sigWords();
1365         
1366         BigInt y = BigInt(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
1367         bigint_shl2(y.mutablePtr(), x.ptr, x_sw, shift_words, shift_bits);
1368         return y.move();
1369     }
1370     
1371     /*
1372     * Right Shift Operator
1373     */
1374     BigInt opBinary(string op)(size_t shift) const
1375         if (op == ">>")
1376     {
1377         if (shift == 0)
1378             return this.dup;
1379         if (bits() <= shift)
1380             return BigInt(0);
1381         
1382         const size_t shift_words = shift / MP_WORD_BITS,
1383             shift_bits  = shift % MP_WORD_BITS,
1384             x_sw = sigWords();
1385         
1386         BigInt y = BigInt(sign(), x_sw - shift_words);
1387         bigint_shr2(y.mutablePtr(), ptr, x_sw, shift_words, shift_bits);
1388         return y.move();
1389     }
1390 
1391     @property BigInt move() {
1392         return BigInt(m_reg, m_signedness);
1393     }
1394 
1395     @property BigInt dup() const {
1396         return BigInt(m_reg.dup(), m_signedness);
1397     }
1398 private:
1399 
1400     SecureVector!word m_reg;
1401     Sign m_signedness = Positive;
1402 }