First stab at producing up to 2^64 unique integers in a pseudo-random order without collisions

IntegerGenerator.js

import math from 'mathjs'

math.config({
  number:    'BigNumber',
  precision: 64
})

/**
 * IntegerGenerator
 *
 * An iterable representing numbers in a range yielded in a pseudo-random sequence. This is
 * accomplished using a linear congruential generator. When given appropriate options which
 * satisfy the Hull-Dobell Theorem (or using options which prompt the class to generate these values
 * on it's own) the iterable will yield every value in the range - that is to say that given the
 * range {0, 2^64-1} the iterable will yield exactly 2^64-1 unique numbers in a shuffled order.
 */
export class IntegerGenerator {
  constructor( opts = {} ) {
    this.min      = math.bignumber( opts.min || 0 )
    this.max      = opts.max ? math.bignumber( opts.max ) : math.bignumber( math.chain( 2 ).pow( 64 ).subtract( 1 ).done() )
    this.range    = math.subtract( this.max, this.min )
    this.seed     = opts.seed ? math.subtract( opts.seed, this.min ) : this.max //TODO: randomize - mathjs random doesn't support BigNumber?? math.random( 0, this.range )
    this.previous = opts.previous ? math.bignumber( opts.previous ) : this.seed
    this.base     = opts.base || 10
    this.glyphs   = opts.glyphs || '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/'
    this.unique   = opts.unique === false ? false : true

    if( this.base > this.glyphs.length )
      throw new RangeError( 'Cannot produce base ' + this.base + ' output with only ' + this.glyphs.length + ' glyphs' )

    if( opts.increment )
      this.increment = math.bignumber( opts.increment )
    else
      this.increment = getNthElement( coprimeGenerator( this.range ), math.bignumber( opts.incrementIndex || 1 ) )

    if( opts.multiplier )
      this.multiplier = math.bignumber( opts.multiplier )
    else
      this.multiplier = getNthElement( multiplierGenerator( this.range ), math.bignumber( opts.multiplierIndex || 1 ) )
  }

  next() {
    if( this.unique && math.equal( this.previous, this.seed ) ) {
      return {
        done:  true,
        value: toBaseString( math.add( this.seed, this.min ), this.base, this.glyphs )
      }
    }

    if( !this.previous )
      this.previous = this.seed

    this.previous = math.chain( this.previous ).multiply( this.multiplier ).add( this.increment ).mod( this.range ).done()

    return {
      done: false,
      value: toBaseString( math.add( this.previous, this.min ), this.base, this.glyphs )
    }
  }

  getState() {
    return {
      seed:     math.string( this.seed ),
      min:      math.string( this.min ),
      max:      math.string( this.max ),
      previous: math.string( this.previous ),
      base:     this.base,
      glyphs:   this.glyphs,
      unique:   this.unique
    }
  }
}

export const toBaseString = ( n, base, glyphs ) => {
  let output = []

  if( 10 === base )
    return math.string( n )

  do {
    output.push( glyphs[ math.number( math.mod( n, base ) ) ] )
    n = math.chain( n ).divide( base ).floor().done()
  } while( !math.equal( n, 0 ) )

  return output.reverse().join('')
}

/**
 * Generates a sequence of numbers which satisfy the Hull-Dobell Theorem requirements for a linear
 * congruential generator's multiplier. Specifically, the multiplier - 1 must A) be divisible by
 * all prime factors of the modulus and B) be divisible by 4 if the modulus is divisible by 4.
 *
 * @param  {BigNumber} n - The modulus (or maximum value) of the LCG
 * @return {Generator} An iterable representing all qualifying multipliers in the range {0, n}
 */
export const multiplierGenerator = function *( n ) {
  let factors       = getUniqueFactors( n )
  let largestFactor = math.max( factors )

  if( math.equal( largestFactor, n ) )
    throw new Error( 'Cannot generate multipliers for a prime modulus' )

  // Multiplier - 1 must be divisible by 4 if n is - so add 4 to factors if n%4===0, and remove 2 if present
  if( math.chain( n ).mod( 4 ).equal( 0 ).done() ) {
    factors = factors.filter( el => !math.equal( el, 2 ) )
    factors.unshift( math.bignumber( 4 ) )
  }

  let i = 1
  let m = math.bignumber( math.prod( factors, [ i++ ] ) )

  if( math.larger( m, n ) )
    throw new Error( 'No possible multipliers for modulus ' + math.string( n ) )

  for(; math.smaller( m, n ); i++ ) {
    yield math.add( m, 1 )
    m = math.prod( factors, [ i++ ] )
  }

  throw new RangeError( 'No further multipliers possible for modulus ' + math.string( n ) )
}

/**
 * Generates a sequence of numbers in the range {0, n} which are coprime with n.
 *
 * @param  {BigNumber} n
 * @return {Generator}
 */
export const coprimeGenerator = function *( n ) {
  for( let i = math.bignumber( 0 ); math.smaller( i, n ); i = math.add( i, 1 ) )
    if( math.equal( 1, math.gcd( n, i ) ) )
      yield i
}

/**
 * Given an iterable, advances iteration to the specified index and returns that value
 *
 * @param  {[type]} iterable [description]
 * @param  {[type]} index    [description]
 * @return {[type]}          [description]
 */
export const getNthElement = ( iterable, index ) => {
  for( let i = 0; !math.equal( i, index ); i++ )
    iterable.next()

  return iterable.next().value
}

export const getUniqueFactors = n => {
  let facts = factorize( n ).map( n => math.string( n ) )

  return [ ...new Set( facts ) ]
}

/**
 * Determine the prime factors of a BigNumber. Uses dtr's risk factor. This is extremely quick for
 * most numbers - most notably those which are round powers - but can take up to 20 minutes for
 * numbers who's largest prime factor is near Number.MAX_SAFE_INTEGER or larger
 *
 * @param  {BigNumber} n - The number which to factor
 * @return {BigNumber[]} - An array of factors
 */
export const factorize = n => {
  if( math.smaller( n, 3 ) )
    return [ n ]

  let limit = math.sqrt( n )
  let facts = []

  if( math.chain( n ).mod( 2 ).equal( 0 ).done() ) {
    facts.push( 2 )
    facts.push( ...factorize( math.divide( n, 2 ) ) )
    return facts
  }

  for( let i = math.bignumber( 3 ); math.smallerEq( i, limit ); i = math.add( i, 2 ) ) {
    if( math.chain( n ).mod( i ).equal( 0 ).done() ) {
      facts.push( i )
      facts.push( ...factorize( math.divide( n, i ) ) )
      return facts
    }
  }

  return [ n ]
}