Modular Arithmetic and Reduction

/**
 * 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;

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');

/**
 * 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;

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"

/**
 * 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;

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"

/**
 * 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;

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 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;
}

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 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;
}

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());

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()
  };
}

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());

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