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@13:d0b4d7cfeb98, 2014-03-06 (annotated)
- Committer:
- feb11
- Date:
- Thu Mar 06 11:17:10 2014 +0000
- Revision:
- 13:d0b4d7cfeb98
- Parent:
- 12:a436f15b58b6
- Child:
- 14:5a1852dac7f7
minor changes
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 | 0:9d554894785b | 10 | static uint32_t num(const uint32_t a) |
feb11 | 0:9d554894785b | 11 | { |
feb11 | 0:9d554894785b | 12 | return a/4 + (a%4 ? 1:0); |
feb11 | 0:9d554894785b | 13 | } |
feb11 | 10:116e201f7d89 | 14 | |
feb11 | 10:116e201f7d89 | 15 | |
feb11 | 0:9d554894785b | 16 | BigInt::BigInt(): |
feb11 | 0:9d554894785b | 17 | size(0), |
feb11 | 0:9d554894785b | 18 | bits(0) |
feb11 | 0:9d554894785b | 19 | { |
feb11 | 0:9d554894785b | 20 | } |
feb11 | 0:9d554894785b | 21 | |
feb11 | 2:1001793a090d | 22 | BigInt::BigInt(const uint32_t a) |
feb11 | 2:1001793a090d | 23 | { |
feb11 | 2:1001793a090d | 24 | if(a >> 24) |
feb11 | 2:1001793a090d | 25 | size = 4; |
feb11 | 2:1001793a090d | 26 | else if(a >> 16) |
feb11 | 2:1001793a090d | 27 | size = 3; |
feb11 | 2:1001793a090d | 28 | else if(a >> 8) |
feb11 | 2:1001793a090d | 29 | size = 2; |
feb11 | 2:1001793a090d | 30 | else |
feb11 | 2:1001793a090d | 31 | size = 1; |
feb11 | 2:1001793a090d | 32 | bits = new uint32_t[1]; |
feb11 | 2:1001793a090d | 33 | bits[0] = a; |
feb11 | 2:1001793a090d | 34 | } |
feb11 | 2:1001793a090d | 35 | |
feb11 | 0:9d554894785b | 36 | BigInt::BigInt(const BigInt &a): |
feb11 | 0:9d554894785b | 37 | size(a.size) |
feb11 | 0:9d554894785b | 38 | { |
feb11 | 0:9d554894785b | 39 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 40 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 41 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 42 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 43 | } |
feb11 | 0:9d554894785b | 44 | |
feb11 | 0:9d554894785b | 45 | |
feb11 | 0:9d554894785b | 46 | BigInt::~BigInt() |
feb11 | 0:9d554894785b | 47 | { |
feb11 | 10:116e201f7d89 | 48 | if(size) |
feb11 | 9:3c191fa04f6e | 49 | { |
feb11 | 0:9d554894785b | 50 | delete[] bits; |
feb11 | 9:3c191fa04f6e | 51 | } |
feb11 | 0:9d554894785b | 52 | } |
feb11 | 0:9d554894785b | 53 | |
feb11 | 0:9d554894785b | 54 | BigInt& BigInt::operator=(const BigInt& a) |
feb11 | 0:9d554894785b | 55 | { |
feb11 | 0:9d554894785b | 56 | size = a.size; |
feb11 | 0:9d554894785b | 57 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 58 | if(bits) |
feb11 | 0:9d554894785b | 59 | delete[] bits; |
feb11 | 0:9d554894785b | 60 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 61 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 62 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 63 | return *this; |
feb11 | 0:9d554894785b | 64 | } |
feb11 | 0:9d554894785b | 65 | |
feb11 | 13:d0b4d7cfeb98 | 66 | void BigInt::importData(uint8_t *data, uint32_t length) |
feb11 | 0:9d554894785b | 67 | { |
feb11 | 0:9d554894785b | 68 | size = length; |
feb11 | 0:9d554894785b | 69 | size_t l = size/4; |
feb11 | 0:9d554894785b | 70 | if(size % 4 != 0) |
feb11 | 0:9d554894785b | 71 | l++; |
feb11 | 0:9d554894785b | 72 | if(bits) |
feb11 | 0:9d554894785b | 73 | delete[] bits; |
feb11 | 0:9d554894785b | 74 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 75 | memset(bits, 0, sizeof(uint32_t)*l); |
feb11 | 4:773aed3156c5 | 76 | for(int i = length-1; i >=0; --i) |
feb11 | 0:9d554894785b | 77 | bits[i/4] |= data[i] << ((i%4)*8); |
feb11 | 0:9d554894785b | 78 | } |
feb11 | 0:9d554894785b | 79 | |
feb11 | 13:d0b4d7cfeb98 | 80 | void BigInt::exportData(uint8_t *data, uint32_t length) |
feb11 | 13:d0b4d7cfeb98 | 81 | { |
feb11 | 13:d0b4d7cfeb98 | 82 | assert(isValid() && data != 0); |
feb11 | 13:d0b4d7cfeb98 | 83 | |
feb11 | 13:d0b4d7cfeb98 | 84 | } |
feb11 | 13:d0b4d7cfeb98 | 85 | |
feb11 | 0:9d554894785b | 86 | BigInt operator+(const BigInt &a, const BigInt& b) |
feb11 | 0:9d554894785b | 87 | { |
feb11 | 9:3c191fa04f6e | 88 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 89 | |
feb11 | 0:9d554894785b | 90 | BigInt result; |
feb11 | 9:3c191fa04f6e | 91 | |
feb11 | 0:9d554894785b | 92 | result.size = a.size > b.size ? a.size : b.size; |
feb11 | 0:9d554894785b | 93 | size_t l = result.size/4; |
feb11 | 0:9d554894785b | 94 | if(result.size % 4 != 0) |
feb11 | 0:9d554894785b | 95 | l++; |
feb11 | 0:9d554894785b | 96 | result.bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 97 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 0:9d554894785b | 98 | uint32_t al = num(a.size); |
feb11 | 0:9d554894785b | 99 | uint32_t bl = num(b.size); |
feb11 | 0:9d554894785b | 100 | uint32_t carry = 0; |
feb11 | 0:9d554894785b | 101 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 102 | { |
feb11 | 0:9d554894785b | 103 | uint32_t tmpA = 0, tmpB = 0; |
feb11 | 0:9d554894785b | 104 | if(i < al) |
feb11 | 0:9d554894785b | 105 | tmpA = a.bits[i]; |
feb11 | 0:9d554894785b | 106 | if(i < bl) |
feb11 | 0:9d554894785b | 107 | tmpB = b.bits[i]; |
feb11 | 0:9d554894785b | 108 | result.bits[i] = tmpA + tmpB + carry; |
feb11 | 10:116e201f7d89 | 109 | carry = result.bits[i] < std::max(tmpA, tmpB); |
feb11 | 0:9d554894785b | 110 | } |
feb11 | 0:9d554894785b | 111 | if(carry) |
feb11 | 0:9d554894785b | 112 | { |
feb11 | 0:9d554894785b | 113 | result.size++; |
feb11 | 0:9d554894785b | 114 | if(result.size > l*4) |
feb11 | 0:9d554894785b | 115 | { |
feb11 | 0:9d554894785b | 116 | l++; |
feb11 | 0:9d554894785b | 117 | result.bits = (uint32_t*)realloc(result.bits, l * sizeof(uint32_t)); |
feb11 | 0:9d554894785b | 118 | result.bits[l-1] = 0x00000001; |
feb11 | 0:9d554894785b | 119 | } |
feb11 | 0:9d554894785b | 120 | else |
feb11 | 0:9d554894785b | 121 | { |
feb11 | 0:9d554894785b | 122 | result.bits[l-1] += 1 << (8 *((result.size-1)%4)); |
feb11 | 0:9d554894785b | 123 | } |
feb11 | 0:9d554894785b | 124 | } |
feb11 | 0:9d554894785b | 125 | |
feb11 | 0:9d554894785b | 126 | return result; |
feb11 | 0:9d554894785b | 127 | } |
feb11 | 0:9d554894785b | 128 | |
feb11 | 0:9d554894785b | 129 | BigInt& BigInt::operator+=(const BigInt &b) |
feb11 | 0:9d554894785b | 130 | { |
feb11 | 0:9d554894785b | 131 | return (*this = (*this) + b); |
feb11 | 0:9d554894785b | 132 | } |
feb11 | 0:9d554894785b | 133 | |
feb11 | 0:9d554894785b | 134 | BigInt& BigInt::operator++() |
feb11 | 0:9d554894785b | 135 | { |
feb11 | 3:3fa3ceb0c69d | 136 | return (*this += 1); |
feb11 | 0:9d554894785b | 137 | } |
feb11 | 0:9d554894785b | 138 | |
feb11 | 0:9d554894785b | 139 | BigInt BigInt::operator++(int) |
feb11 | 0:9d554894785b | 140 | { |
feb11 | 0:9d554894785b | 141 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 142 | *this += 1; |
feb11 | 0:9d554894785b | 143 | return t; |
feb11 | 0:9d554894785b | 144 | } |
feb11 | 0:9d554894785b | 145 | |
feb11 | 0:9d554894785b | 146 | // a - b, if b >= a, returns 0 |
feb11 | 0:9d554894785b | 147 | // No negative number allowed |
feb11 | 0:9d554894785b | 148 | BigInt operator-(const BigInt &a, const BigInt& b) |
feb11 | 0:9d554894785b | 149 | { |
feb11 | 9:3c191fa04f6e | 150 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 151 | |
feb11 | 0:9d554894785b | 152 | BigInt result; |
feb11 | 0:9d554894785b | 153 | |
feb11 | 0:9d554894785b | 154 | if(b >= a) |
feb11 | 0:9d554894785b | 155 | { |
feb11 | 3:3fa3ceb0c69d | 156 | return result = 0; |
feb11 | 0:9d554894785b | 157 | } |
feb11 | 0:9d554894785b | 158 | else |
feb11 | 0:9d554894785b | 159 | { |
feb11 | 0:9d554894785b | 160 | result.size = a.size; |
feb11 | 0:9d554894785b | 161 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 162 | result.bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 163 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 0:9d554894785b | 164 | uint32_t bl = num(b.size); |
feb11 | 0:9d554894785b | 165 | uint8_t borrow = 0; |
feb11 | 0:9d554894785b | 166 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 167 | { |
feb11 | 0:9d554894785b | 168 | uint32_t tmpA = a.bits[i], tmpB = 0; |
feb11 | 0:9d554894785b | 169 | if(i < bl) |
feb11 | 0:9d554894785b | 170 | tmpB = b.bits[i]; |
feb11 | 0:9d554894785b | 171 | if(borrow) |
feb11 | 0:9d554894785b | 172 | { |
feb11 | 0:9d554894785b | 173 | if(tmpA == 0) |
feb11 | 0:9d554894785b | 174 | tmpA = ULONG_MAX; |
feb11 | 0:9d554894785b | 175 | else |
feb11 | 0:9d554894785b | 176 | --tmpA; |
feb11 | 0:9d554894785b | 177 | |
feb11 | 0:9d554894785b | 178 | if(tmpA < tmpB) |
feb11 | 0:9d554894785b | 179 | result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB); |
feb11 | 0:9d554894785b | 180 | else |
feb11 | 0:9d554894785b | 181 | result.bits[i] = tmpA - tmpB; |
feb11 | 0:9d554894785b | 182 | |
feb11 | 0:9d554894785b | 183 | if(a.bits[i] != 0 && tmpA > tmpB) |
feb11 | 0:9d554894785b | 184 | borrow = 0; |
feb11 | 0:9d554894785b | 185 | } |
feb11 | 0:9d554894785b | 186 | else |
feb11 | 0:9d554894785b | 187 | { |
feb11 | 0:9d554894785b | 188 | if(tmpA < tmpB) |
feb11 | 0:9d554894785b | 189 | result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB); |
feb11 | 0:9d554894785b | 190 | else |
feb11 | 0:9d554894785b | 191 | result.bits[i] = tmpA - tmpB; |
feb11 | 0:9d554894785b | 192 | borrow = tmpA < tmpB; |
feb11 | 0:9d554894785b | 193 | } |
feb11 | 0:9d554894785b | 194 | } |
feb11 | 0:9d554894785b | 195 | |
feb11 | 9:3c191fa04f6e | 196 | result.trim(); |
feb11 | 0:9d554894785b | 197 | |
feb11 | 0:9d554894785b | 198 | return result; |
feb11 | 0:9d554894785b | 199 | } |
feb11 | 0:9d554894785b | 200 | } |
feb11 | 0:9d554894785b | 201 | |
feb11 | 0:9d554894785b | 202 | BigInt& BigInt::operator-=(const BigInt &b) |
feb11 | 0:9d554894785b | 203 | { |
feb11 | 0:9d554894785b | 204 | return (*this = (*this) - b); |
feb11 | 0:9d554894785b | 205 | } |
feb11 | 0:9d554894785b | 206 | |
feb11 | 0:9d554894785b | 207 | BigInt& BigInt::operator--() |
feb11 | 0:9d554894785b | 208 | { |
feb11 | 3:3fa3ceb0c69d | 209 | return (*this -= 1); |
feb11 | 0:9d554894785b | 210 | } |
feb11 | 0:9d554894785b | 211 | |
feb11 | 0:9d554894785b | 212 | BigInt BigInt::operator--(int) |
feb11 | 0:9d554894785b | 213 | { |
feb11 | 0:9d554894785b | 214 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 215 | *this -= 1; |
feb11 | 0:9d554894785b | 216 | return t; |
feb11 | 0:9d554894785b | 217 | } |
feb11 | 3:3fa3ceb0c69d | 218 | |
feb11 | 1:00f2c40d46ed | 219 | BigInt operator*(const BigInt &a, const BigInt& b) |
feb11 | 1:00f2c40d46ed | 220 | { |
feb11 | 9:3c191fa04f6e | 221 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 222 | |
feb11 | 1:00f2c40d46ed | 223 | // if a == 0 or b == 0 then result = 0 |
feb11 | 1:00f2c40d46ed | 224 | if(!a || !b) |
feb11 | 12:a436f15b58b6 | 225 | return 0; |
feb11 | 1:00f2c40d46ed | 226 | |
feb11 | 1:00f2c40d46ed | 227 | // if a == 1, then result = b |
feb11 | 3:3fa3ceb0c69d | 228 | if(a == 1) |
feb11 | 12:a436f15b58b6 | 229 | return b; |
feb11 | 1:00f2c40d46ed | 230 | |
feb11 | 1:00f2c40d46ed | 231 | // if b == 1, then result = a |
feb11 | 3:3fa3ceb0c69d | 232 | if(b == 1) |
feb11 | 12:a436f15b58b6 | 233 | return a; |
feb11 | 12:a436f15b58b6 | 234 | |
feb11 | 12:a436f15b58b6 | 235 | BigInt result; |
feb11 | 4:773aed3156c5 | 236 | result.size = a.size + b.size; |
feb11 | 4:773aed3156c5 | 237 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 12:a436f15b58b6 | 238 | memset(result.bits, 0, sizeof(uint32_t)*num(result.size)); |
feb11 | 11:2f16a220ebbb | 239 | for(int i = 0; i < num(a.size); ++i) |
feb11 | 4:773aed3156c5 | 240 | { |
feb11 | 11:2f16a220ebbb | 241 | uint64_t carry = 0; |
feb11 | 11:2f16a220ebbb | 242 | for(int j = 0; j < num(b.size); ++j) |
feb11 | 11:2f16a220ebbb | 243 | { |
feb11 | 11:2f16a220ebbb | 244 | uint64_t tmp = (uint64_t)a.bits[i] * (uint64_t)b.bits[j] + carry; |
feb11 | 12:a436f15b58b6 | 245 | uint32_t t = result.bits[i+j]; |
feb11 | 11:2f16a220ebbb | 246 | result.bits[i+j] += tmp; |
feb11 | 12:a436f15b58b6 | 247 | carry = tmp >> 32; |
feb11 | 12:a436f15b58b6 | 248 | if(t > result.bits[i+j]) |
feb11 | 12:a436f15b58b6 | 249 | ++carry; |
feb11 | 11:2f16a220ebbb | 250 | } |
feb11 | 11:2f16a220ebbb | 251 | if(carry != 0) |
feb11 | 11:2f16a220ebbb | 252 | result.bits[i+num(b.size)] += carry; |
feb11 | 4:773aed3156c5 | 253 | } |
feb11 | 4:773aed3156c5 | 254 | |
feb11 | 9:3c191fa04f6e | 255 | result.trim(); |
feb11 | 1:00f2c40d46ed | 256 | |
feb11 | 1:00f2c40d46ed | 257 | return result; |
feb11 | 1:00f2c40d46ed | 258 | } |
feb11 | 1:00f2c40d46ed | 259 | |
feb11 | 1:00f2c40d46ed | 260 | BigInt& BigInt::operator*=(const BigInt &b) |
feb11 | 1:00f2c40d46ed | 261 | { |
feb11 | 1:00f2c40d46ed | 262 | return (*this = (*this) * b); |
feb11 | 1:00f2c40d46ed | 263 | } |
feb11 | 1:00f2c40d46ed | 264 | |
feb11 | 10:116e201f7d89 | 265 | |
feb11 | 11:2f16a220ebbb | 266 | BigInt operator/(const BigInt &a, const BigInt &b) |
feb11 | 10:116e201f7d89 | 267 | { |
feb11 | 10:116e201f7d89 | 268 | assert(a.isValid() && b.isValid() && b != 0); |
feb11 | 10:116e201f7d89 | 269 | if(b == 1) |
feb11 | 10:116e201f7d89 | 270 | return a; |
feb11 | 10:116e201f7d89 | 271 | if(a < b) |
feb11 | 10:116e201f7d89 | 272 | return 0; |
feb11 | 10:116e201f7d89 | 273 | if(a == b) |
feb11 | 10:116e201f7d89 | 274 | return 1; |
feb11 | 11:2f16a220ebbb | 275 | BigInt u = a; |
feb11 | 11:2f16a220ebbb | 276 | int m = a.numBits() - b.numBits(); |
feb11 | 10:116e201f7d89 | 277 | BigInt q = 0; |
feb11 | 12:a436f15b58b6 | 278 | BigInt tmp = b; |
feb11 | 12:a436f15b58b6 | 279 | tmp <<= m; |
feb11 | 10:116e201f7d89 | 280 | for(int j = m; j >= 0; --j) |
feb11 | 10:116e201f7d89 | 281 | { |
feb11 | 11:2f16a220ebbb | 282 | if(tmp <= u) |
feb11 | 10:116e201f7d89 | 283 | { |
feb11 | 11:2f16a220ebbb | 284 | u -= tmp; |
feb11 | 11:2f16a220ebbb | 285 | BigInt tmp2 = 1; |
feb11 | 11:2f16a220ebbb | 286 | tmp2 <<= j; |
feb11 | 12:a436f15b58b6 | 287 | q += tmp2; |
feb11 | 10:116e201f7d89 | 288 | } |
feb11 | 10:116e201f7d89 | 289 | tmp >>= 1; |
feb11 | 10:116e201f7d89 | 290 | } |
feb11 | 11:2f16a220ebbb | 291 | q.trim(); |
feb11 | 11:2f16a220ebbb | 292 | return q; |
feb11 | 10:116e201f7d89 | 293 | } |
feb11 | 10:116e201f7d89 | 294 | |
feb11 | 10:116e201f7d89 | 295 | BigInt& BigInt::operator/=(const BigInt &b) |
feb11 | 10:116e201f7d89 | 296 | { |
feb11 | 10:116e201f7d89 | 297 | return (*this = (*this) / b); |
feb11 | 10:116e201f7d89 | 298 | } |
feb11 | 10:116e201f7d89 | 299 | |
feb11 | 1:00f2c40d46ed | 300 | BigInt operator>>(const BigInt &a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 301 | { |
feb11 | 9:3c191fa04f6e | 302 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 303 | |
feb11 | 12:a436f15b58b6 | 304 | if(m == 0) |
feb11 | 12:a436f15b58b6 | 305 | return a; |
feb11 | 12:a436f15b58b6 | 306 | if(m/8 >= a.size) |
feb11 | 12:a436f15b58b6 | 307 | return 0; |
feb11 | 12:a436f15b58b6 | 308 | |
feb11 | 1:00f2c40d46ed | 309 | BigInt result; |
feb11 | 1:00f2c40d46ed | 310 | result.size = a.size - m/8; |
feb11 | 1:00f2c40d46ed | 311 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 1:00f2c40d46ed | 312 | uint8_t s = m%32; |
feb11 | 1:00f2c40d46ed | 313 | for(uint32_t i = 0; i < num(result.size); ++i) |
feb11 | 1:00f2c40d46ed | 314 | { |
feb11 | 1:00f2c40d46ed | 315 | if(m/32+i+1 < num(a.size)) |
feb11 | 1:00f2c40d46ed | 316 | result.bits[i] = (a.bits[m/32+i+1] << (32-s)) | (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 317 | else |
feb11 | 1:00f2c40d46ed | 318 | result.bits[i] = (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 319 | } |
feb11 | 1:00f2c40d46ed | 320 | |
feb11 | 10:116e201f7d89 | 321 | result.trim(); |
feb11 | 10:116e201f7d89 | 322 | |
feb11 | 1:00f2c40d46ed | 323 | return result; |
feb11 | 1:00f2c40d46ed | 324 | } |
feb11 | 1:00f2c40d46ed | 325 | |
feb11 | 1:00f2c40d46ed | 326 | BigInt& BigInt::operator>>=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 327 | { |
feb11 | 1:00f2c40d46ed | 328 | return *this = *this >> m; |
feb11 | 1:00f2c40d46ed | 329 | } |
feb11 | 1:00f2c40d46ed | 330 | |
feb11 | 1:00f2c40d46ed | 331 | BigInt operator<<(const BigInt &a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 332 | { |
feb11 | 9:3c191fa04f6e | 333 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 334 | |
feb11 | 1:00f2c40d46ed | 335 | BigInt result; |
feb11 | 9:3c191fa04f6e | 336 | |
feb11 | 1:00f2c40d46ed | 337 | if(m == 0) |
feb11 | 1:00f2c40d46ed | 338 | return result = a; |
feb11 | 1:00f2c40d46ed | 339 | |
feb11 | 1:00f2c40d46ed | 340 | result.size = m/8 + a.size; |
feb11 | 1:00f2c40d46ed | 341 | uint32_t h = a.bits[num(a.size)-1]; |
feb11 | 12:a436f15b58b6 | 342 | if((m%32)%8 != 0) |
feb11 | 1:00f2c40d46ed | 343 | ++result.size; |
feb11 | 1:00f2c40d46ed | 344 | uint32_t l = num(result.size); |
feb11 | 1:00f2c40d46ed | 345 | result.bits = new uint32_t[l]; |
feb11 | 1:00f2c40d46ed | 346 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 1:00f2c40d46ed | 347 | uint32_t s = m % 32; |
feb11 | 1:00f2c40d46ed | 348 | for(uint32_t i = 0; i < num(a.size); ++i) |
feb11 | 1:00f2c40d46ed | 349 | { |
feb11 | 1:00f2c40d46ed | 350 | if(i == 0) |
feb11 | 1:00f2c40d46ed | 351 | result.bits[m/32+i] = a.bits[i] << s; |
feb11 | 1:00f2c40d46ed | 352 | else |
feb11 | 1:00f2c40d46ed | 353 | result.bits[m/32+i] = (a.bits[i] << s) | (a.bits[i-1] >> (32-s)); |
feb11 | 1:00f2c40d46ed | 354 | } |
feb11 | 12:a436f15b58b6 | 355 | if(a.bits[num(a.size)-1] && s != 0) |
feb11 | 12:a436f15b58b6 | 356 | result.bits[m/32+num(result.size)-1] |= a.bits[num(a.size)-1] >> (32-s); |
feb11 | 1:00f2c40d46ed | 357 | |
feb11 | 12:a436f15b58b6 | 358 | result.trim(); |
feb11 | 1:00f2c40d46ed | 359 | |
feb11 | 1:00f2c40d46ed | 360 | return result; |
feb11 | 1:00f2c40d46ed | 361 | } |
feb11 | 1:00f2c40d46ed | 362 | |
feb11 | 1:00f2c40d46ed | 363 | BigInt& BigInt::operator<<=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 364 | { |
feb11 | 1:00f2c40d46ed | 365 | return (*this = *this << m); |
feb11 | 1:00f2c40d46ed | 366 | } |
feb11 | 0:9d554894785b | 367 | |
feb11 | 5:beeb31f340a7 | 368 | BigInt operator%(const BigInt &a, const BigInt &b) |
feb11 | 5:beeb31f340a7 | 369 | { |
feb11 | 10:116e201f7d89 | 370 | assert(a.isValid() && b.isValid() && b > 0); |
feb11 | 12:a436f15b58b6 | 371 | return a - (a/b)*b; |
feb11 | 5:beeb31f340a7 | 372 | } |
feb11 | 5:beeb31f340a7 | 373 | |
feb11 | 5:beeb31f340a7 | 374 | BigInt& BigInt::operator%=(const BigInt &a) |
feb11 | 5:beeb31f340a7 | 375 | { |
feb11 | 5:beeb31f340a7 | 376 | return (*this = *this % a); |
feb11 | 5:beeb31f340a7 | 377 | } |
feb11 | 5:beeb31f340a7 | 378 | |
feb11 | 0:9d554894785b | 379 | bool operator==(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 380 | { |
feb11 | 9:3c191fa04f6e | 381 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 382 | |
feb11 | 0:9d554894785b | 383 | if(a.size != b.size) |
feb11 | 0:9d554894785b | 384 | return false; |
feb11 | 0:9d554894785b | 385 | |
feb11 | 0:9d554894785b | 386 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 387 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 388 | if(a.bits[i] != b.bits[i]) |
feb11 | 0:9d554894785b | 389 | return false; |
feb11 | 0:9d554894785b | 390 | return true; |
feb11 | 0:9d554894785b | 391 | } |
feb11 | 0:9d554894785b | 392 | |
feb11 | 0:9d554894785b | 393 | bool operator!=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 394 | { |
feb11 | 0:9d554894785b | 395 | return ! (a==b); |
feb11 | 0:9d554894785b | 396 | } |
feb11 | 0:9d554894785b | 397 | |
feb11 | 0:9d554894785b | 398 | bool operator<(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 399 | { |
feb11 | 9:3c191fa04f6e | 400 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 401 | |
feb11 | 0:9d554894785b | 402 | if(a.size < b.size) |
feb11 | 0:9d554894785b | 403 | return true; |
feb11 | 0:9d554894785b | 404 | if(a.size > b.size) |
feb11 | 0:9d554894785b | 405 | return false; |
feb11 | 0:9d554894785b | 406 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 407 | for(int i = l-1; i >= 0; --i) |
feb11 | 12:a436f15b58b6 | 408 | { |
feb11 | 0:9d554894785b | 409 | if(a.bits[i] < b.bits[i]) |
feb11 | 0:9d554894785b | 410 | return true; |
feb11 | 12:a436f15b58b6 | 411 | else if(a.bits[i] > b.bits[i]) |
feb11 | 12:a436f15b58b6 | 412 | return false; |
feb11 | 12:a436f15b58b6 | 413 | } |
feb11 | 0:9d554894785b | 414 | return false; |
feb11 | 0:9d554894785b | 415 | } |
feb11 | 0:9d554894785b | 416 | |
feb11 | 0:9d554894785b | 417 | bool operator<=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 418 | { |
feb11 | 9:3c191fa04f6e | 419 | return !(a > b); |
feb11 | 0:9d554894785b | 420 | } |
feb11 | 0:9d554894785b | 421 | |
feb11 | 0:9d554894785b | 422 | bool operator>(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 423 | { |
feb11 | 9:3c191fa04f6e | 424 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 425 | |
feb11 | 0:9d554894785b | 426 | if(a.size > b.size) |
feb11 | 0:9d554894785b | 427 | return true; |
feb11 | 0:9d554894785b | 428 | if(a.size < b.size) |
feb11 | 0:9d554894785b | 429 | return false; |
feb11 | 0:9d554894785b | 430 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 431 | for(int i = l-1; i >= 0; --i) |
feb11 | 12:a436f15b58b6 | 432 | { |
feb11 | 0:9d554894785b | 433 | if(a.bits[i] > b.bits[i]) |
feb11 | 0:9d554894785b | 434 | return true; |
feb11 | 12:a436f15b58b6 | 435 | else if(a.bits[i] < b.bits[i]) |
feb11 | 12:a436f15b58b6 | 436 | return false; |
feb11 | 12:a436f15b58b6 | 437 | } |
feb11 | 0:9d554894785b | 438 | return false; |
feb11 | 0:9d554894785b | 439 | } |
feb11 | 0:9d554894785b | 440 | |
feb11 | 0:9d554894785b | 441 | bool operator>=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 442 | { |
feb11 | 9:3c191fa04f6e | 443 | return !(a < b); |
feb11 | 0:9d554894785b | 444 | } |
feb11 | 0:9d554894785b | 445 | |
feb11 | 1:00f2c40d46ed | 446 | bool operator!(const BigInt &a) |
feb11 | 0:9d554894785b | 447 | { |
feb11 | 9:3c191fa04f6e | 448 | assert(a.isValid()); |
feb11 | 9:3c191fa04f6e | 449 | |
feb11 | 1:00f2c40d46ed | 450 | if(a.size != 1) |
feb11 | 0:9d554894785b | 451 | return false; |
feb11 | 1:00f2c40d46ed | 452 | return a.bits[0] == 0; |
feb11 | 0:9d554894785b | 453 | } |
feb11 | 0:9d554894785b | 454 | |
feb11 | 7:1aad58757705 | 455 | |
feb11 | 7:1aad58757705 | 456 | BigInt operator&(const BigInt &a, const BigInt &b) |
feb11 | 7:1aad58757705 | 457 | { |
feb11 | 9:3c191fa04f6e | 458 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 459 | |
feb11 | 7:1aad58757705 | 460 | BigInt result; |
feb11 | 7:1aad58757705 | 461 | |
feb11 | 7:1aad58757705 | 462 | result.size = a.size < b.size ? a.size : b.size; |
feb11 | 7:1aad58757705 | 463 | uint32_t l = num(result.size); |
feb11 | 7:1aad58757705 | 464 | result.bits = new uint32_t[l]; |
feb11 | 7:1aad58757705 | 465 | memset(result.bits, 0, l); |
feb11 | 7:1aad58757705 | 466 | |
feb11 | 7:1aad58757705 | 467 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 7:1aad58757705 | 468 | result.bits[i] = a.bits[i] & b.bits[i]; |
feb11 | 7:1aad58757705 | 469 | |
feb11 | 9:3c191fa04f6e | 470 | result.trim(); |
feb11 | 7:1aad58757705 | 471 | |
feb11 | 7:1aad58757705 | 472 | return result; |
feb11 | 7:1aad58757705 | 473 | } |
feb11 | 7:1aad58757705 | 474 | |
feb11 | 7:1aad58757705 | 475 | BigInt& BigInt::operator&=(const BigInt &a) |
feb11 | 7:1aad58757705 | 476 | { |
feb11 | 7:1aad58757705 | 477 | return (*this = *this & a); |
feb11 | 7:1aad58757705 | 478 | } |
feb11 | 7:1aad58757705 | 479 | |
feb11 | 7:1aad58757705 | 480 | BigInt operator|(const BigInt &a, const BigInt &b) |
feb11 | 7:1aad58757705 | 481 | { |
feb11 | 9:3c191fa04f6e | 482 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 483 | |
feb11 | 7:1aad58757705 | 484 | BigInt result; |
feb11 | 7:1aad58757705 | 485 | |
feb11 | 7:1aad58757705 | 486 | uint32_t na = num(a.size); |
feb11 | 7:1aad58757705 | 487 | uint32_t nb = num(b.size); |
feb11 | 10:116e201f7d89 | 488 | uint32_t l = std::max(na,nb); |
feb11 | 10:116e201f7d89 | 489 | result.size = std::max(a.size, b.size); |
feb11 | 7:1aad58757705 | 490 | result.bits = new uint32_t[l]; |
feb11 | 7:1aad58757705 | 491 | memset(result.bits, 0, l); |
feb11 | 7:1aad58757705 | 492 | |
feb11 | 7:1aad58757705 | 493 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 7:1aad58757705 | 494 | { |
feb11 | 7:1aad58757705 | 495 | if(i < na && i < nb) |
feb11 | 7:1aad58757705 | 496 | result.bits[i] = a.bits[i] | b.bits[i]; |
feb11 | 7:1aad58757705 | 497 | else if(i < na) |
feb11 | 7:1aad58757705 | 498 | result.bits[i] = a.bits[i]; |
feb11 | 7:1aad58757705 | 499 | else |
feb11 | 7:1aad58757705 | 500 | result.bits[i] = b.bits[i]; |
feb11 | 7:1aad58757705 | 501 | } |
feb11 | 7:1aad58757705 | 502 | |
feb11 | 7:1aad58757705 | 503 | return result; |
feb11 | 7:1aad58757705 | 504 | } |
feb11 | 7:1aad58757705 | 505 | |
feb11 | 7:1aad58757705 | 506 | BigInt& BigInt::operator|=(const BigInt &a) |
feb11 | 7:1aad58757705 | 507 | { |
feb11 | 7:1aad58757705 | 508 | return (*this = *this | a); |
feb11 | 7:1aad58757705 | 509 | } |
feb11 | 8:2a361f1b41da | 510 | |
feb11 | 8:2a361f1b41da | 511 | BigInt operator^(const BigInt &a, const BigInt &b) |
feb11 | 8:2a361f1b41da | 512 | { |
feb11 | 9:3c191fa04f6e | 513 | assert(a.isValid() && b.isValid()); |
feb11 | 9:3c191fa04f6e | 514 | |
feb11 | 9:3c191fa04f6e | 515 | |
feb11 | 8:2a361f1b41da | 516 | BigInt result; |
feb11 | 8:2a361f1b41da | 517 | |
feb11 | 8:2a361f1b41da | 518 | uint32_t na = num(a.size); |
feb11 | 8:2a361f1b41da | 519 | uint32_t nb = num(b.size); |
feb11 | 10:116e201f7d89 | 520 | uint32_t l = std::max(na,nb); |
feb11 | 10:116e201f7d89 | 521 | result.size = std::max(a.size, b.size); |
feb11 | 8:2a361f1b41da | 522 | result.bits = new uint32_t[l]; |
feb11 | 8:2a361f1b41da | 523 | memset(result.bits, 0, l); |
feb11 | 7:1aad58757705 | 524 | |
feb11 | 8:2a361f1b41da | 525 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 8:2a361f1b41da | 526 | { |
feb11 | 8:2a361f1b41da | 527 | if(i < na && i < nb) |
feb11 | 8:2a361f1b41da | 528 | result.bits[i] = a.bits[i] ^ b.bits[i]; |
feb11 | 8:2a361f1b41da | 529 | else if(i < na) |
feb11 | 8:2a361f1b41da | 530 | result.bits[i] = a.bits[i]; |
feb11 | 8:2a361f1b41da | 531 | else |
feb11 | 8:2a361f1b41da | 532 | result.bits[i] = b.bits[i]; |
feb11 | 8:2a361f1b41da | 533 | } |
feb11 | 8:2a361f1b41da | 534 | |
feb11 | 9:3c191fa04f6e | 535 | result.trim(); |
feb11 | 9:3c191fa04f6e | 536 | |
feb11 | 8:2a361f1b41da | 537 | return result; |
feb11 | 8:2a361f1b41da | 538 | } |
feb11 | 8:2a361f1b41da | 539 | |
feb11 | 8:2a361f1b41da | 540 | BigInt& BigInt::operator^=(const BigInt &a) |
feb11 | 8:2a361f1b41da | 541 | { |
feb11 | 8:2a361f1b41da | 542 | return (*this = *this ^ a); |
feb11 | 8:2a361f1b41da | 543 | } |
feb11 | 9:3c191fa04f6e | 544 | |
feb11 | 10:116e201f7d89 | 545 | BigInt montgomeryStep(const BigInt &a, const BigInt &b, const BigInt &m, uint32_t r) |
feb11 | 10:116e201f7d89 | 546 | { |
feb11 | 10:116e201f7d89 | 547 | BigInt result = 0; |
feb11 | 10:116e201f7d89 | 548 | BigInt tmp = a; |
feb11 | 10:116e201f7d89 | 549 | while(r > 0) |
feb11 | 10:116e201f7d89 | 550 | { |
feb11 | 10:116e201f7d89 | 551 | if(tmp.bits[0] & 0x01) |
feb11 | 10:116e201f7d89 | 552 | result += b; |
feb11 | 10:116e201f7d89 | 553 | |
feb11 | 10:116e201f7d89 | 554 | if(result.bits[0] & 0x01) |
feb11 | 10:116e201f7d89 | 555 | result += m; |
feb11 | 10:116e201f7d89 | 556 | |
feb11 | 10:116e201f7d89 | 557 | --r; |
feb11 | 10:116e201f7d89 | 558 | result >>= 1; |
feb11 | 10:116e201f7d89 | 559 | tmp >>= 1; |
feb11 | 10:116e201f7d89 | 560 | } |
feb11 | 10:116e201f7d89 | 561 | return result; |
feb11 | 10:116e201f7d89 | 562 | } |
feb11 | 10:116e201f7d89 | 563 | |
feb11 | 10:116e201f7d89 | 564 | // Implementation using Montgomery algorithm |
feb11 | 9:3c191fa04f6e | 565 | BigInt modPow(const BigInt &a, const BigInt &expn, const BigInt &modulus) |
feb11 | 9:3c191fa04f6e | 566 | { |
feb11 | 9:3c191fa04f6e | 567 | assert(a.isValid() && expn.isValid() && modulus.isValid()); |
feb11 | 9:3c191fa04f6e | 568 | |
feb11 | 10:116e201f7d89 | 569 | // precompute R and R^2 |
feb11 | 10:116e201f7d89 | 570 | uint32_t r = 8*modulus.size; |
feb11 | 10:116e201f7d89 | 571 | |
feb11 | 10:116e201f7d89 | 572 | // convert a in montgomery world |
feb11 | 11:2f16a220ebbb | 573 | BigInt tmp2 = 1; |
feb11 | 13:d0b4d7cfeb98 | 574 | tmp2 <<= r; |
feb11 | 11:2f16a220ebbb | 575 | tmp2 *= a; |
feb11 | 12:a436f15b58b6 | 576 | BigInt montA = tmp2%modulus; |
feb11 | 10:116e201f7d89 | 577 | BigInt tmp = montA; |
feb11 | 9:3c191fa04f6e | 578 | BigInt tmpE = expn; |
feb11 | 10:116e201f7d89 | 579 | while(tmpE > 1) |
feb11 | 9:3c191fa04f6e | 580 | { |
feb11 | 10:116e201f7d89 | 581 | tmp = montgomeryStep(montA, tmp, modulus, r); |
feb11 | 10:116e201f7d89 | 582 | --tmpE; |
feb11 | 9:3c191fa04f6e | 583 | } |
feb11 | 9:3c191fa04f6e | 584 | |
feb11 | 10:116e201f7d89 | 585 | // convert a to normal world |
feb11 | 10:116e201f7d89 | 586 | return montgomeryStep(tmp, 1, modulus, r); |
feb11 | 9:3c191fa04f6e | 587 | } |
feb11 | 9:3c191fa04f6e | 588 | |
feb11 | 9:3c191fa04f6e | 589 | bool BigInt::isValid() const |
feb11 | 9:3c191fa04f6e | 590 | { |
feb11 | 9:3c191fa04f6e | 591 | return size != 0 && bits != 0; |
feb11 | 9:3c191fa04f6e | 592 | } |
feb11 | 9:3c191fa04f6e | 593 | |
feb11 | 11:2f16a220ebbb | 594 | void BigInt::print() const |
feb11 | 0:9d554894785b | 595 | { |
feb11 | 11:2f16a220ebbb | 596 | assert(isValid()); |
feb11 | 11:2f16a220ebbb | 597 | |
feb11 | 0:9d554894785b | 598 | printf("size: %d bytes\n", size); |
feb11 | 0:9d554894785b | 599 | uint32_t n = num(size); |
feb11 | 0:9d554894785b | 600 | for(int i = n-1; i >= 0; --i) |
feb11 | 0:9d554894785b | 601 | { |
feb11 | 1:00f2c40d46ed | 602 | printf("%08x ", bits[i]); |
feb11 | 0:9d554894785b | 603 | } |
feb11 | 0:9d554894785b | 604 | printf("\n"); |
feb11 | 0:9d554894785b | 605 | } |
feb11 | 9:3c191fa04f6e | 606 | |
feb11 | 9:3c191fa04f6e | 607 | void BigInt::trim() |
feb11 | 9:3c191fa04f6e | 608 | { |
feb11 | 9:3c191fa04f6e | 609 | uint8_t *tmp = (uint8_t*)bits; |
feb11 | 9:3c191fa04f6e | 610 | uint32_t newSize = size; |
feb11 | 9:3c191fa04f6e | 611 | while(tmp[newSize-1] == 0 && newSize > 0) |
feb11 | 9:3c191fa04f6e | 612 | newSize--; |
feb11 | 10:116e201f7d89 | 613 | if(newSize == 0) |
feb11 | 10:116e201f7d89 | 614 | newSize = 1; |
feb11 | 9:3c191fa04f6e | 615 | if(num(newSize) < num(size)) |
feb11 | 10:116e201f7d89 | 616 | { |
feb11 | 9:3c191fa04f6e | 617 | bits = (uint32_t*)realloc(bits, sizeof(uint32_t)*num(newSize)); |
feb11 | 10:116e201f7d89 | 618 | } |
feb11 | 9:3c191fa04f6e | 619 | size = newSize; |
feb11 | 9:3c191fa04f6e | 620 | } |
feb11 | 9:3c191fa04f6e | 621 | |
feb11 | 11:2f16a220ebbb | 622 | uint32_t BigInt::numBits() const |
feb11 | 10:116e201f7d89 | 623 | { |
feb11 | 10:116e201f7d89 | 624 | assert(isValid()); |
feb11 | 12:a436f15b58b6 | 625 | |
feb11 | 10:116e201f7d89 | 626 | uint32_t n = (size-1)*8; |
feb11 | 11:2f16a220ebbb | 627 | uint8_t a = bits[num(size)-1] >> ((size-1)%4)*8; |
feb11 | 10:116e201f7d89 | 628 | uint8_t tmp2 = 8; |
feb11 | 11:2f16a220ebbb | 629 | while(!(a & 0x80)) |
feb11 | 10:116e201f7d89 | 630 | { |
feb11 | 11:2f16a220ebbb | 631 | a <<= 1; |
feb11 | 10:116e201f7d89 | 632 | --tmp2; |
feb11 | 10:116e201f7d89 | 633 | } |
feb11 | 10:116e201f7d89 | 634 | n += tmp2; |
feb11 | 10:116e201f7d89 | 635 | |
feb11 | 10:116e201f7d89 | 636 | return n; |
feb11 | 10:116e201f7d89 | 637 | } |