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