MULMOD (0x09)

Modular multiplication for 256-bit unsigned integers with arbitrary modulus

This page is a placeholder. All examples on this page are currently AI-generated and are not correct. This documentation will be completed in the future with accurate, tested examples.

Overview

Opcode: 0x09 Introduced: Frontier (EVM genesis)

MULMOD performs modular multiplication (a * b) % N where all operands are 256-bit unsigned integers. Unlike standard MUL followed by MOD, MULMOD computes the result using wider arithmetic to prevent intermediate overflow, making it critical for cryptographic operations.

Division by zero (N = 0) returns 0 rather than throwing an exception.

Specification

Stack Input:

a (top)
b
N (modulus)

Stack Output:

(a * b) % N

Gas Cost: 8 (GasMidStep)

Operation:

if N == 0:
  result = 0
else:
  result = (a * b) % N

Behavior

MULMOD pops three values from the stack (a, b, N), computes (a * b) mod N, and pushes the result back:

• Normal case: Result is (a * b) % N
• N = 0: Returns 0 (EVM convention)
• No intermediate overflow: Uses 512-bit arithmetic internally

The key advantage over MUL then MOD is that MULMOD avoids intermediate overflow when a * b >= 2^256.

Examples

Basic Modular Multiplication

import { mulmod } from '@tevm/voltaire/evm/arithmetic';
import { createFrame } from '@tevm/voltaire/evm/Frame';

// (5 * 10) % 3 = 50 % 3 = 2
const frame = createFrame({ stack: [5n, 10n, 3n] });
const err = mulmod(frame);

console.log(frame.stack); // [2n]
console.log(frame.gasRemaining); // Original - 8

Overflow-Safe Multiplication

// MAX * MAX would overflow in MUL, but MULMOD handles it
const MAX_U256 = (1n << 256n) - 1n;
const frame = createFrame({ stack: [MAX_U256, MAX_U256, 7n] });
const err = mulmod(frame);

// (MAX * MAX) % 7
const expected = ((MAX_U256 * MAX_U256) % 7n);
console.log(frame.stack); // [expected]

Zero Modulus

// Division by zero returns 0
const frame = createFrame({ stack: [5n, 10n, 0n] });
const err = mulmod(frame);

console.log(frame.stack); // [0n]

Multiply by Zero

// 0 * anything = 0
const frame = createFrame({ stack: [0n, 42n, 17n] });
const err = mulmod(frame);

console.log(frame.stack); // [0n]

Large Modulus Operation

// Very large multiplication
const a = (1n << 200n) - 1n;
const b = (1n << 200n) - 1n;
const n = (1n << 100n) + 7n;

const frame = createFrame({ stack: [a, b, n] });
const err = mulmod(frame);

const expected = (a * b) % n;
console.log(frame.stack); // [expected]

Gas Cost

Cost: 8 gas (GasMidStep)

MULMOD shares the same gas cost as ADDMOD due to similar computational complexity:

Comparison:

• ADD/SUB: 3 gas
• MUL: 5 gas
• DIV/MOD: 5 gas
• ADDMOD/MULMOD: 8 gas
• EXP: 10 + 50 per byte

MULMOD is more efficient than separate MUL + MOD when dealing with values that would overflow during multiplication.

Edge Cases

Maximum Values

const MAX = (1n << 256n) - 1n;

// MAX * MAX mod large prime
const frame = createFrame({ stack: [MAX, MAX, 1000000007n] });
mulmod(frame);

const expected = (MAX * MAX) % 1000000007n;
console.log(frame.stack); // [expected]

Modulus of 1

// Any number mod 1 is 0
const frame = createFrame({ stack: [999n, 888n, 1n] });
mulmod(frame);

console.log(frame.stack); // [0n]

Result Equals Modulus Minus One

// (3 * 3) % 10 = 9
const frame = createFrame({ stack: [3n, 3n, 10n] });
mulmod(frame);

console.log(frame.stack); // [9n]

Stack Underflow

// Not enough stack items
const frame = createFrame({ stack: [5n, 10n] });
const err = mulmod(frame);

console.log(err); // { type: "StackUnderflow" }

Out of Gas

// Insufficient gas
const frame = createFrame({ stack: [5n, 10n, 3n], gasRemaining: 7n });
const err = mulmod(frame);

console.log(err); // { type: "OutOfGas" }
console.log(frame.gasRemaining); // 0n

Common Usage

Elliptic Curve Point Multiplication

// secp256k1 field multiplication
assembly {
    let p := 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

    // Multiply two field elements
    let x1 := mload(0x00)
    let x2 := mload(0x20)
    let product := mulmod(x1, x2, p)
}

Montgomery Reduction

// Montgomery form multiplication
function montgomeryMul(uint256 a, uint256 b, uint256 N, uint256 R)
    pure returns (uint256)
{
    assembly {
        let T := mulmod(a, b, N)
        let m := mulmod(T, R, N)
        let t := addmod(mulmod(m, N, N), T, N)
        mstore(0x00, mulmod(t, R, N))
        return(0x00, 0x20)
    }
}

Modular Exponentiation Building Block

// Square-and-multiply algorithm
function modExp(uint256 base, uint256 exp, uint256 mod)
    pure returns (uint256 result)
{
    result = 1;
    assembly {
        for {} gt(exp, 0) {} {
            if and(exp, 1) {
                result := mulmod(result, base, mod)
            }
            base := mulmod(base, base, mod)
            exp := shr(1, exp)
        }
    }
}

RSA/Fermat Operations

// Modular square for primality testing
function fermatTest(uint256 a, uint256 p) pure returns (bool) {
    // Check if a^(p-1) ≡ 1 (mod p)
    uint256 exp = p - 1;
    uint256 result = 1;

    assembly {
        for {} gt(exp, 0) {} {
            if and(exp, 1) {
                result := mulmod(result, a, p)
            }
            a := mulmod(a, a, p)
            exp := shr(1, exp)
        }
    }

    return result == 1;
}

Polynomial Evaluation

// Evaluate polynomial at point x mod p
function polyEval(uint256[] memory coeffs, uint256 x, uint256 p)
    pure returns (uint256 result)
{
    assembly {
        let len := mload(coeffs)
        result := 0

        for { let i := 0 } lt(i, len) { i := add(i, 1) } {
            let coeff := mload(add(coeffs, mul(add(i, 1), 0x20)))
            result := addmod(mulmod(result, x, p), coeff, p)
        }
    }
}

Implementation

TypeScript

/**
 * MULMOD opcode (0x09) - Multiplication modulo N
 */
export function mulmod(frame: FrameType): EvmError | null {
  // Consume gas (GasMidStep = 8)
  frame.gasRemaining -= 8n;
  if (frame.gasRemaining < 0n) {
    frame.gasRemaining = 0n;
    return { type: "OutOfGas" };
  }

  // Pop operands: a, b, N
  if (frame.stack.length < 3) return { type: "StackUnderflow" };
  const a = frame.stack.pop();
  const b = frame.stack.pop();
  const n = frame.stack.pop();

  // Compute result
  let result: bigint;
  if (n === 0n) {
    result = 0n;
  } else {
    // BigInt handles arbitrary precision - no overflow
    result = (a * b) % n;
  }

  // Push result
  if (frame.stack.length >= 1024) return { type: "StackOverflow" };
  frame.stack.push(result);

  // Increment PC
  frame.pc += 1;

  return null;
}

Testing

Test Coverage

import { describe, it, expect } from 'vitest';
import { mulmod } from './0x09_MULMOD.js';

describe('MULMOD (0x09)', () => {
  it('computes (a * b) % N', () => {
    const frame = createFrame([5n, 10n, 3n]);
    expect(mulmod(frame)).toBeNull();
    expect(frame.stack).toEqual([2n]); // 50 % 3 = 2
  });

  it('returns 0 when N is 0', () => {
    const frame = createFrame([5n, 10n, 0n]);
    expect(mulmod(frame)).toBeNull();
    expect(frame.stack).toEqual([0n]);
  });

  it('handles large values without overflow', () => {
    const MAX = (1n << 256n) - 1n;
    const frame = createFrame([MAX, MAX, 7n]);
    expect(mulmod(frame)).toBeNull();
    expect(frame.stack).toEqual([(MAX * MAX) % 7n]);
  });

  it('multiplies by zero', () => {
    const frame = createFrame([0n, 42n, 17n]);
    expect(mulmod(frame)).toBeNull();
    expect(frame.stack).toEqual([0n]);
  });

  it('returns StackUnderflow with insufficient stack', () => {
    const frame = createFrame([5n, 10n]);
    expect(mulmod(frame)).toEqual({ type: 'StackUnderflow' });
  });

  it('returns OutOfGas when insufficient gas', () => {
    const frame = createFrame([5n, 10n, 3n], 7n);
    expect(mulmod(frame)).toEqual({ type: 'OutOfGas' });
  });
});

Edge Cases Tested

• Basic modular multiplication (50 % 3 = 2)
• Zero modulus (returns 0)
• Modulus of 1 (always returns 0)
• Multiply by zero (always returns 0)
• Large values (MAX * MAX)
• Overflow-safe computation
• Very large intermediate products
• Stack underflow (< 3 items)
• Out of gas (< 8 gas)

Security

Cryptographic Operations

MULMOD is fundamental for implementing secure cryptographic primitives:

secp256k1 Scalar Multiplication:

uint256 constant CURVE_ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;

function scalarMul(uint256 k, uint256 x) pure returns (uint256) {
    return mulmod(k, x, CURVE_ORDER);
}

BN254 Pairing Operations:

// BN254 field operations
uint256 constant BN254_P = 21888242871839275222246405745257275088696311157297823662689037894645226208583;

function bn254FieldMul(uint256 a, uint256 b) pure returns (uint256) {
    return mulmod(a, b, BN254_P);
}

Side-Channel Resistance

MULMOD completes in constant time regardless of operand values, preventing timing attacks in cryptographic implementations. This is critical for:

• Private key operations
• Signature generation
• Zero-knowledge proof systems

Overflow Safety

Unlike MUL then MOD, MULMOD prevents intermediate overflow:

Vulnerable pattern:

// Can overflow if a * b >= 2^256
uint256 product = a * b;
uint256 result = product % N;  // Wrong result if overflow occurred

Safe pattern:

// Always correct
uint256 result = mulmod(a, b, N);

Constant-Time Guarantees

EVM implementations must ensure MULMOD executes in constant time to prevent leaking sensitive information through timing channels:

// Safe for private key operations
function blindSignature(uint256 message, uint256 blindFactor, uint256 n)
    pure returns (uint256)
{
    return mulmod(message, blindFactor, n);
}

References

• Yellow Paper - Section 9.1 (Arithmetic Operations)
• EVM Codes - MULMOD
• EIP-196 - alt_bn128 curve operations
• EIP-197 - Precompiled contracts for optimal ate pairing check
• Montgomery Arithmetic - Efficient modular multiplication

Related Instructions

• MUL - Basic multiplication with wrapping
• ADDMOD - Modular addition
• MOD - Unsigned modulo operation
• EXP - Exponentiation (uses MULMOD internally)