SkillAgentSearch skills...

Leemon

High perfomance big integer library for modern javascript application

GenerateConvertImprove

Install / Use

/learn @zerobias/Leemon
About this skill

Quality Score

0/100

Supported Platforms

Universal

README

Leemon

High perfomance big integer library for modern javascript application

npm install --save leemon

yarn add leemon

npm version Build Status

This code is reincarnation of Big Integer Library created by Leemon Baird in 2000, supported up to 2013

Example

Fibonacci

import { one, zero, add, bigInt2str } from 'leemon'

function* fibonacci() {
  let a = zero
  let b = one
  while(true){
    const c = add(a, b)
    a = b
    b = c
    yield bigInt2str(c, 10)
  }
}

const fib = fibonacci()



for (let i = 0;i<500;i++) fib.next().value

// => '225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626'

A bigInt is an array of integers storing the value in chunks of bpe bits, little endian (buff[0] is the least significant word). Negative bigInts are stored two's complement. Almost all the functions treat bigInts as nonnegative. The few that view them as two's complement say so in their comments. Some functions assume their parameters have at least one leading zero element. Functions with an underscore at the end of the name put their answer into one of the arrays passed in, and have unpredictable behavior in case of overflow, so the caller must make sure the arrays are big enough to hold the answer. But the average user should never have to call any of the underscored functions. Each important underscored function has a wrapper function of the same name without the underscore that takes care of the details for you. For each underscored function where a parameter is modified, that same variable must not be used as another argument too. So, you cannot square x by doing multMod_(x,x,n). You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n). Or simply use the multMod(x,x,n) function without the underscore, where such issues never arise, because non-underscored functions never change their parameters (immutable); they always allocate new memory for the answer that is returned.

API

Table of Contents

  • [Bool][1]
  • [findPrimes][2]
    • [Parameters][3]
  • [millerRabinInt][4]
    • [Parameters][5]
  • [millerRabin][6]
    • [Parameters][7]
  • [bitSize][8]
    • [Parameters][9]
  • [expand][10]
    • [Parameters][11]
  • [randTruePrime][12]
    • [Parameters][13]
  • [randProbPrime][14]
    • [Parameters][15]
  • [randProbPrimeRounds][16]
    • [Parameters][17]
  • [mod][18]
    • [Parameters][19]
  • [addInt][20]
    • [Parameters][21]
  • [mult][22]
    • [Parameters][23]
  • [powMod][24]
    • [Parameters][25]
  • [sub][26]
    • [Parameters][27]
  • [add][28]
    • [Parameters][29]
  • [inverseMod][30]
    • [Parameters][31]
  • [multMod][32]
    • [Parameters][33]
  • [randTruePrime_][34]
    • [Parameters][35]
  • [randBigInt][36]
    • [Parameters][37]
  • [randBigInt_][38]
    • [Parameters][39]
  • [GCD][40]
    • [Parameters][41]
  • [GCD_][42]
    • [Parameters][43]
  • [inverseMod_][44]
    • [Parameters][45]
  • [inverseModInt][46]
    • [Parameters][47]
  • [eGCD_][48]
    • [Parameters][49]
  • [negative][50]
    • [Parameters][51]
  • [greaterShift][52]
    • [Parameters][53]
  • [greater][54]
    • [Parameters][55]
  • [divide_][56]
    • [Parameters][57]
  • [carry_][58]
    • [Parameters][59]
  • [modInt][60]
    • [Parameters][61]
  • [int2bigInt][62]
    • [Parameters][63]
  • [str2bigInt][64]
    • [Parameters][65]
  • [equalsInt][66]
    • [Parameters][67]
  • [equals][68]
    • [Parameters][69]
  • [isZero][70]
    • [Parameters][71]
  • [bigInt2str][72]
    • [Parameters][73]
  • [dup][74]
    • [Parameters][75]
  • [copy_][76]
    • [Parameters][77]
  • [copyInt_][78]
    • [Parameters][79]
  • [addInt_][80]
    • [Parameters][81]
  • [rightShift_][82]
    • [Parameters][83]
  • [halve_][84]
    • [Parameters][85]
  • [leftShift_][86]
    • [Parameters][87]
  • [multInt_][88]
    • [Parameters][89]
  • [divInt_][90]
    • [Parameters][91]
  • [linComb_][92]
    • [Parameters][93]
  • [linCombShift_][94]
    • [Parameters][95]
  • [addShift_][96]
    • [Parameters][97]
  • [subShift_][98]
    • [Parameters][99]
  • [sub_][100]
    • [Parameters][101]
  • [add_][102]
    • [Parameters][103]
  • [mult_][104]
    • [Parameters][105]
  • [mod_][106]
    • [Parameters][107]
  • [multMod_][108]
    • [Parameters][109]
  • [squareMod_][110]
    • [Parameters][111]
  • [trim][112]
    • [Parameters][113]
  • [powMod_][114]
    • [Parameters][115]
  • [mont_][116]
    • [Parameters][117]

Bool

Big Integer Library _ Created 2000 _ Leemon Baird _ www.leemon.com _

Type: (1 | 0)

findPrimes

return array of all primes less than integer n

Parameters

  • n [number][118]

Returns [Array][119]<[number][118]>

millerRabinInt

does a single round of Miller-Rabin base b consider x to be a possible prime?

x is a bigInt, and b is an integer, with b<x

Parameters

  • x [Array][119]<[number][118]>
  • b [number][118]

Returns (0 | 1)

millerRabin

does a single round of Miller-Rabin base b consider x to be a possible prime?

x and b are bigInts with b<x

Parameters

  • x [Array][119]<[number][118]>
  • b [Array][119]<[number][118]>

Returns (0 | 1)

bitSize

returns how many bits long the bigInt is, not counting leading zeros.

Parameters

  • x [Array][119]<[number][118]>

Returns [number][118]

expand

return a copy of x with at least n elements, adding leading zeros if needed

Parameters

  • x [Array][119]<[number][118]>
  • n [number][118]

Returns [Array][119]<[number][118]>

randTruePrime

return a k-bit true random prime using Maurer's algorithm.

Parameters

  • k [number][118]

Returns [Array][119]<[number][118]>

randProbPrime

return a k-bit random probable prime with probability of error < 2^-80

Parameters

  • k [number][118]

Returns [Array][119]<[number][118]>

randProbPrimeRounds

return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)

Parameters

  • k [number][118]
  • n [number][118]

Returns [Array][119]<[number][118]>

mod

return a new bigInt equal to (x mod n) for bigInts x and n.

Parameters

  • x [Array][119]<[number][118]>
  • n [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

addInt

return (x+n) where x is a bigInt and n is an integer.

Parameters

  • x [Array][119]<[number][118]>
  • n [number][118]

Returns [Array][119]<[number][118]>

mult

return x*y for bigInts x and y. This is faster when y<x.

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

powMod

return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.

0**0=1.

Faster for odd n.

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>
  • n [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

sub

return (x-y) for bigInts x and y

Negative answers will be 2s complement

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

add

return (x+y) for bigInts x and y

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

inverseMod

return (x**(-1) mod n) for bigInts x and n.

If no inverse exists, it returns null

Parameters

  • x [Array][119]<[number][118]>
  • n [Array][119]<[number][118]>

Returns ([Array][119]<[number][118]> | null)

multMod

return (x*y mod n) for bigInts x,y,n.

For greater speed, let y<x.

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>
  • n [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

randTruePrime_

generate a k-bit true random prime using Maurer's algorithm, and put it into ans.

The bigInt ans must be large enough to hold it.

Parameters

  • ans [Array][119]<[number][118]>
  • k [number][118]

Returns void

randBigInt

Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1.

Parameters

  • n [number][118]
  • s [number][118]

Returns [Array][119]<[number][118]>

randBigInt_

Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1.

Array b must be big enough to hold the result. Must have n>=1

Parameters

  • b [Array][119]<[number][118]>
  • n [number][118]
  • s [number][118]

Returns void

GCD

Return the greatest common divisor of bigInts x and y (each with same number of elements).

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>

Returns [Array][119]<[number][118]>

GCD_

set x to the greatest common divisor of bigInts x and y (each with same number of elements).

y is destroyed.

Parameters

  • x [Array][119]<[number][118]>
  • y [Array][119]<[number][118]>

Returns void

inverseMod_

do x=x**(-1) mod n, for bigInts x and n.

If no inverse exists, it sets x to zero

zerobias

View profile

View on GitHub
GitHub Stars29
CategoryDevelopment
Updated1y ago
Forks3
zerobias/leemon

Languages

JavaScript

Security Score

75/100

Audited on Jul 17, 2024

No findings