Big Number Arithmetic

/**
 * Big number constructor
 * @param {number|string|sjcl.bn} it - Initial value (number, hex string, or another big number)
 */
new sjcl.bn(it);

const sjcl = require('sjcl');

// Create from integer
const bn1 = new sjcl.bn(12345);
console.log('From integer:', bn1.toString());

// Create from hex string
const bn2 = new sjcl.bn('deadbeef');
console.log('From hex:', bn2.toString());

// Create from another big number (copy constructor)
const bn3 = new sjcl.bn(bn2);
console.log('Copied:', bn3.toString());

// Create large number
const largeBN = new sjcl.bn('123456789abcdef0123456789abcdef0123456789abcdef');
console.log('Large number:', largeBN.toString());

/**
 * Copy the big number
 * @returns {sjcl.bn} New big number with same value
 */
sjcl.bn.prototype.copy();

/**
 * Initialize with new value
 * @param {number|string|sjcl.bn} it - New value
 * @returns {sjcl.bn} This big number for chaining
 */
sjcl.bn.prototype.initWith(it);

/**
 * Test equality with another big number
 * @param {sjcl.bn} that - Big number to compare with
 * @returns {boolean} True if numbers are equal
 */
sjcl.bn.prototype.equals(that);

/**
 * Greater than or equal comparison (constant time)
 * @param {sjcl.bn} that - Big number to compare with
 * @returns {boolean} True if this >= that
 */
sjcl.bn.prototype.greaterEquals(that);

/**
 * Convert to hex string
 * @returns {string} Hexadecimal representation
 */
sjcl.bn.prototype.toString();

const sjcl = require('sjcl');

// Basic operations
const a = new sjcl.bn('deadbeef');
const b = new sjcl.bn('cafebabe');

// Copy
const aCopy = a.copy();
console.log('Copy equals original:', a.equals(aCopy)); // true

// Comparison
console.log('a >= b:', a.greaterEquals(b));
console.log('a == b:', a.equals(b)); // false

// String conversion
console.log('a as hex:', a.toString());
console.log('b as hex:', b.toString());

// Reinitialize
aCopy.initWith('12345678');
console.log('Reinitialized:', aCopy.toString());

/**
 * Add two big numbers
 * @param {sjcl.bn} that - Big number to add
 * @returns {sjcl.bn} Sum as new big number
 */
sjcl.bn.prototype.add(that);

/**
 * Subtract big number from this one
 * @param {sjcl.bn} that - Big number to subtract
 * @returns {sjcl.bn} Difference as new big number
 */
sjcl.bn.prototype.sub(that);

/**
 * Multiply two big numbers
 * @param {sjcl.bn} that - Big number to multiply by
 * @returns {sjcl.bn} Product as new big number
 */
sjcl.bn.prototype.mul(that);

/**
 * Square the big number
 * @returns {sjcl.bn} Square as new big number
 */
sjcl.bn.prototype.square();

/**
 * Modular exponentiation
 * @param {sjcl.bn} exp - Exponent
 * @param {sjcl.bn} [mod] - Modulus (if provided, computes (this^exp) mod mod)
 * @returns {sjcl.bn} Result as new big number
 */
sjcl.bn.prototype.power(exp, mod);

const sjcl = require('sjcl');

// Create test numbers
const a = new sjcl.bn('1000');
const b = new sjcl.bn('500');
const c = new sjcl.bn('7');

// Basic arithmetic
const sum = a.add(b);
console.log('1000 + 500 =', sum.toString()); // 1500

const diff = a.sub(b);
console.log('1000 - 500 =', diff.toString()); // 500

const product = a.mul(b);
console.log('1000 * 500 =', product.toString()); // 500000

const squared = a.square();
console.log('1000^2 =', squared.toString()); // 1000000

// Exponentiation
const powered = c.power(new sjcl.bn('3'));
console.log('7^3 =', powered.toString()); // 343

// Modular exponentiation
const modPow = c.power(new sjcl.bn('10'), new sjcl.bn('13'));
console.log('7^10 mod 13 =', modPow.toString());

/**
 * Get the i'th limb (32-bit word)
 * @param {number} i - Limb index
 * @returns {number} 32-bit limb value
 */
sjcl.bn.prototype.getLimb(i);

/**
 * Remove leading zeros
 * @returns {sjcl.bn} This big number for chaining
 */
sjcl.bn.prototype.trim();

const sjcl = require('sjcl');\n\n// Create big number\nconst bn = new sjcl.bn('deadbeefcafebabe');\n\n// Access individual limbs (32-bit words)\nconsole.log('Limb 0:', bn.getLimb(0).toString(16));\nconsole.log('Limb 1:', bn.getLimb(1).toString(16));\n\n// Trim leading zeros\nconst withZeros = new sjcl.bn('000deadbeef');\nconsole.log('Before trim:', withZeros.toString());\nwithZeros.trim();\nconsole.log('After trim:', withZeros.toString());\n```\n\n## Cryptographic Applications\n\n### RSA Key Operations\n\nBig numbers are essential for RSA cryptography:\n\n```javascript\nconst sjcl = require('sjcl');\n\n// Simulate RSA key generation components\nfunction generateRSAComponents() {\n  // In real RSA, these would be large random primes\n  const p = new sjcl.bn('d5bbf8a7e3d5e5e0b3f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5');\n  const q = new sjcl.bn('e9f8a7b3d5e5e0f3f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5f5');\n  \n  // Calculate n = p * q\n  const n = p.mul(q);\n  \n  // Calculate phi(n) = (p-1) * (q-1)\n  const pMinus1 = p.sub(new sjcl.bn('1'));\n  const qMinus1 = q.sub(new sjcl.bn('1'));\n  const phi = pMinus1.mul(qMinus1);\n  \n  // Common public exponent\n  const e = new sjcl.bn('65537');\n  \n  return { n, e, phi, p, q };\n}\n\n// RSA encryption (simplified)\nfunction rsaEncrypt(message, publicKey) {\n  const m = new sjcl.bn(message);\n  return m.power(publicKey.e, publicKey.n);\n}\n\n// Usage\nconst keys = generateRSAComponents();\nconst message = 'deadbeef';\nconst encrypted = rsaEncrypt(message, { e: keys.e, n: keys.n });\n\nconsole.log('Original message:', message);\nconsole.log('Encrypted:', encrypted.toString());\n```\n\n### Discrete Logarithm Operations\n\nBig numbers in discrete logarithm cryptography:\n\n```javascript\nconst sjcl = require('sjcl');\n\n// Diffie-Hellman key exchange simulation\nfunction diffieHellmanExample() {\n  // Public parameters (in real use, these would be much larger)\n  const p = new sjcl.bn('23'); // Prime modulus\n  const g = new sjcl.bn('5');  // Generator\n  \n  // Alice's private key\n  const alicePrivate = new sjcl.bn('6');\n  // Alice's public key: g^a mod p\n  const alicePublic = g.power(alicePrivate, p);\n  \n  // Bob's private key\n  const bobPrivate = new sjcl.bn('15');\n  // Bob's public key: g^b mod p\n  const bobPublic = g.power(bobPrivate, p);\n  \n  // Shared secret calculation\n  // Alice computes: (Bob's public)^(Alice's private) mod p\n  const aliceShared = bobPublic.power(alicePrivate, p);\n  \n  // Bob computes: (Alice's public)^(Bob's private) mod p\n  const bobShared = alicePublic.power(bobPrivate, p);\n  \n  return {\n    alicePublic: alicePublic.toString(),\n    bobPublic: bobPublic.toString(),\n    aliceShared: aliceShared.toString(),\n    bobShared: bobShared.toString(),\n    secretsMatch: aliceShared.equals(bobShared)\n  };\n}\n\nconst dhResult = diffieHellmanExample();\nconsole.log('DH Exchange:', dhResult);\n```\n\n### Modular Arithmetic\n\nCommon modular arithmetic operations:\n\n```javascript\nconst sjcl = require('sjcl');\n\nclass ModularArithmetic {\n  constructor(modulus) {\n    this.modulus = new sjcl.bn(modulus);\n  }\n  \n  // Modular addition\n  addMod(a, b) {\n    const aBN = new sjcl.bn(a);\n    const bBN = new sjcl.bn(b);\n    const sum = aBN.add(bBN);\n    \n    // Simple modular reduction (not constant-time)\n    while (sum.greaterEquals(this.modulus)) {\n      sum = sum.sub(this.modulus);\n    }\n    \n    return sum;\n  }\n  \n  // Modular multiplication\n  mulMod(a, b) {\n    const aBN = new sjcl.bn(a);\n    const bBN = new sjcl.bn(b);\n    const product = aBN.mul(bBN);\n    \n    // Simple modular reduction\n    while (product.greaterEquals(this.modulus)) {\n      product = product.sub(this.modulus);\n    }\n    \n    return product;\n  }\n  \n  // Modular exponentiation\n  powMod(base, exp) {\n    const baseBN = new sjcl.bn(base);\n    const expBN = new sjcl.bn(exp);\n    \n    return baseBN.power(expBN, this.modulus);\n  }\n}\n\n// Usage\nconst mod17 = new ModularArithmetic('17');\n\nconsole.log('5 + 15 mod 17 =', mod17.addMod('5', '15').toString()); // 3\nconsole.log('7 * 8 mod 17 =', mod17.mulMod('7', '8').toString());   // 5\nconsole.log('3^10 mod 17 =', mod17.powMod('3', '10').toString());   // 16\n```\n\n## Advanced Operations\n\n### Prime Testing\n\nBasic primality testing using big numbers:\n\n```javascript\nconst sjcl = require('sjcl');\n\nclass PrimalityTest {\n  // Simple trial division (not cryptographically secure)\n  static isSmallPrime(n) {\n    const bn = new sjcl.bn(n);\n    const two = new sjcl.bn('2');\n    const three = new sjcl.bn('3');\n    \n    if (bn.equals(two) || bn.equals(three)) return true;\n    \n    // Check if divisible by 2\n    const mod2 = bn.power(new sjcl.bn('1'), two);\n    if (mod2.equals(new sjcl.bn('0'))) return false;\n    \n    // Check odd divisors up to sqrt(n)\n    let divisor = new sjcl.bn('3');\n    const limit = new sjcl.bn(Math.floor(Math.sqrt(parseInt(n.toString()))));\n    \n    while (divisor.greaterEquals(limit) === false) {\n      // This is a simplified check - real implementation would use modular division\n      divisor = divisor.add(two);\n    }\n    \n    return true; // Simplified - real implementation needed\n  }\n  \n  // Fermat primality test (probabilistic)\n  static fermatTest(n, iterations = 5) {\n    const nBN = new sjcl.bn(n);\n    const one = new sjcl.bn('1');\n    const nMinus1 = nBN.sub(one);\n    \n    for (let i = 0; i < iterations; i++) {\n      // Choose random a in range [2, n-2]\n      const a = new sjcl.bn('2').add(new sjcl.bn(Math.floor(Math.random() * 100)));\n      \n      // Check if a^(n-1) ≡ 1 (mod n)\n      const result = a.power(nMinus1, nBN);\n      \n      if (!result.equals(one)) {\n        return false; // Definitely composite\n      }\n    }\n    \n    return true; // Probably prime\n  }\n}\n\n// Usage (simplified examples)\nconsole.log('17 is prime (Fermat):', PrimalityTest.fermatTest('17'));\nconsole.log('15 is prime (Fermat):', PrimalityTest.fermatTest('15')); // Should be false\n```\n\n### Number Theory Operations\n\nImplement common number theory operations:\n\n```javascript\nconst sjcl = require('sjcl');\n\nclass NumberTheory {\n  // Greatest Common Divisor (Euclidean algorithm)\n  static gcd(a, b) {\n    let aBN = new sjcl.bn(a);\n    let bBN = new sjcl.bn(b);\n    const zero = new sjcl.bn('0');\n    \n    while (!bBN.equals(zero)) {\n      const temp = bBN.copy();\n      // In real implementation, we'd need modular division\n      // This is simplified\n      bBN = aBN; // Placeholder - real implementation needed\n      aBN = temp;\n    }\n    \n    return aBN;\n  }\n  \n  // Least Common Multiple\n  static lcm(a, b) {\n    const aBN = new sjcl.bn(a);\n    const bBN = new sjcl.bn(b);\n    const gcdResult = NumberTheory.gcd(a, b);\n    \n    return aBN.mul(bBN); // Simplified - should divide by GCD\n  }\n  \n  // Check if two numbers are coprime\n  static areCoprime(a, b) {\n    const gcdResult = NumberTheory.gcd(a, b);\n    return gcdResult.equals(new sjcl.bn('1'));\n  }\n}\n\n// Usage examples\nconst a = '48';\nconst b = '18';\n\nconsole.log(`gcd(${a}, ${b}) =`, NumberTheory.gcd(a, b).toString());\nconsole.log(`Are ${a} and ${b} coprime?`, NumberTheory.areCoprime(a, b));\n```\n\n## Performance Considerations\n\n1. **Operation Cost**: Multiplication and exponentiation are expensive\n2. **Memory Usage**: Large numbers consume significant memory\n3. **Algorithm Choice**: Use appropriate algorithms for different operations\n4. **Optimization**: Consider Montgomery multiplication for repeated modular operations\n5. **Bit Length**: Minimize bit lengths when possible\n\n## Security Considerations\n\n1. **Timing Attacks**: Big number operations are NOT constant-time\n2. **Side Channels**: Be aware of potential information leakage\n3. **Random Numbers**: Use secure random number generation for cryptographic applications\n4. **Implementation**: SJCL's big number implementation may not be side-channel resistant\n5. **Validation**: Always validate big number inputs and results\n\n## Common Use Cases\n\n1. **RSA Cryptography**: Modular exponentiation with large numbers\n2. **Elliptic Curves**: Field arithmetic for curve operations\n3. **Discrete Logarithms**: Diffie-Hellman and related protocols\n4. **Digital Signatures**: DSA and ECDSA signature schemes\n5. **Key Generation**: Creating cryptographic keys and parameters\n6. **Mathematical Proofs**: Zero-knowledge proofs and commitments