This library provides a way to easily handle arbitrary large integers.
This library provides the following operations :
- addition, substraction, multiplication, division and modulo
- bits operators (AND, OR, XOR, left and right shifts)
- boolean operators
- modular exponentiation (using montgomery algorithm)
- modular inverse
Example
In this example, we use a 1024 bits long RSA key to encrypt and decrypt a message. We first encrypt the value 0x41 (65 in decimal) and then decrypt it. At the end, m should be equal to 0x41. The encryption is fast (0, 4 second) while the decryption is really slow. This code will take between 30 seconds and 2 minutes to execute depending on the compiler and optimization flags.
main.cpp
#include "mbed.h" #include "BigInt.h" #include <stdlib.h> #include <stdio.h> uint8_t modbits[] = { 0xd9, 0x4d, 0x88, 0x9e, 0x88, 0x85, 0x3d, 0xd8, 0x97, 0x69, 0xa1, 0x80, 0x15, 0xa0, 0xa2, 0xe6, 0xbf, 0x82, 0xbf, 0x35, 0x6f, 0xe1, 0x4f, 0x25, 0x1f, 0xb4, 0xf5, 0xe2, 0xdf, 0x0d, 0x9f, 0x9a, 0x94, 0xa6, 0x8a, 0x30, 0xc4, 0x28, 0xb3, 0x9e, 0x33, 0x62, 0xfb, 0x37, 0x79, 0xa4, 0x97, 0xec, 0xea, 0xea, 0x37, 0x10, 0x0f, 0x26, 0x4d, 0x7f, 0xb9, 0xfb, 0x1a, 0x97, 0xfb, 0xf6, 0x21, 0x13, 0x3d, 0xe5, 0x5f, 0xdc, 0xb9, 0xb1, 0xad, 0x0d, 0x7a, 0x31, 0xb3, 0x79, 0x21, 0x6d, 0x79, 0x25, 0x2f, 0x5c, 0x52, 0x7b, 0x9b, 0xc6, 0x3d, 0x83, 0xd4, 0xec, 0xf4, 0xd1, 0xd4, 0x5c, 0xbf, 0x84, 0x3e, 0x84, 0x74, 0xba, 0xbc, 0x65, 0x5e, 0x9b, 0xb6, 0x79, 0x9c, 0xba, 0x77, 0xa4, 0x7e, 0xaf, 0xa8, 0x38, 0x29, 0x64, 0x74, 0xaf, 0xc2, 0x4b, 0xeb, 0x9c, 0x82, 0x5b, 0x73, 0xeb, 0xf5, 0x49 }; uint8_t dbits[] = { 0x04, 0x7b, 0x9c, 0xfd, 0xe8, 0x43, 0x17, 0x6b, 0x88, 0x74, 0x1d, 0x68, 0xcf, 0x09, 0x69, 0x52, 0xe9, 0x50, 0x81, 0x31, 0x51, 0x05, 0x8c, 0xe4, 0x6f, 0x2b, 0x04, 0x87, 0x91, 0xa2, 0x6e, 0x50, 0x7a, 0x10, 0x95, 0x79, 0x3c, 0x12, 0xba, 0xe1, 0xe0, 0x9d, 0x82, 0x21, 0x3a, 0xd9, 0x32, 0x69, 0x28, 0xcf, 0x7c, 0x23, 0x50, 0xac, 0xb1, 0x9c, 0x98, 0xf1, 0x9d, 0x32, 0xd5, 0x77, 0xd6, 0x66, 0xcd, 0x7b, 0xb8, 0xb2, 0xb5, 0xba, 0x62, 0x9d, 0x25, 0xcc, 0xf7, 0x2a, 0x5c, 0xeb, 0x8a, 0x8d, 0xa0, 0x38, 0x90, 0x6c, 0x84, 0xdc, 0xdb, 0x1f, 0xe6, 0x77, 0xdf, 0xfb, 0x2c, 0x02, 0x9f, 0xd8, 0x92, 0x63, 0x18, 0xee, 0xde, 0x1b, 0x58, 0x27, 0x2a, 0xf2, 0x2b, 0xda, 0x5c, 0x52, 0x32, 0xbe, 0x06, 0x68, 0x39, 0x39, 0x8e, 0x42, 0xf5, 0x35, 0x2d, 0xf5, 0x88, 0x48, 0xad, 0xad, 0x11, 0xa1 }; int main() { BigInt e = 65537, mod, d; mod.importData(modbits, sizeof(modbits)); d.importData(dbits, sizeof(dbits)); BigInt c = modPow(0x41,e,mod); c.print(); BigInt m = modPow(c,d,mod); m.print(); printf("done\n"); return 0; }
BigInt.cpp@26:94e26bcd229d, 2014-05-11 (annotated)
- Committer:
- feb11
- Date:
- Sun May 11 10:33:20 2014 +0000
- Revision:
- 26:94e26bcd229d
- Parent:
- 25:3d5c1f299da2
Support signed integers. Add invMod function
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
feb11 | 0:9d554894785b | 1 | #include "BigInt.h" |
feb11 | 0:9d554894785b | 2 | #include <string.h> |
feb11 | 0:9d554894785b | 3 | #include <stdio.h> |
feb11 | 0:9d554894785b | 4 | #include <stdlib.h> |
feb11 | 0:9d554894785b | 5 | #include <iostream> |
feb11 | 0:9d554894785b | 6 | #include <climits> |
feb11 | 9:3c191fa04f6e | 7 | #include <cassert> |
feb11 | 10:116e201f7d89 | 8 | #include <algorithm> |
feb11 | 0:9d554894785b | 9 | |
feb11 | 15:85a6bd4539eb | 10 | static uint32_t BITS[] = |
feb11 | 15:85a6bd4539eb | 11 | { |
feb11 | 15:85a6bd4539eb | 12 | 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080, |
feb11 | 15:85a6bd4539eb | 13 | 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000, |
feb11 | 15:85a6bd4539eb | 14 | 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, |
feb11 | 15:85a6bd4539eb | 15 | 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000 |
feb11 | 15:85a6bd4539eb | 16 | }; |
feb11 | 15:85a6bd4539eb | 17 | |
feb11 | 24:a3453a18388c | 18 | static uint32_t BITS2[] = |
feb11 | 24:a3453a18388c | 19 | { |
feb11 | 24:a3453a18388c | 20 | 0x00FFFFFF, 0x0000FFFF, 0x00FFFFFF |
feb11 | 24:a3453a18388c | 21 | }; |
feb11 | 24:a3453a18388c | 22 | |
feb11 | 24:a3453a18388c | 23 | static inline uint32_t num(const uint32_t a) |
feb11 | 0:9d554894785b | 24 | { |
feb11 | 0:9d554894785b | 25 | return a/4 + (a%4 ? 1:0); |
feb11 | 0:9d554894785b | 26 | } |
feb11 | 10:116e201f7d89 | 27 | |
feb11 | 10:116e201f7d89 | 28 | |
feb11 | 0:9d554894785b | 29 | BigInt::BigInt(): |
feb11 | 26:94e26bcd229d | 30 | sign(POS), |
feb11 | 0:9d554894785b | 31 | size(0), |
feb11 | 0:9d554894785b | 32 | bits(0) |
feb11 | 0:9d554894785b | 33 | { |
feb11 | 0:9d554894785b | 34 | } |
feb11 | 0:9d554894785b | 35 | |
feb11 | 26:94e26bcd229d | 36 | BigInt::BigInt(int32_t a) |
feb11 | 2:1001793a090d | 37 | { |
feb11 | 26:94e26bcd229d | 38 | if(a < 0) |
feb11 | 26:94e26bcd229d | 39 | { |
feb11 | 26:94e26bcd229d | 40 | a = -a; |
feb11 | 26:94e26bcd229d | 41 | sign = NEG; |
feb11 | 26:94e26bcd229d | 42 | } |
feb11 | 26:94e26bcd229d | 43 | else |
feb11 | 26:94e26bcd229d | 44 | sign = POS; |
feb11 | 26:94e26bcd229d | 45 | |
feb11 | 2:1001793a090d | 46 | if(a >> 24) |
feb11 | 2:1001793a090d | 47 | size = 4; |
feb11 | 2:1001793a090d | 48 | else if(a >> 16) |
feb11 | 2:1001793a090d | 49 | size = 3; |
feb11 | 2:1001793a090d | 50 | else if(a >> 8) |
feb11 | 2:1001793a090d | 51 | size = 2; |
feb11 | 2:1001793a090d | 52 | else |
feb11 | 2:1001793a090d | 53 | size = 1; |
feb11 | 2:1001793a090d | 54 | bits = new uint32_t[1]; |
feb11 | 2:1001793a090d | 55 | bits[0] = a; |
feb11 | 2:1001793a090d | 56 | } |
feb11 | 2:1001793a090d | 57 | |
feb11 | 0:9d554894785b | 58 | BigInt::BigInt(const BigInt &a): |
feb11 | 26:94e26bcd229d | 59 | sign(a.sign), |
feb11 | 0:9d554894785b | 60 | size(a.size) |
feb11 | 0:9d554894785b | 61 | { |
feb11 | 0:9d554894785b | 62 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 63 | bits = new uint32_t[l]; |
feb11 | 25:3d5c1f299da2 | 64 | for(int i = 0; i < (int)l; ++i) |
feb11 | 0:9d554894785b | 65 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 66 | } |
feb11 | 0:9d554894785b | 67 | |
feb11 | 0:9d554894785b | 68 | |
feb11 | 0:9d554894785b | 69 | BigInt::~BigInt() |
feb11 | 0:9d554894785b | 70 | { |
feb11 | 10:116e201f7d89 | 71 | if(size) |
feb11 | 9:3c191fa04f6e | 72 | { |
feb11 | 0:9d554894785b | 73 | delete[] bits; |
feb11 | 9:3c191fa04f6e | 74 | } |
feb11 | 0:9d554894785b | 75 | } |
feb11 | 0:9d554894785b | 76 | |
feb11 | 0:9d554894785b | 77 | BigInt& BigInt::operator=(const BigInt& a) |
feb11 | 0:9d554894785b | 78 | { |
feb11 | 26:94e26bcd229d | 79 | sign = a.sign; |
feb11 | 0:9d554894785b | 80 | size = a.size; |
feb11 | 0:9d554894785b | 81 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 82 | if(bits) |
feb11 | 0:9d554894785b | 83 | delete[] bits; |
feb11 | 0:9d554894785b | 84 | bits = new uint32_t[l]; |
feb11 | 25:3d5c1f299da2 | 85 | for(int i = 0; i < (int)l; ++i) |
feb11 | 0:9d554894785b | 86 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 87 | return *this; |
feb11 | 0:9d554894785b | 88 | } |
feb11 | 0:9d554894785b | 89 | |
feb11 | 26:94e26bcd229d | 90 | void BigInt::importData(uint8_t *data, uint32_t length, bool sign) |
feb11 | 0:9d554894785b | 91 | { |
feb11 | 26:94e26bcd229d | 92 | this->sign = sign; |
feb11 | 0:9d554894785b | 93 | size = length; |
feb11 | 0:9d554894785b | 94 | if(bits) |
feb11 | 0:9d554894785b | 95 | delete[] bits; |
feb11 | 22:9d5f18b86753 | 96 | bits = new uint32_t[num(size)]; |
feb11 | 22:9d5f18b86753 | 97 | memset(bits, 0, sizeof(uint32_t)*num(size)); |
feb11 | 25:3d5c1f299da2 | 98 | for(int i = 0; i < (int)length; ++i) |
feb11 | 22:9d5f18b86753 | 99 | bits[i/4] |= data[length-i-1] << ((i%4)*8); |
feb11 | 18:4549ca354fdb | 100 | |
feb11 | 18:4549ca354fdb | 101 | trim(); |
feb11 | 0:9d554894785b | 102 | } |
feb11 | 0:9d554894785b | 103 | |
feb11 | 26:94e26bcd229d | 104 | void BigInt::exportData(uint8_t *data, uint32_t length, bool &sign) |
feb11 | 13:d0b4d7cfeb98 | 105 | { |
feb11 | 13:d0b4d7cfeb98 | 106 | assert(isValid() && data != 0); |
feb11 | 13:d0b4d7cfeb98 | 107 | |
feb11 | 14:5a1852dac7f7 | 108 | if(length < size) |
feb11 | 14:5a1852dac7f7 | 109 | return; |
feb11 | 26:94e26bcd229d | 110 | |
feb11 | 26:94e26bcd229d | 111 | sign = this->sign; |
feb11 | 14:5a1852dac7f7 | 112 | uint32_t offset = length-size; |
feb11 | 14:5a1852dac7f7 | 113 | memset(data, 0, offset); |
feb11 | 14:5a1852dac7f7 | 114 | for(int i = size-1; i >= 0; --i) |
feb11 | 14:5a1852dac7f7 | 115 | data[offset+size-1-i] = bits[i/4] >> ((i%4)*8); |
feb11 | 13:d0b4d7cfeb98 | 116 | } |
feb11 | 13:d0b4d7cfeb98 | 117 | |
feb11 | 0:9d554894785b | 118 | BigInt operator+(const BigInt &a, const BigInt& b) |
feb11 | 0:9d554894785b | 119 | { |
feb11 | 9:3c191fa04f6e | 120 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 121 | |
feb11 | 26:94e26bcd229d | 122 | if(a.sign == POS && b.sign == POS) // a+b |
feb11 | 26:94e26bcd229d | 123 | return add(a, b); |
feb11 | 26:94e26bcd229d | 124 | if(a.sign == NEG && b.sign == NEG) // (-a)+(-b) = -(a+b) |
feb11 | 26:94e26bcd229d | 125 | return -add(a, b); |
feb11 | 26:94e26bcd229d | 126 | else if(a.sign == POS) // a + (-b) = a-b |
feb11 | 26:94e26bcd229d | 127 | return a - (-b); |
feb11 | 26:94e26bcd229d | 128 | else // (-a) + b = b-a |
feb11 | 26:94e26bcd229d | 129 | return b - (-a); |
feb11 | 0:9d554894785b | 130 | } |
feb11 | 0:9d554894785b | 131 | |
feb11 | 0:9d554894785b | 132 | BigInt& BigInt::operator+=(const BigInt &b) |
feb11 | 0:9d554894785b | 133 | { |
feb11 | 0:9d554894785b | 134 | return (*this = (*this) + b); |
feb11 | 0:9d554894785b | 135 | } |
feb11 | 0:9d554894785b | 136 | |
feb11 | 0:9d554894785b | 137 | BigInt& BigInt::operator++() |
feb11 | 0:9d554894785b | 138 | { |
feb11 | 3:3fa3ceb0c69d | 139 | return (*this += 1); |
feb11 | 0:9d554894785b | 140 | } |
feb11 | 0:9d554894785b | 141 | |
feb11 | 0:9d554894785b | 142 | BigInt BigInt::operator++(int) |
feb11 | 0:9d554894785b | 143 | { |
feb11 | 0:9d554894785b | 144 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 145 | *this += 1; |
feb11 | 0:9d554894785b | 146 | return t; |
feb11 | 0:9d554894785b | 147 | } |
feb11 | 0:9d554894785b | 148 | |
feb11 | 20:d747159d77c4 | 149 | BigInt operator-(const BigInt& a, const BigInt& b) |
feb11 | 0:9d554894785b | 150 | { |
feb11 | 9:3c191fa04f6e | 151 | assert(a.isValid() && b.isValid()); |
feb11 | 26:94e26bcd229d | 152 | |
feb11 | 26:94e26bcd229d | 153 | if(a.sign == POS && b.sign == POS) |
feb11 | 0:9d554894785b | 154 | { |
feb11 | 26:94e26bcd229d | 155 | if(equals(a, b)) |
feb11 | 26:94e26bcd229d | 156 | return 0; |
feb11 | 26:94e26bcd229d | 157 | else if(greater(a, b)) |
feb11 | 26:94e26bcd229d | 158 | return sub(a, b); |
feb11 | 26:94e26bcd229d | 159 | else |
feb11 | 26:94e26bcd229d | 160 | return -sub(b, a); |
feb11 | 20:d747159d77c4 | 161 | } |
feb11 | 26:94e26bcd229d | 162 | else if(a.sign == NEG && b.sign == NEG) |
feb11 | 26:94e26bcd229d | 163 | return (-b) - (-a); |
feb11 | 26:94e26bcd229d | 164 | else if(a.sign == NEG && b.sign == POS) |
feb11 | 26:94e26bcd229d | 165 | return -add(a, b); |
feb11 | 26:94e26bcd229d | 166 | else |
feb11 | 26:94e26bcd229d | 167 | return add(a, b); |
feb11 | 26:94e26bcd229d | 168 | } |
feb11 | 26:94e26bcd229d | 169 | |
feb11 | 26:94e26bcd229d | 170 | BigInt operator-(const BigInt &a) |
feb11 | 26:94e26bcd229d | 171 | { |
feb11 | 26:94e26bcd229d | 172 | assert(a.isValid()); |
feb11 | 26:94e26bcd229d | 173 | |
feb11 | 26:94e26bcd229d | 174 | BigInt result = a; |
feb11 | 26:94e26bcd229d | 175 | result.sign = !a.sign; |
feb11 | 20:d747159d77c4 | 176 | return result; |
feb11 | 0:9d554894785b | 177 | } |
feb11 | 0:9d554894785b | 178 | |
feb11 | 0:9d554894785b | 179 | BigInt& BigInt::operator-=(const BigInt &b) |
feb11 | 0:9d554894785b | 180 | { |
feb11 | 0:9d554894785b | 181 | return (*this = (*this) - b); |
feb11 | 0:9d554894785b | 182 | } |
feb11 | 0:9d554894785b | 183 | |
feb11 | 0:9d554894785b | 184 | BigInt& BigInt::operator--() |
feb11 | 0:9d554894785b | 185 | { |
feb11 | 3:3fa3ceb0c69d | 186 | return (*this -= 1); |
feb11 | 0:9d554894785b | 187 | } |
feb11 | 0:9d554894785b | 188 | |
feb11 | 0:9d554894785b | 189 | BigInt BigInt::operator--(int) |
feb11 | 0:9d554894785b | 190 | { |
feb11 | 0:9d554894785b | 191 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 192 | *this -= 1; |
feb11 | 0:9d554894785b | 193 | return t; |
feb11 | 0:9d554894785b | 194 | } |
feb11 | 3:3fa3ceb0c69d | 195 | |
feb11 | 1:00f2c40d46ed | 196 | BigInt operator*(const BigInt &a, const BigInt& b) |
feb11 | 1:00f2c40d46ed | 197 | { |
feb11 | 9:3c191fa04f6e | 198 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 199 | |
feb11 | 1:00f2c40d46ed | 200 | // if a == 0 or b == 0 then result = 0 |
feb11 | 1:00f2c40d46ed | 201 | if(!a || !b) |
feb11 | 12:a436f15b58b6 | 202 | return 0; |
feb11 | 26:94e26bcd229d | 203 | |
feb11 | 26:94e26bcd229d | 204 | BigInt result; |
feb11 | 26:94e26bcd229d | 205 | if(equals(a, 1)) |
feb11 | 26:94e26bcd229d | 206 | result = b; |
feb11 | 26:94e26bcd229d | 207 | else if(equals(b, 1)) |
feb11 | 26:94e26bcd229d | 208 | result = a; |
feb11 | 26:94e26bcd229d | 209 | else |
feb11 | 26:94e26bcd229d | 210 | result = mul(a, b); |
feb11 | 26:94e26bcd229d | 211 | |
feb11 | 26:94e26bcd229d | 212 | if(a.sign == b.sign) |
feb11 | 26:94e26bcd229d | 213 | result.sign = POS; |
feb11 | 26:94e26bcd229d | 214 | else |
feb11 | 26:94e26bcd229d | 215 | result.sign = NEG; |
feb11 | 1:00f2c40d46ed | 216 | return result; |
feb11 | 1:00f2c40d46ed | 217 | } |
feb11 | 1:00f2c40d46ed | 218 | |
feb11 | 1:00f2c40d46ed | 219 | BigInt& BigInt::operator*=(const BigInt &b) |
feb11 | 1:00f2c40d46ed | 220 | { |
feb11 | 1:00f2c40d46ed | 221 | return (*this = (*this) * b); |
feb11 | 1:00f2c40d46ed | 222 | } |
feb11 | 1:00f2c40d46ed | 223 | |
feb11 | 11:2f16a220ebbb | 224 | BigInt operator/(const BigInt &a, const BigInt &b) |
feb11 | 10:116e201f7d89 | 225 | { |
feb11 | 10:116e201f7d89 | 226 | assert(a.isValid() && b.isValid() && b != 0); |
feb11 | 15:85a6bd4539eb | 227 | |
feb11 | 26:94e26bcd229d | 228 | if(lesser(a, b)) |
feb11 | 10:116e201f7d89 | 229 | return 0; |
feb11 | 20:d747159d77c4 | 230 | |
feb11 | 26:94e26bcd229d | 231 | BigInt result; |
feb11 | 26:94e26bcd229d | 232 | |
feb11 | 26:94e26bcd229d | 233 | if(equals(a, b)) |
feb11 | 26:94e26bcd229d | 234 | result = 1; |
feb11 | 26:94e26bcd229d | 235 | else if(equals(b, 1)) |
feb11 | 26:94e26bcd229d | 236 | result = a; |
feb11 | 26:94e26bcd229d | 237 | else |
feb11 | 26:94e26bcd229d | 238 | result = div(a, b); |
feb11 | 26:94e26bcd229d | 239 | |
feb11 | 26:94e26bcd229d | 240 | if(a.sign == b.sign) |
feb11 | 26:94e26bcd229d | 241 | result.sign = POS; |
feb11 | 26:94e26bcd229d | 242 | else |
feb11 | 26:94e26bcd229d | 243 | result.sign = NEG; |
feb11 | 26:94e26bcd229d | 244 | |
feb11 | 26:94e26bcd229d | 245 | return result; |
feb11 | 10:116e201f7d89 | 246 | } |
feb11 | 10:116e201f7d89 | 247 | |
feb11 | 10:116e201f7d89 | 248 | BigInt& BigInt::operator/=(const BigInt &b) |
feb11 | 10:116e201f7d89 | 249 | { |
feb11 | 10:116e201f7d89 | 250 | return (*this = (*this) / b); |
feb11 | 10:116e201f7d89 | 251 | } |
feb11 | 10:116e201f7d89 | 252 | |
feb11 | 1:00f2c40d46ed | 253 | BigInt operator>>(const BigInt &a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 254 | { |
feb11 | 9:3c191fa04f6e | 255 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 256 | |
feb11 | 12:a436f15b58b6 | 257 | if(m == 0) |
feb11 | 12:a436f15b58b6 | 258 | return a; |
feb11 | 12:a436f15b58b6 | 259 | if(m/8 >= a.size) |
feb11 | 12:a436f15b58b6 | 260 | return 0; |
feb11 | 12:a436f15b58b6 | 261 | |
feb11 | 1:00f2c40d46ed | 262 | BigInt result; |
feb11 | 1:00f2c40d46ed | 263 | result.size = a.size - m/8; |
feb11 | 1:00f2c40d46ed | 264 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 20:d747159d77c4 | 265 | memset(result.bits, 0, sizeof(uint32_t)*num(result.size)); |
feb11 | 1:00f2c40d46ed | 266 | uint8_t s = m%32; |
feb11 | 1:00f2c40d46ed | 267 | for(uint32_t i = 0; i < num(result.size); ++i) |
feb11 | 1:00f2c40d46ed | 268 | { |
feb11 | 1:00f2c40d46ed | 269 | if(m/32+i+1 < num(a.size)) |
feb11 | 1:00f2c40d46ed | 270 | result.bits[i] = (a.bits[m/32+i+1] << (32-s)) | (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 271 | else |
feb11 | 1:00f2c40d46ed | 272 | result.bits[i] = (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 273 | } |
feb11 | 1:00f2c40d46ed | 274 | |
feb11 | 10:116e201f7d89 | 275 | result.trim(); |
feb11 | 26:94e26bcd229d | 276 | result.checkZero(); |
feb11 | 26:94e26bcd229d | 277 | |
feb11 | 1:00f2c40d46ed | 278 | return result; |
feb11 | 1:00f2c40d46ed | 279 | } |
feb11 | 1:00f2c40d46ed | 280 | |
feb11 | 1:00f2c40d46ed | 281 | BigInt& BigInt::operator>>=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 282 | { |
feb11 | 20:d747159d77c4 | 283 | return (*this = (*this >> m)); |
feb11 | 1:00f2c40d46ed | 284 | } |
feb11 | 1:00f2c40d46ed | 285 | |
feb11 | 20:d747159d77c4 | 286 | BigInt operator<<(const BigInt& a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 287 | { |
feb11 | 9:3c191fa04f6e | 288 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 289 | |
feb11 | 26:94e26bcd229d | 290 | if(m == 0) |
feb11 | 26:94e26bcd229d | 291 | return a; |
feb11 | 26:94e26bcd229d | 292 | |
feb11 | 1:00f2c40d46ed | 293 | BigInt result; |
feb11 | 9:3c191fa04f6e | 294 | |
feb11 | 1:00f2c40d46ed | 295 | result.size = m/8 + a.size; |
feb11 | 12:a436f15b58b6 | 296 | if((m%32)%8 != 0) |
feb11 | 1:00f2c40d46ed | 297 | ++result.size; |
feb11 | 1:00f2c40d46ed | 298 | uint32_t l = num(result.size); |
feb11 | 1:00f2c40d46ed | 299 | result.bits = new uint32_t[l]; |
feb11 | 1:00f2c40d46ed | 300 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 1:00f2c40d46ed | 301 | uint32_t s = m % 32; |
feb11 | 20:d747159d77c4 | 302 | result.bits[m/32] = a.bits[0] << s; |
feb11 | 20:d747159d77c4 | 303 | for(uint32_t i = 1; i < num(a.size); ++i) |
feb11 | 20:d747159d77c4 | 304 | result.bits[m/32+i] = (a.bits[i] << s) | (a.bits[i-1] >> (32-s)); |
feb11 | 26:94e26bcd229d | 305 | if(s != 0 && num(result.size) != 1) |
feb11 | 26:94e26bcd229d | 306 | result.bits[num(result.size)-1] |= a.bits[num(a.size)-1] >> (32-s); |
feb11 | 1:00f2c40d46ed | 307 | |
feb11 | 12:a436f15b58b6 | 308 | result.trim(); |
feb11 | 1:00f2c40d46ed | 309 | |
feb11 | 1:00f2c40d46ed | 310 | return result; |
feb11 | 1:00f2c40d46ed | 311 | } |
feb11 | 1:00f2c40d46ed | 312 | |
feb11 | 1:00f2c40d46ed | 313 | BigInt& BigInt::operator<<=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 314 | { |
feb11 | 1:00f2c40d46ed | 315 | return (*this = *this << m); |
feb11 | 1:00f2c40d46ed | 316 | } |
feb11 | 0:9d554894785b | 317 | |
feb11 | 5:beeb31f340a7 | 318 | BigInt operator%(const BigInt &a, const BigInt &b) |
feb11 | 5:beeb31f340a7 | 319 | { |
feb11 | 10:116e201f7d89 | 320 | assert(a.isValid() && b.isValid() && b > 0); |
feb11 | 26:94e26bcd229d | 321 | if(a < b) |
feb11 | 26:94e26bcd229d | 322 | return a; |
feb11 | 26:94e26bcd229d | 323 | if(a == b) |
feb11 | 26:94e26bcd229d | 324 | return 0; |
feb11 | 12:a436f15b58b6 | 325 | return a - (a/b)*b; |
feb11 | 5:beeb31f340a7 | 326 | } |
feb11 | 5:beeb31f340a7 | 327 | |
feb11 | 5:beeb31f340a7 | 328 | BigInt& BigInt::operator%=(const BigInt &a) |
feb11 | 5:beeb31f340a7 | 329 | { |
feb11 | 5:beeb31f340a7 | 330 | return (*this = *this % a); |
feb11 | 5:beeb31f340a7 | 331 | } |
feb11 | 5:beeb31f340a7 | 332 | |
feb11 | 0:9d554894785b | 333 | bool operator==(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 334 | { |
feb11 | 9:3c191fa04f6e | 335 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 336 | |
feb11 | 26:94e26bcd229d | 337 | return a.sign == b.sign && equals(a, b); |
feb11 | 0:9d554894785b | 338 | } |
feb11 | 0:9d554894785b | 339 | |
feb11 | 0:9d554894785b | 340 | bool operator!=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 341 | { |
feb11 | 0:9d554894785b | 342 | return ! (a==b); |
feb11 | 0:9d554894785b | 343 | } |
feb11 | 0:9d554894785b | 344 | |
feb11 | 0:9d554894785b | 345 | bool operator<(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 346 | { |
feb11 | 9:3c191fa04f6e | 347 | assert(a.isValid() && b.isValid()); |
feb11 | 26:94e26bcd229d | 348 | |
feb11 | 26:94e26bcd229d | 349 | if(a.sign == NEG && b.sign == NEG) |
feb11 | 26:94e26bcd229d | 350 | return !lesser(a, b); |
feb11 | 26:94e26bcd229d | 351 | else if(a.sign == NEG && b.sign == POS) |
feb11 | 0:9d554894785b | 352 | return true; |
feb11 | 26:94e26bcd229d | 353 | else if(a.sign == POS && b.sign == NEG) |
feb11 | 0:9d554894785b | 354 | return false; |
feb11 | 26:94e26bcd229d | 355 | else |
feb11 | 26:94e26bcd229d | 356 | return lesser(a, b); |
feb11 | 0:9d554894785b | 357 | } |
feb11 | 0:9d554894785b | 358 | |
feb11 | 0:9d554894785b | 359 | bool operator<=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 360 | { |
feb11 | 9:3c191fa04f6e | 361 | return !(a > b); |
feb11 | 0:9d554894785b | 362 | } |
feb11 | 0:9d554894785b | 363 | |
feb11 | 0:9d554894785b | 364 | bool operator>(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 365 | { |
feb11 | 9:3c191fa04f6e | 366 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 367 | |
feb11 | 26:94e26bcd229d | 368 | if(a.sign == NEG && b.sign == NEG) |
feb11 | 26:94e26bcd229d | 369 | return !greater(a, b); |
feb11 | 26:94e26bcd229d | 370 | else if(a.sign == NEG && b.sign == POS) |
feb11 | 0:9d554894785b | 371 | return false; |
feb11 | 26:94e26bcd229d | 372 | else if(a.sign == POS && b.sign == NEG) |
feb11 | 26:94e26bcd229d | 373 | return true; |
feb11 | 26:94e26bcd229d | 374 | else |
feb11 | 26:94e26bcd229d | 375 | return greater(a, b); |
feb11 | 0:9d554894785b | 376 | } |
feb11 | 0:9d554894785b | 377 | |
feb11 | 0:9d554894785b | 378 | bool operator>=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 379 | { |
feb11 | 9:3c191fa04f6e | 380 | return !(a < b); |
feb11 | 0:9d554894785b | 381 | } |
feb11 | 0:9d554894785b | 382 | |
feb11 | 1:00f2c40d46ed | 383 | bool operator!(const BigInt &a) |
feb11 | 0:9d554894785b | 384 | { |
feb11 | 9:3c191fa04f6e | 385 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 386 | |
feb11 | 1:00f2c40d46ed | 387 | if(a.size != 1) |
feb11 | 0:9d554894785b | 388 | return false; |
feb11 | 1:00f2c40d46ed | 389 | return a.bits[0] == 0; |
feb11 | 0:9d554894785b | 390 | } |
feb11 | 0:9d554894785b | 391 | |
feb11 | 7:1aad58757705 | 392 | |
feb11 | 7:1aad58757705 | 393 | BigInt operator&(const BigInt &a, const BigInt &b) |
feb11 | 7:1aad58757705 | 394 | { |
feb11 | 9:3c191fa04f6e | 395 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 396 | |
feb11 | 7:1aad58757705 | 397 | BigInt result; |
feb11 | 7:1aad58757705 | 398 | |
feb11 | 21:cfa04e0e6b59 | 399 | result.size = std::min(a.size, b.size); |
feb11 | 7:1aad58757705 | 400 | uint32_t l = num(result.size); |
feb11 | 7:1aad58757705 | 401 | result.bits = new uint32_t[l]; |
feb11 | 21:cfa04e0e6b59 | 402 | memset(result.bits, 0, l*sizeof(uint32_t)); |
feb11 | 7:1aad58757705 | 403 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 7:1aad58757705 | 404 | result.bits[i] = a.bits[i] & b.bits[i]; |
feb11 | 7:1aad58757705 | 405 | |
feb11 | 9:3c191fa04f6e | 406 | result.trim(); |
feb11 | 7:1aad58757705 | 407 | |
feb11 | 7:1aad58757705 | 408 | return result; |
feb11 | 7:1aad58757705 | 409 | } |
feb11 | 7:1aad58757705 | 410 | |
feb11 | 7:1aad58757705 | 411 | BigInt& BigInt::operator&=(const BigInt &a) |
feb11 | 7:1aad58757705 | 412 | { |
feb11 | 7:1aad58757705 | 413 | return (*this = *this & a); |
feb11 | 7:1aad58757705 | 414 | } |
feb11 | 7:1aad58757705 | 415 | |
feb11 | 7:1aad58757705 | 416 | BigInt operator|(const BigInt &a, const BigInt &b) |
feb11 | 7:1aad58757705 | 417 | { |
feb11 | 9:3c191fa04f6e | 418 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 419 | |
feb11 | 7:1aad58757705 | 420 | BigInt result; |
feb11 | 7:1aad58757705 | 421 | |
feb11 | 7:1aad58757705 | 422 | uint32_t na = num(a.size); |
feb11 | 7:1aad58757705 | 423 | uint32_t nb = num(b.size); |
feb11 | 10:116e201f7d89 | 424 | uint32_t l = std::max(na,nb); |
feb11 | 10:116e201f7d89 | 425 | result.size = std::max(a.size, b.size); |
feb11 | 21:cfa04e0e6b59 | 426 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 21:cfa04e0e6b59 | 427 | memset(result.bits, 0, num(result.size)*sizeof(uint32_t)); |
feb11 | 7:1aad58757705 | 428 | |
feb11 | 7:1aad58757705 | 429 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 7:1aad58757705 | 430 | { |
feb11 | 7:1aad58757705 | 431 | if(i < na && i < nb) |
feb11 | 7:1aad58757705 | 432 | result.bits[i] = a.bits[i] | b.bits[i]; |
feb11 | 7:1aad58757705 | 433 | else if(i < na) |
feb11 | 7:1aad58757705 | 434 | result.bits[i] = a.bits[i]; |
feb11 | 7:1aad58757705 | 435 | else |
feb11 | 7:1aad58757705 | 436 | result.bits[i] = b.bits[i]; |
feb11 | 7:1aad58757705 | 437 | } |
feb11 | 7:1aad58757705 | 438 | |
feb11 | 20:d747159d77c4 | 439 | result.trim(); |
feb11 | 20:d747159d77c4 | 440 | |
feb11 | 7:1aad58757705 | 441 | return result; |
feb11 | 7:1aad58757705 | 442 | } |
feb11 | 7:1aad58757705 | 443 | |
feb11 | 7:1aad58757705 | 444 | BigInt& BigInt::operator|=(const BigInt &a) |
feb11 | 7:1aad58757705 | 445 | { |
feb11 | 7:1aad58757705 | 446 | return (*this = *this | a); |
feb11 | 7:1aad58757705 | 447 | } |
feb11 | 8:2a361f1b41da | 448 | |
feb11 | 8:2a361f1b41da | 449 | BigInt operator^(const BigInt &a, const BigInt &b) |
feb11 | 8:2a361f1b41da | 450 | { |
feb11 | 9:3c191fa04f6e | 451 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 452 | |
feb11 | 8:2a361f1b41da | 453 | BigInt result; |
feb11 | 8:2a361f1b41da | 454 | |
feb11 | 8:2a361f1b41da | 455 | uint32_t na = num(a.size); |
feb11 | 8:2a361f1b41da | 456 | uint32_t nb = num(b.size); |
feb11 | 10:116e201f7d89 | 457 | result.size = std::max(a.size, b.size); |
feb11 | 21:cfa04e0e6b59 | 458 | uint32_t l = num(result.size); |
feb11 | 8:2a361f1b41da | 459 | result.bits = new uint32_t[l]; |
feb11 | 21:cfa04e0e6b59 | 460 | memset(result.bits, 0, l*sizeof(uint32_t)); |
feb11 | 8:2a361f1b41da | 461 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 8:2a361f1b41da | 462 | { |
feb11 | 8:2a361f1b41da | 463 | if(i < na && i < nb) |
feb11 | 8:2a361f1b41da | 464 | result.bits[i] = a.bits[i] ^ b.bits[i]; |
feb11 | 8:2a361f1b41da | 465 | else if(i < na) |
feb11 | 8:2a361f1b41da | 466 | result.bits[i] = a.bits[i]; |
feb11 | 8:2a361f1b41da | 467 | else |
feb11 | 8:2a361f1b41da | 468 | result.bits[i] = b.bits[i]; |
feb11 | 8:2a361f1b41da | 469 | } |
feb11 | 8:2a361f1b41da | 470 | |
feb11 | 9:3c191fa04f6e | 471 | result.trim(); |
feb11 | 9:3c191fa04f6e | 472 | |
feb11 | 8:2a361f1b41da | 473 | return result; |
feb11 | 8:2a361f1b41da | 474 | } |
feb11 | 8:2a361f1b41da | 475 | |
feb11 | 8:2a361f1b41da | 476 | BigInt& BigInt::operator^=(const BigInt &a) |
feb11 | 8:2a361f1b41da | 477 | { |
feb11 | 8:2a361f1b41da | 478 | return (*this = *this ^ a); |
feb11 | 8:2a361f1b41da | 479 | } |
feb11 | 9:3c191fa04f6e | 480 | |
feb11 | 19:412b822df7bf | 481 | // Perform one step : (a * b) / r mod m |
feb11 | 10:116e201f7d89 | 482 | BigInt montgomeryStep(const BigInt &a, const BigInt &b, const BigInt &m, uint32_t r) |
feb11 | 10:116e201f7d89 | 483 | { |
feb11 | 10:116e201f7d89 | 484 | BigInt result = 0; |
feb11 | 16:d70cf164440c | 485 | uint32_t j = 0; |
feb11 | 10:116e201f7d89 | 486 | while(r > 0) |
feb11 | 10:116e201f7d89 | 487 | { |
feb11 | 16:d70cf164440c | 488 | if(a.bits[j/32] & BITS[j%32]) |
feb11 | 26:94e26bcd229d | 489 | result.fastAdd(b); |
feb11 | 10:116e201f7d89 | 490 | |
feb11 | 20:d747159d77c4 | 491 | if(result.bits[0] & BITS[0]) |
feb11 | 26:94e26bcd229d | 492 | result.fastAdd(m); |
feb11 | 16:d70cf164440c | 493 | |
feb11 | 16:d70cf164440c | 494 | ++j; |
feb11 | 10:116e201f7d89 | 495 | --r; |
feb11 | 26:94e26bcd229d | 496 | result.fastShr(); |
feb11 | 10:116e201f7d89 | 497 | } |
feb11 | 19:412b822df7bf | 498 | |
feb11 | 19:412b822df7bf | 499 | if(result >= m) |
feb11 | 19:412b822df7bf | 500 | return result - m; |
feb11 | 20:d747159d77c4 | 501 | |
feb11 | 10:116e201f7d89 | 502 | return result; |
feb11 | 10:116e201f7d89 | 503 | } |
feb11 | 10:116e201f7d89 | 504 | |
feb11 | 10:116e201f7d89 | 505 | // Implementation using Montgomery algorithm |
feb11 | 9:3c191fa04f6e | 506 | BigInt modPow(const BigInt &a, const BigInt &expn, const BigInt &modulus) |
feb11 | 9:3c191fa04f6e | 507 | { |
feb11 | 19:412b822df7bf | 508 | assert(a.isValid() && expn.isValid() && modulus.isValid() && modulus != 0); |
feb11 | 20:d747159d77c4 | 509 | |
feb11 | 20:d747159d77c4 | 510 | if(modulus == 1) |
feb11 | 20:d747159d77c4 | 511 | return 0; |
feb11 | 19:412b822df7bf | 512 | if(expn == 0) |
feb11 | 19:412b822df7bf | 513 | return 1; |
feb11 | 19:412b822df7bf | 514 | if(a == 1) |
feb11 | 19:412b822df7bf | 515 | return 1; |
feb11 | 20:d747159d77c4 | 516 | if(expn == 1) |
feb11 | 20:d747159d77c4 | 517 | return a % modulus; |
feb11 | 9:3c191fa04f6e | 518 | |
feb11 | 20:d747159d77c4 | 519 | const uint32_t r = 8*modulus.size; |
feb11 | 23:002f471a973e | 520 | |
feb11 | 10:116e201f7d89 | 521 | // convert a in montgomery world |
feb11 | 17:9811d859dc83 | 522 | BigInt montA = (a << r) % modulus; |
feb11 | 20:d747159d77c4 | 523 | |
feb11 | 16:d70cf164440c | 524 | BigInt tmp; |
feb11 | 20:d747159d77c4 | 525 | const uint32_t n = expn.numBits(); |
feb11 | 23:002f471a973e | 526 | uint32_t j = 0; |
feb11 | 20:d747159d77c4 | 527 | while(j <= n) |
feb11 | 9:3c191fa04f6e | 528 | { |
feb11 | 24:a3453a18388c | 529 | |
feb11 | 16:d70cf164440c | 530 | if(expn.bits[j/32] & BITS[j%32]) |
feb11 | 16:d70cf164440c | 531 | { |
feb11 | 16:d70cf164440c | 532 | if(tmp.isValid()) |
feb11 | 19:412b822df7bf | 533 | tmp = montgomeryStep(tmp, montA, modulus, r); |
feb11 | 16:d70cf164440c | 534 | else |
feb11 | 16:d70cf164440c | 535 | tmp = montA; |
feb11 | 16:d70cf164440c | 536 | } |
feb11 | 16:d70cf164440c | 537 | ++j; |
feb11 | 23:002f471a973e | 538 | if(j <= n) |
feb11 | 23:002f471a973e | 539 | montA = montgomeryStep(montA, montA, modulus, r); |
feb11 | 24:a3453a18388c | 540 | |
feb11 | 9:3c191fa04f6e | 541 | } |
feb11 | 19:412b822df7bf | 542 | |
feb11 | 20:d747159d77c4 | 543 | // convert tmp to normal world |
feb11 | 10:116e201f7d89 | 544 | return montgomeryStep(tmp, 1, modulus, r); |
feb11 | 9:3c191fa04f6e | 545 | } |
feb11 | 9:3c191fa04f6e | 546 | |
feb11 | 26:94e26bcd229d | 547 | // Implementation as described in FIPS.186-4, Appendix C.1 |
feb11 | 26:94e26bcd229d | 548 | BigInt invMod(const BigInt &a, const BigInt &modulus) |
feb11 | 26:94e26bcd229d | 549 | { |
feb11 | 26:94e26bcd229d | 550 | assert(a.isValid() && modulus.isValid() && 0 < a && a < modulus); |
feb11 | 26:94e26bcd229d | 551 | |
feb11 | 26:94e26bcd229d | 552 | BigInt i = modulus; |
feb11 | 26:94e26bcd229d | 553 | BigInt j = a; |
feb11 | 26:94e26bcd229d | 554 | BigInt y2 = 0; |
feb11 | 26:94e26bcd229d | 555 | BigInt y1 = 1; |
feb11 | 26:94e26bcd229d | 556 | do |
feb11 | 26:94e26bcd229d | 557 | { |
feb11 | 26:94e26bcd229d | 558 | BigInt quotient = i / j; |
feb11 | 26:94e26bcd229d | 559 | BigInt remainder = i - (j * quotient); |
feb11 | 26:94e26bcd229d | 560 | BigInt y = y2 - (y1 * quotient); |
feb11 | 26:94e26bcd229d | 561 | i = j; |
feb11 | 26:94e26bcd229d | 562 | j = remainder; |
feb11 | 26:94e26bcd229d | 563 | y2 = y1; |
feb11 | 26:94e26bcd229d | 564 | y1 = y; |
feb11 | 26:94e26bcd229d | 565 | }while(j > 0); |
feb11 | 26:94e26bcd229d | 566 | |
feb11 | 26:94e26bcd229d | 567 | |
feb11 | 26:94e26bcd229d | 568 | assert(i == 1); |
feb11 | 26:94e26bcd229d | 569 | |
feb11 | 26:94e26bcd229d | 570 | y2 %= modulus; |
feb11 | 26:94e26bcd229d | 571 | if(y2 < 0) |
feb11 | 26:94e26bcd229d | 572 | y2 += modulus; |
feb11 | 26:94e26bcd229d | 573 | |
feb11 | 26:94e26bcd229d | 574 | return y2; |
feb11 | 26:94e26bcd229d | 575 | } |
feb11 | 26:94e26bcd229d | 576 | |
feb11 | 9:3c191fa04f6e | 577 | bool BigInt::isValid() const |
feb11 | 9:3c191fa04f6e | 578 | { |
feb11 | 9:3c191fa04f6e | 579 | return size != 0 && bits != 0; |
feb11 | 9:3c191fa04f6e | 580 | } |
feb11 | 9:3c191fa04f6e | 581 | |
feb11 | 11:2f16a220ebbb | 582 | void BigInt::print() const |
feb11 | 0:9d554894785b | 583 | { |
feb11 | 11:2f16a220ebbb | 584 | assert(isValid()); |
feb11 | 11:2f16a220ebbb | 585 | |
feb11 | 25:3d5c1f299da2 | 586 | printf("size: %lu bytes\n", size); |
feb11 | 0:9d554894785b | 587 | uint32_t n = num(size); |
feb11 | 26:94e26bcd229d | 588 | if(sign == NEG) |
feb11 | 26:94e26bcd229d | 589 | printf("- "); |
feb11 | 0:9d554894785b | 590 | for(int i = n-1; i >= 0; --i) |
feb11 | 25:3d5c1f299da2 | 591 | printf("%08x ", (int)bits[i]); |
feb11 | 0:9d554894785b | 592 | printf("\n"); |
feb11 | 0:9d554894785b | 593 | } |
feb11 | 9:3c191fa04f6e | 594 | |
feb11 | 26:94e26bcd229d | 595 | // return a + b |
feb11 | 26:94e26bcd229d | 596 | BigInt add(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 597 | { |
feb11 | 26:94e26bcd229d | 598 | BigInt result; |
feb11 | 26:94e26bcd229d | 599 | |
feb11 | 26:94e26bcd229d | 600 | result.size = std::max(a.size, b.size) + 1; |
feb11 | 26:94e26bcd229d | 601 | size_t l = num(result.size); |
feb11 | 26:94e26bcd229d | 602 | result.bits = new uint32_t[l]; |
feb11 | 26:94e26bcd229d | 603 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 26:94e26bcd229d | 604 | uint32_t al = num(a.size); |
feb11 | 26:94e26bcd229d | 605 | uint32_t bl = num(b.size); |
feb11 | 26:94e26bcd229d | 606 | uint32_t carry = 0; |
feb11 | 26:94e26bcd229d | 607 | for(int i = 0; i < (int)l; ++i) |
feb11 | 26:94e26bcd229d | 608 | { |
feb11 | 26:94e26bcd229d | 609 | uint32_t tmpA = 0, tmpB = 0; |
feb11 | 26:94e26bcd229d | 610 | if(i < (int)al) |
feb11 | 26:94e26bcd229d | 611 | tmpA = a.bits[i]; |
feb11 | 26:94e26bcd229d | 612 | if(i < (int)bl) |
feb11 | 26:94e26bcd229d | 613 | tmpB = b.bits[i]; |
feb11 | 26:94e26bcd229d | 614 | result.bits[i] = tmpA + tmpB + carry; |
feb11 | 26:94e26bcd229d | 615 | carry = result.bits[i] < std::max(tmpA, tmpB); |
feb11 | 26:94e26bcd229d | 616 | } |
feb11 | 26:94e26bcd229d | 617 | |
feb11 | 26:94e26bcd229d | 618 | result.trim(); |
feb11 | 26:94e26bcd229d | 619 | result.checkZero(); |
feb11 | 26:94e26bcd229d | 620 | |
feb11 | 26:94e26bcd229d | 621 | return result; |
feb11 | 26:94e26bcd229d | 622 | } |
feb11 | 26:94e26bcd229d | 623 | |
feb11 | 26:94e26bcd229d | 624 | // return a - b |
feb11 | 26:94e26bcd229d | 625 | // Assume that a > b |
feb11 | 26:94e26bcd229d | 626 | BigInt sub(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 627 | { |
feb11 | 26:94e26bcd229d | 628 | BigInt result; |
feb11 | 26:94e26bcd229d | 629 | result.size = a.size; |
feb11 | 26:94e26bcd229d | 630 | uint32_t l = num(a.size); |
feb11 | 26:94e26bcd229d | 631 | result.bits = new uint32_t[l]; |
feb11 | 26:94e26bcd229d | 632 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 26:94e26bcd229d | 633 | uint32_t bl = num(b.size); |
feb11 | 26:94e26bcd229d | 634 | uint8_t borrow = 0; |
feb11 | 26:94e26bcd229d | 635 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 26:94e26bcd229d | 636 | { |
feb11 | 26:94e26bcd229d | 637 | uint32_t tmpA = a.bits[i], tmpB = 0; |
feb11 | 26:94e26bcd229d | 638 | if(i < bl) |
feb11 | 26:94e26bcd229d | 639 | tmpB = b.bits[i]; |
feb11 | 26:94e26bcd229d | 640 | |
feb11 | 26:94e26bcd229d | 641 | if(borrow) |
feb11 | 26:94e26bcd229d | 642 | { |
feb11 | 26:94e26bcd229d | 643 | if(tmpA == 0) |
feb11 | 26:94e26bcd229d | 644 | tmpA = 0xFFFFFFFF; |
feb11 | 26:94e26bcd229d | 645 | else |
feb11 | 26:94e26bcd229d | 646 | { |
feb11 | 26:94e26bcd229d | 647 | --tmpA; |
feb11 | 26:94e26bcd229d | 648 | borrow = 0; |
feb11 | 26:94e26bcd229d | 649 | } |
feb11 | 26:94e26bcd229d | 650 | } |
feb11 | 26:94e26bcd229d | 651 | if(tmpA >= tmpB) |
feb11 | 26:94e26bcd229d | 652 | result.bits[i] = tmpA - tmpB; |
feb11 | 26:94e26bcd229d | 653 | else |
feb11 | 26:94e26bcd229d | 654 | { |
feb11 | 26:94e26bcd229d | 655 | result.bits[i] = 0xFFFFFFFF - tmpB; |
feb11 | 26:94e26bcd229d | 656 | result.bits[i] += tmpA + 1; |
feb11 | 26:94e26bcd229d | 657 | borrow = 1; |
feb11 | 26:94e26bcd229d | 658 | } |
feb11 | 26:94e26bcd229d | 659 | } |
feb11 | 26:94e26bcd229d | 660 | result.trim(); |
feb11 | 26:94e26bcd229d | 661 | result.checkZero(); |
feb11 | 26:94e26bcd229d | 662 | |
feb11 | 26:94e26bcd229d | 663 | return result; |
feb11 | 26:94e26bcd229d | 664 | } |
feb11 | 26:94e26bcd229d | 665 | |
feb11 | 26:94e26bcd229d | 666 | BigInt mul(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 667 | { |
feb11 | 26:94e26bcd229d | 668 | BigInt result; |
feb11 | 26:94e26bcd229d | 669 | result.size = a.size + b.size; |
feb11 | 26:94e26bcd229d | 670 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 26:94e26bcd229d | 671 | memset(result.bits, 0, sizeof(uint32_t)*num(result.size)); |
feb11 | 26:94e26bcd229d | 672 | for(int i = 0; i < (int)num(a.size); ++i) |
feb11 | 26:94e26bcd229d | 673 | { |
feb11 | 26:94e26bcd229d | 674 | uint64_t carry = 0; |
feb11 | 26:94e26bcd229d | 675 | for(int j = 0; j < (int)num(b.size); ++j) |
feb11 | 26:94e26bcd229d | 676 | { |
feb11 | 26:94e26bcd229d | 677 | uint64_t tmp = (uint64_t)a.bits[i] * (uint64_t)b.bits[j] + carry; |
feb11 | 26:94e26bcd229d | 678 | uint32_t t = result.bits[i+j]; |
feb11 | 26:94e26bcd229d | 679 | result.bits[i+j] += tmp; |
feb11 | 26:94e26bcd229d | 680 | carry = tmp >> 32; |
feb11 | 26:94e26bcd229d | 681 | if(t > result.bits[i+j]) |
feb11 | 26:94e26bcd229d | 682 | ++carry; |
feb11 | 26:94e26bcd229d | 683 | } |
feb11 | 26:94e26bcd229d | 684 | if(carry != 0) |
feb11 | 26:94e26bcd229d | 685 | result.bits[i+num(b.size)] += carry; |
feb11 | 26:94e26bcd229d | 686 | } |
feb11 | 26:94e26bcd229d | 687 | |
feb11 | 26:94e26bcd229d | 688 | result.trim(); |
feb11 | 26:94e26bcd229d | 689 | |
feb11 | 26:94e26bcd229d | 690 | return result; |
feb11 | 26:94e26bcd229d | 691 | } |
feb11 | 26:94e26bcd229d | 692 | |
feb11 | 26:94e26bcd229d | 693 | BigInt div(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 694 | { |
feb11 | 26:94e26bcd229d | 695 | BigInt u = a; |
feb11 | 26:94e26bcd229d | 696 | const uint32_t m = a.numBits() - b.numBits(); |
feb11 | 26:94e26bcd229d | 697 | BigInt q; |
feb11 | 26:94e26bcd229d | 698 | q.size = m/8 + 1; |
feb11 | 26:94e26bcd229d | 699 | q.bits = new uint32_t[num(q.size)]; |
feb11 | 26:94e26bcd229d | 700 | memset(q.bits, 0, num(q.size)*sizeof(uint32_t)); |
feb11 | 26:94e26bcd229d | 701 | BigInt tmp = b; |
feb11 | 26:94e26bcd229d | 702 | tmp <<= m; |
feb11 | 26:94e26bcd229d | 703 | for(int j = m; j >= 0; --j) |
feb11 | 26:94e26bcd229d | 704 | { |
feb11 | 26:94e26bcd229d | 705 | if(tmp <= u) |
feb11 | 26:94e26bcd229d | 706 | { |
feb11 | 26:94e26bcd229d | 707 | u -= tmp; |
feb11 | 26:94e26bcd229d | 708 | q.bits[j/32] |= BITS[j%32]; |
feb11 | 26:94e26bcd229d | 709 | } |
feb11 | 26:94e26bcd229d | 710 | tmp >>= 1; |
feb11 | 26:94e26bcd229d | 711 | } |
feb11 | 26:94e26bcd229d | 712 | q.trim(); |
feb11 | 26:94e26bcd229d | 713 | |
feb11 | 26:94e26bcd229d | 714 | return q; |
feb11 | 26:94e26bcd229d | 715 | } |
feb11 | 26:94e26bcd229d | 716 | |
feb11 | 26:94e26bcd229d | 717 | bool equals(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 718 | { |
feb11 | 26:94e26bcd229d | 719 | if(a.size != b.size) |
feb11 | 26:94e26bcd229d | 720 | return false; |
feb11 | 26:94e26bcd229d | 721 | |
feb11 | 26:94e26bcd229d | 722 | uint32_t l = num(a.size); |
feb11 | 26:94e26bcd229d | 723 | for(int i = 0; i < (int)l; ++i) |
feb11 | 26:94e26bcd229d | 724 | if(a.bits[i] != b.bits[i]) |
feb11 | 26:94e26bcd229d | 725 | return false; |
feb11 | 26:94e26bcd229d | 726 | return true; |
feb11 | 26:94e26bcd229d | 727 | } |
feb11 | 26:94e26bcd229d | 728 | |
feb11 | 26:94e26bcd229d | 729 | bool lesser(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 730 | { |
feb11 | 26:94e26bcd229d | 731 | if(a.size < b.size) |
feb11 | 26:94e26bcd229d | 732 | return true; |
feb11 | 26:94e26bcd229d | 733 | if(a.size > b.size) |
feb11 | 26:94e26bcd229d | 734 | return false; |
feb11 | 26:94e26bcd229d | 735 | |
feb11 | 26:94e26bcd229d | 736 | uint32_t l = num(a.size); |
feb11 | 26:94e26bcd229d | 737 | for(int i = l-1; i >= 0; --i) |
feb11 | 26:94e26bcd229d | 738 | { |
feb11 | 26:94e26bcd229d | 739 | if(a.bits[i] < b.bits[i]) |
feb11 | 26:94e26bcd229d | 740 | return true; |
feb11 | 26:94e26bcd229d | 741 | else if(a.bits[i] > b.bits[i]) |
feb11 | 26:94e26bcd229d | 742 | return false; |
feb11 | 26:94e26bcd229d | 743 | } |
feb11 | 26:94e26bcd229d | 744 | return false; |
feb11 | 26:94e26bcd229d | 745 | } |
feb11 | 26:94e26bcd229d | 746 | |
feb11 | 26:94e26bcd229d | 747 | bool greater(const BigInt &a, const BigInt &b) |
feb11 | 26:94e26bcd229d | 748 | { |
feb11 | 26:94e26bcd229d | 749 | if(a.size > b.size) |
feb11 | 26:94e26bcd229d | 750 | return true; |
feb11 | 26:94e26bcd229d | 751 | if(a.size < b.size) |
feb11 | 26:94e26bcd229d | 752 | return false; |
feb11 | 26:94e26bcd229d | 753 | uint32_t l = num(a.size); |
feb11 | 26:94e26bcd229d | 754 | for(int i = l-1; i >= 0; --i) |
feb11 | 26:94e26bcd229d | 755 | { |
feb11 | 26:94e26bcd229d | 756 | if(a.bits[i] > b.bits[i]) |
feb11 | 26:94e26bcd229d | 757 | return true; |
feb11 | 26:94e26bcd229d | 758 | else if(a.bits[i] < b.bits[i]) |
feb11 | 26:94e26bcd229d | 759 | return false; |
feb11 | 26:94e26bcd229d | 760 | } |
feb11 | 26:94e26bcd229d | 761 | return false; |
feb11 | 26:94e26bcd229d | 762 | } |
feb11 | 26:94e26bcd229d | 763 | |
feb11 | 26:94e26bcd229d | 764 | |
feb11 | 26:94e26bcd229d | 765 | void BigInt::fastAdd(const BigInt &b) |
feb11 | 24:a3453a18388c | 766 | { |
feb11 | 24:a3453a18388c | 767 | uint32_t al = num(size); |
feb11 | 24:a3453a18388c | 768 | uint32_t bl = num(b.size); |
feb11 | 24:a3453a18388c | 769 | uint32_t rsize = std::max(size, b.size) + 1; |
feb11 | 24:a3453a18388c | 770 | size_t l = num(rsize); |
feb11 | 24:a3453a18388c | 771 | |
feb11 | 24:a3453a18388c | 772 | if(l > al) |
feb11 | 24:a3453a18388c | 773 | { |
feb11 | 24:a3453a18388c | 774 | bits = (uint32_t*)realloc(bits, sizeof(uint32_t)*l); |
feb11 | 24:a3453a18388c | 775 | memset(&bits[al], 0, (l-al)*sizeof(uint32_t)); |
feb11 | 24:a3453a18388c | 776 | size = rsize; |
feb11 | 24:a3453a18388c | 777 | } |
feb11 | 24:a3453a18388c | 778 | |
feb11 | 24:a3453a18388c | 779 | uint32_t carry = 0; |
feb11 | 25:3d5c1f299da2 | 780 | for(int i = 0; i < (int)l; ++i) |
feb11 | 24:a3453a18388c | 781 | { |
feb11 | 24:a3453a18388c | 782 | uint32_t tmpA = 0, tmpB = 0; |
feb11 | 25:3d5c1f299da2 | 783 | if(i < (int)al) |
feb11 | 24:a3453a18388c | 784 | tmpA = bits[i]; |
feb11 | 25:3d5c1f299da2 | 785 | if(i < (int)bl) |
feb11 | 24:a3453a18388c | 786 | tmpB = b.bits[i]; |
feb11 | 24:a3453a18388c | 787 | bits[i] = tmpA + tmpB + carry; |
feb11 | 24:a3453a18388c | 788 | carry = bits[i] < std::max(tmpA, tmpB); |
feb11 | 24:a3453a18388c | 789 | } |
feb11 | 24:a3453a18388c | 790 | |
feb11 | 24:a3453a18388c | 791 | trim(); |
feb11 | 24:a3453a18388c | 792 | } |
feb11 | 24:a3453a18388c | 793 | |
feb11 | 26:94e26bcd229d | 794 | void BigInt::fastShr() |
feb11 | 24:a3453a18388c | 795 | { |
feb11 | 24:a3453a18388c | 796 | uint32_t lastBit = 0; |
feb11 | 24:a3453a18388c | 797 | uint32_t tmp; |
feb11 | 24:a3453a18388c | 798 | for(int i = num(size)-1; i >= 0; --i) |
feb11 | 24:a3453a18388c | 799 | { |
feb11 | 24:a3453a18388c | 800 | tmp = bits[i] & BITS[0]; |
feb11 | 24:a3453a18388c | 801 | bits[i] >>= 1; |
feb11 | 24:a3453a18388c | 802 | bits[i] |= (lastBit ? BITS[31] : 0); |
feb11 | 24:a3453a18388c | 803 | lastBit = tmp; |
feb11 | 24:a3453a18388c | 804 | } |
feb11 | 24:a3453a18388c | 805 | |
feb11 | 24:a3453a18388c | 806 | trim(); |
feb11 | 24:a3453a18388c | 807 | } |
feb11 | 24:a3453a18388c | 808 | |
feb11 | 9:3c191fa04f6e | 809 | void BigInt::trim() |
feb11 | 9:3c191fa04f6e | 810 | { |
feb11 | 20:d747159d77c4 | 811 | assert(isValid()); |
feb11 | 26:94e26bcd229d | 812 | |
feb11 | 20:d747159d77c4 | 813 | |
feb11 | 9:3c191fa04f6e | 814 | uint8_t *tmp = (uint8_t*)bits; |
feb11 | 9:3c191fa04f6e | 815 | uint32_t newSize = size; |
feb11 | 20:d747159d77c4 | 816 | while(newSize > 0 && tmp[newSize-1] == 0) |
feb11 | 9:3c191fa04f6e | 817 | newSize--; |
feb11 | 10:116e201f7d89 | 818 | if(newSize == 0) |
feb11 | 10:116e201f7d89 | 819 | newSize = 1; |
feb11 | 24:a3453a18388c | 820 | uint32_t n = num(newSize); |
feb11 | 24:a3453a18388c | 821 | if(n < num(size)) |
feb11 | 10:116e201f7d89 | 822 | { |
feb11 | 24:a3453a18388c | 823 | bits = (uint32_t*)realloc(bits, n*sizeof(uint32_t)); |
feb11 | 24:a3453a18388c | 824 | if(newSize % 4 != 0) |
feb11 | 24:a3453a18388c | 825 | bits[n-1] &= BITS2[newSize%4]; |
feb11 | 10:116e201f7d89 | 826 | } |
feb11 | 9:3c191fa04f6e | 827 | size = newSize; |
feb11 | 9:3c191fa04f6e | 828 | } |
feb11 | 9:3c191fa04f6e | 829 | |
feb11 | 11:2f16a220ebbb | 830 | uint32_t BigInt::numBits() const |
feb11 | 10:116e201f7d89 | 831 | { |
feb11 | 10:116e201f7d89 | 832 | assert(isValid()); |
feb11 | 12:a436f15b58b6 | 833 | |
feb11 | 10:116e201f7d89 | 834 | uint32_t n = (size-1)*8; |
feb11 | 11:2f16a220ebbb | 835 | uint8_t a = bits[num(size)-1] >> ((size-1)%4)*8; |
feb11 | 10:116e201f7d89 | 836 | uint8_t tmp2 = 8; |
feb11 | 11:2f16a220ebbb | 837 | while(!(a & 0x80)) |
feb11 | 10:116e201f7d89 | 838 | { |
feb11 | 11:2f16a220ebbb | 839 | a <<= 1; |
feb11 | 10:116e201f7d89 | 840 | --tmp2; |
feb11 | 10:116e201f7d89 | 841 | } |
feb11 | 10:116e201f7d89 | 842 | n += tmp2; |
feb11 | 10:116e201f7d89 | 843 | |
feb11 | 10:116e201f7d89 | 844 | return n; |
feb11 | 26:94e26bcd229d | 845 | } |
feb11 | 26:94e26bcd229d | 846 | |
feb11 | 26:94e26bcd229d | 847 | // Ensure that there is no negative zero |
feb11 | 26:94e26bcd229d | 848 | void BigInt::checkZero() |
feb11 | 26:94e26bcd229d | 849 | { |
feb11 | 26:94e26bcd229d | 850 | assert(isValid()); |
feb11 | 26:94e26bcd229d | 851 | |
feb11 | 26:94e26bcd229d | 852 | if(size == 1 && bits[0] == 0) |
feb11 | 26:94e26bcd229d | 853 | sign = POS; |
feb11 | 26:94e26bcd229d | 854 | } |