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