Repository files navigation

BigNum in pure javascript

npm install --save bn.js

constBN=require('bn.js');vara=newBN('dead',16);varb=newBN('101010',2);varres=a.add(b);console.log(res.toString(10));// 57047

Note: decimals are not supported in this library.

My Open Source work is supported byScout APM andother sponsors.

There are several prefixes to instructions that affect the way they work. Hereis the list of them in the order of appearance in the function name:

• i - perform operation in-place, storing the result in the host object (onwhich the method was invoked). Might be used to avoid number allocation costs
• u - unsigned, ignore the sign of operands when performing operation, oralways return positive value. Second case applies to reduction operationslikemod(). In such cases if the result will be negative - modulo will beadded to the result to make it positive

• n - the argument of the function must be a plain JavaScriptNumber. Decimals are not supported. The number passed must be smaller than 0x4000000 (67_108_864). Otherwise, an error is thrown.
• rn - both argument and return value of the function are plain JavaScriptNumbers. Decimals are not supported.

• a.iadd(b) - perform addition ona andb, storing the result ina
• a.umod(b) - reducea modulob, returning positive value
• a.iushln(13) - shift bits ofa left by 13

Prefixes/postfixes are put in parens at the end of the line.endian - could beeitherle (little-endian) orbe (big-endian).

• a.clone() - clone number
• a.toString(base, length) - convert to base-string and pad with zeroes
• a.toNumber() - convert to Javascript Number (limited to 53 bits)
• a.toJSON() - convert to JSON compatible hex string (alias oftoString(16))
• a.toArray(endian, length) - convert to byteArray, and optionally zeropad to length, throwing if already exceeding
• a.toArrayLike(type, endian, length) - convert to an instance oftype,which must behave like anArray
• a.toBuffer(endian, length) - convert to Node.js Buffer (if available).length in bytes. Forcompatibility with browserify and similar tools, use this instead:a.toArrayLike(Buffer, endian, length)
• a.bitLength() - get number of bits occupied
• a.zeroBits() - return number of less-significant consequent zero bits(example:1010000 has 4 zero bits)
• a.byteLength() - return number of bytes occupied
• a.isNeg() - true if the number is negative
• a.isEven() - no comments
• a.isOdd() - no comments
• a.isZero() - no comments
• a.cmp(b) - compare numbers and return-1 (a< b),0 (a== b), or1 (a> b)depending on the comparison result (ucmp,cmpn)
• a.lt(b) -a less thanb (n)
• a.lte(b) -a less than or equalsb (n)
• a.gt(b) -a greater thanb (n)
• a.gte(b) -a greater than or equalsb (n)
• a.eq(b) -a equalsb (n)
• a.toTwos(width) - convert to two's complement representation, wherewidth is bit width
• a.fromTwos(width) - convert from two's complement representation, wherewidth is the bit width
• BN.isBN(object) - returns true if the suppliedobject is a BN.js instance
• BN.max(a, b) - returna ifa bigger thanb
• BN.min(a, b) - returna ifa less thanb

• a.neg() - negate sign (i)
• a.abs() - absolute value (i)
• a.add(b) - addition (i,n,in)
• a.sub(b) - subtraction (i,n,in)
• a.mul(b) - multiply (i,n,in)
• a.sqr() - square (i)
• a.pow(b) - raisea to the power ofb
• a.div(b) - divide (divn,idivn)
• a.mod(b) - reduct (u,n) (but noumodn)
• a.divmod(b) - quotient and modulus obtained by dividing
• a.divRound(b) - rounded division

• a.or(b) - or (i,u,iu)
• a.and(b) - and (i,u,iu,andln) (NOTE:andln is going to be replacedwithandn in future)
• a.xor(b) - xor (i,u,iu)
• a.setn(b, value) - set specified bit tovalue
• a.shln(b) - shift left (i,u,iu)
• a.shrn(b) - shift right (i,u,iu)
• a.testn(b) - test if specified bit is set
• a.maskn(b) - clear bits with indexes higher or equal tob (i)
• a.bincn(b) - add1 << b to the number
• a.notn(w) - not (for the width specified byw) (i)

• a.gcd(b) - GCD
• a.egcd(b) - Extended GCD results ({ a: ..., b: ..., gcd: ... })
• a.invm(b) - inversea modulob

When doing lots of reductions using the same modulo, it might be beneficial touse some tricks: likeMontgomery multiplication, or using special algorithmforMersenne Prime.

To enable this trick one should create a reduction context:

varred=BN.red(num);

wherenum is just a BN instance.

Or:

varred=BN.red(primeName);

WhereprimeName is either of theseMersenne Primes:

• 'k256'
• 'p224'
• 'p192'
• 'p25519'

Or:

varred=BN.mont(num);

To reduce numbers withMontgomery trick..mont() is generally faster than.red(num), but slower thanBN.red(primeName).

Before performing anything in reduction context - numbers should be convertedto it. Usually, this means that one should:

• Convert inputs to reducted ones
• Operate on them in reduction context
• Convert outputs back from the reduction context

Here is how one may convert numbers tored:

varredA=a.toRed(red);

Wherered is a reduction context created using instructions above

Here is how to convert them back:

vara=redA.fromRed();

Most of the instructions from the very start of this readme have theircounterparts in red context:

• a.redAdd(b),a.redIAdd(b)
• a.redSub(b),a.redISub(b)
• a.redShl(num)
• a.redMul(b),a.redIMul(b)
• a.redSqr(),a.redISqr()
• a.redSqrt() - square root modulo reduction context's prime
• a.redInvm() - modular inverse of the number
• a.redNeg()
• a.redPow(b) - modular exponentiation

Optimized for elliptic curves that work with 256-bit numbers.There is no limitation on the size of the numbers.

This software is licensed under the MIT License.