CtrlK
BlogDocsLog inGet started
Tessl Logo

tessl/npm-bn-js

Big number implementation in pure javascript for arbitrary precision arithmetic

—

Pending

Quality

Pending

Does it follow best practices?

Impact

Pending

No eval scenarios have been run

SecuritybySnyk

Pending

The risk profile of this skill

Overview
Eval results
Files

reduction.mddocs/

Modular Arithmetic and Reduction

Advanced modular arithmetic operations with optimization contexts for cryptographic applications, including Montgomery multiplication and special prime field optimizations.

Capabilities

Reduction Context Creation

Create specialized contexts for efficient modular arithmetic operations.

/**
 * Create a reduction context for modular arithmetic
 * @param {BN|string} modulus - The modulus (BN instance or named prime)
 * @returns {Red} Reduction context for optimized modular operations
 */
BN.red(modulus: BN | string): Red;

/**
 * Create a Montgomery reduction context  
 * @param {BN} modulus - The modulus for Montgomery reduction
 * @returns {Mont} Montgomery reduction context
 */
BN.mont(modulus: BN): Mont;

/**
 * Get a named prime reduction context
 * @param {string} name - Prime name: 'k256', 'p224', 'p192', 'p25519'
 * @returns {Prime} Optimized prime reduction context
 */
BN._prime(name: string): Prime;

Usage Examples:

const BN = require('bn.js');

// Basic reduction context
const mod = new BN('17');
const red = BN.red(mod);

// Montgomery reduction context (faster for repeated operations)
const mont = BN.mont(mod);

// Named prime contexts (highly optimized)
const k256 = BN.red('k256');  // secp256k1 prime
const p224 = BN.red('p224');  // NIST P-224 prime
const p192 = BN.red('p192');  // NIST P-192 prime  
const p25519 = BN.red('p25519'); // Curve25519 prime

console.log('Reduction contexts created');

Converting to Reduction Context

Convert regular BN instances to work within a reduction context.

/**
 * Convert this number to a reduction context
 * @param {Red} ctx - Reduction context to convert to
 * @returns {BN} New BN instance in the reduction context
 */
toRed(ctx: Red): BN;

/**
 * Convert from reduction context back to regular BN
 * @returns {BN} New BN instance outside reduction context
 */
fromRed(): BN;

/**
 * Force this number into a reduction context (without conversion)
 * @param {Red} ctx - Reduction context to force into
 * @returns {BN} This BN instance marked as being in the reduction context
 */
forceRed(ctx: Red): BN;

Usage Examples:

const BN = require('bn.js');

const mod = new BN('17');
const red = BN.red(mod);

// Convert numbers to reduction context
const a = new BN('25').toRed(red);  // 25 mod 17 = 8
const b = new BN('10').toRed(red);  // 10 mod 17 = 10

console.log(a.toString()); // "8" (automatically reduced)
console.log(b.toString()); // "10"

// Convert back from reduction context
const regularA = a.fromRed();
console.log(regularA.toString()); // "8"

Reduction Context Arithmetic

Arithmetic operations optimized for reduction contexts.

/**
 * Addition in reduction context
 * @param {BN} num - Number to add (must be in same reduction context)
 * @returns {BN} New BN instance with sum in reduction context
 */
redAdd(num: BN): BN;

/**
 * Addition in reduction context in-place
 * @param {BN} num - Number to add (must be in same reduction context)
 * @returns {BN} This BN instance with sum in reduction context
 */
redIAdd(num: BN): BN;

/**
 * Subtraction in reduction context
 * @param {BN} num - Number to subtract (must be in same reduction context)
 * @returns {BN} New BN instance with difference in reduction context
 */
redSub(num: BN): BN;

/**
 * Subtraction in reduction context in-place
 * @param {BN} num - Number to subtract (must be in same reduction context)
 * @returns {BN} This BN instance with difference in reduction context
 */
redISub(num: BN): BN;

/**
 * Multiplication in reduction context
 * @param {BN} num - Number to multiply by (must be in same reduction context)
 * @returns {BN} New BN instance with product in reduction context
 */
redMul(num: BN): BN;

/**
 * Multiplication in reduction context in-place
 * @param {BN} num - Number to multiply by (must be in same reduction context)
 * @returns {BN} This BN instance with product in reduction context
 */
redIMul(num: BN): BN;

/**
 * Squaring in reduction context
 * @returns {BN} New BN instance with square in reduction context
 */
redSqr(): BN;

/**
 * Squaring in reduction context in-place
 * @returns {BN} This BN instance with square in reduction context
 */
redISqr(): BN;

Usage Examples:

const BN = require('bn.js');

const mod = new BN('17');
const red = BN.red(mod);

// Convert numbers to reduction context
const a = new BN('10').toRed(red);
const b = new BN('8').toRed(red);

// Reduction context arithmetic (all results automatically mod 17)
const sum = a.redAdd(b);     // (10 + 8) mod 17 = 1
const diff = a.redSub(b);    // (10 - 8) mod 17 = 2  
const product = a.redMul(b); // (10 * 8) mod 17 = 12
const square = a.redSqr();   // (10 * 10) mod 17 = 15

console.log(sum.toString());     // "1"
console.log(diff.toString());    // "2"
console.log(product.toString()); // "12" 
console.log(square.toString());  // "15"

Advanced Reduction Operations

Specialized operations for cryptographic and mathematical applications.

/**
 * Left shift in reduction context
 * @param {number} bits - Number of bits to shift
 * @returns {BN} New BN instance shifted in reduction context
 */
redShl(bits: number): BN;

/**
 * Square root in reduction context (modulo prime)
 * @returns {BN} New BN instance with square root in reduction context
 */
redSqrt(): BN;

/**
 * Modular inverse in reduction context
 * @returns {BN} New BN instance with modular inverse in reduction context
 */
redInvm(): BN;

/**
 * Negation in reduction context
 * @returns {BN} New BN instance with negation in reduction context
 */
redNeg(): BN;

/**
 * Exponentiation in reduction context
 * @param {BN} exponent - Exponent (regular BN, not in reduction context)
 * @returns {BN} New BN instance with result in reduction context
 */
redPow(exponent: BN): BN;

Usage Examples:

const BN = require('bn.js');

// Using a prime modulus for cryptographic operations
const p = new BN('97'); // Small prime for example
const red = BN.red(p);

const base = new BN('5').toRed(red);
const exponent = new BN('3');

// Modular exponentiation: 5^3 mod 97 = 125 mod 97 = 28
const result = base.redPow(exponent);
console.log(result.toString()); // "28"

// Modular inverse: find x such that 5*x ≡ 1 (mod 97)
const inverse = base.redInvm();
console.log(inverse.toString()); // "78" (because 5*78 = 390 ≡ 1 (mod 97))

// Verify inverse
const verification = base.redMul(inverse);
console.log(verification.toString()); // "1"

// Square root (if exists)
const square = new BN('4').toRed(red);
const sqrt = square.redSqrt();
console.log(sqrt.toString()); // "2" (since 2^2 = 4)

Named Prime Contexts

Working with well-known cryptographic primes for optimal performance.

/**
 * Named prime reduction contexts for cryptographic applications
 */
interface NamedPrimes {
  /** secp256k1 prime: 2^256 - 2^32 - 977 */
  'k256': Red;
  
  /** NIST P-224 prime */
  'p224': Red;
  
  /** NIST P-192 prime */
  'p192': Red;
  
  /** Curve25519 prime: 2^255 - 19 */
  'p25519': Red;
}

Usage Examples:

const BN = require('bn.js');

// secp256k1 curve operations (Bitcoin/Ethereum)
const k256 = BN.red('k256');
const privateKey = new BN('1234567890abcdef1234567890abcdef1234567890abcdef1234567890abcdef', 16);
const keyInField = privateKey.toRed(k256);

// Curve25519 operations
const p25519 = BN.red('p25519');
const coordinate = new BN('9').toRed(p25519);
const doubled = coordinate.redAdd(coordinate);

console.log('Cryptographic field operations completed');

// NIST curves
const p224 = BN.red('p224');
const p192 = BN.red('p192');

// These contexts are heavily optimized for their specific primes

Montgomery Reduction

Specialized Montgomery reduction for repeated modular operations.

/**
 * Montgomery reduction context for high-performance modular arithmetic
 */
interface Mont extends Red {
  /** Convert number to Montgomery form */
  convertTo(num: BN): BN;
  
  /** Convert number from Montgomery form */
  convertFrom(num: BN): BN;
  
  /** Montgomery multiplication */
  mul(a: BN, b: BN): BN;
  
  /** Montgomery in-place multiplication */
  imul(a: BN, b: BN): BN;
  
  /** Montgomery modular inverse */
  invm(a: BN): BN;
}

Usage Examples:

const BN = require('bn.js');

// Montgomery context is ideal for repeated operations with same modulus
const modulus = new BN('1000000007'); // Large prime
const mont = BN.mont(modulus);

// Convert to Montgomery form
const a = new BN('123456').toRed(mont);
const b = new BN('789012').toRed(mont);

// Montgomery arithmetic (highly optimized)
const product = a.redMul(b);
const sum = a.redAdd(b);

// Convert back when done
const finalResult = product.fromRed();
console.log(finalResult.toString());

Cryptographic Applications

Elliptic Curve Operations

const BN = require('bn.js');

// Example: Basic operations on secp256k1 field
const k256 = BN.red('k256');

// Simulate elliptic curve point operations
function addPoints(p1, p2) {
  // Simplified example - real EC operations are more complex
  const x1 = p1.x.toRed(k256);
  const y1 = p1.y.toRed(k256);
  const x2 = p2.x.toRed(k256);
  const y2 = p2.y.toRed(k256);
  
  // Point addition formula components
  const dx = x2.redSub(x1);
  const dy = y2.redSub(y1);
  const slope = dy.redMul(dx.redInvm());
  
  // New point coordinates
  const x3 = slope.redSqr().redSub(x1).redSub(x2);
  const y3 = slope.redMul(x1.redSub(x3)).redSub(y1);
  
  return {
    x: x3.fromRed(),
    y: y3.fromRed()
  };
}

Modular Exponentiation for RSA

const BN = require('bn.js');

function rsaEncrypt(message, exponent, modulus) {
  const red = BN.mont(modulus); // Montgomery for efficiency
  
  const m = message.toRed(red);
  const c = m.redPow(exponent);
  
  return c.fromRed();
}

// Example usage
const message = new BN('42');
const publicExponent = new BN('65537');
const modulus = new BN('1000000007');

const ciphertext = rsaEncrypt(message, publicExponent, modulus);
console.log('Encrypted:', ciphertext.toString());

Discrete Logarithm Operations

const BN = require('bn.js');

function modularExponentiation(base, exponent, modulus) {
  const red = BN.mont(modulus);
  
  const b = base.toRed(red);
  const result = b.redPow(exponent);
  
  return result.fromRed();
}

// Diffie-Hellman key exchange simulation
const p = new BN('23'); // Small prime for example
const g = new BN('5');  // Generator

const alicePrivate = new BN('6');
const bobPrivate = new BN('15');

// Public keys
const alicePublic = modularExponentiation(g, alicePrivate, p);
const bobPublic = modularExponentiation(g, bobPrivate, p);

// Shared secrets (should be equal)
const aliceShared = modularExponentiation(bobPublic, alicePrivate, p);
const bobShared = modularExponentiation(alicePublic, bobPrivate, p);

console.log('Alice shared:', aliceShared.toString());
console.log('Bob shared:', bobShared.toString());
console.log('Equal:', aliceShared.eq(bobShared)); // true

Performance Notes

  • Named prime contexts ('k256', 'p224', etc.) are most optimized
  • Montgomery contexts are best for repeated operations with the same modulus
  • Basic red contexts are sufficient for occasional modular arithmetic
  • Always convert numbers to the reduction context before operations
  • Keep numbers in reduction context for sequences of operations
  • Convert back to regular BN only when needed for output or different contexts

docs

arithmetic.md

bitwise.md

comparison.md

conversion.md

index.md

reduction.md

tile.json