big integer math operations implemented on top of node buffers


use node buffers as big integers.

Buffers and interpreted as base 256 numbers, where each place is 256 times larger than the previous one, instead of 10 times larger. value = Math.pow(256, i).

Also note that this means bytes in a buffer are interpreted in little endian order. This means that a number such as 0x12345678 is represented in a buffer as new Buffer([0x78, 0x56, 0x34, 0x12]). This greatly simplifies the implementation because the least significant byte (digit) also has the lowest index.

in general, all methods follow this pattern:

result = op(a, b, m?) where m is an optional buffer that the result will be stored into. If m is not provided, then it will be allocated.

return true if this buffer represents zero.

convert int_n into a buffer, that is at least 4 bytes, but if you supply a longer length value, then it will be zero filled to that length.

add a to b and store the result in m (if m is not provided a new buffer will be allocated, and returned) in some cases, a may === m, in other cases, it must be a different buffer.

m may be a, b

subtract b from a and store the result in m (if m is not provided a new buffer will be allocated, and returned)

only positive integers are supported (currently) so a must be larger than b.

m may be a, b

multiply a by b.

m must not be a, b

get the modulus of dividing a big number with a 32 bit int.

Compare whether a is smaller than (-1), equal (0), or greater than b (1) this the same signature as is expected by Array.sort(comparator)

move a big number across by bits. bits can be both positive or negative. a positive number of bits is the same as Math.pow(a, bits) This is an essential part of divide

m may be a

Find the position of the largest valued bit in the number. (since the buffer may have trailing zeros, it's not necessaryily in the last byte)

Divide a by b, updating the q (quotient) and r (remainder) buffers.

a,b,q, and r must all be different buffers.

multiply a by itself.

m must not be a.

Raise e to the power of x, If mod is provided, the result will be e^x % mod.

Calculate the greatest common divisor using the binary gcd algorithm

If mutate is true, the inputs will be mutated, by default, new buffers will be allocated.

Calculate the modular multiplicative inverse This is the inverse of a*x % m = 1.

My implementation is based on sjcl's implementation Unfortunately I was unable to find any reference explaining this particular algorithm, (the benefit this algorithm is that it doesn't require negative numbers, which I havn't implemented)

  • isProbablyPrime (needed for RSA)