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;
}

Committer:
feb11
Date:
Sun May 11 10:33:20 2014 +0000
Revision:
26:94e26bcd229d
Parent:
25:3d5c1f299da2
Support signed integers. Add invMod function

Who changed what in which revision?

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