Modulo arithmetic with large numbers

Yesterday, we touched on algorithms to support modulo arithmetic in PHP. The goal of these algorithms is to efficiently calculate math against large numbers without blowing up your program’s memory.

Unfortunately, it’s not quite enough to support modern cryptography.

In PHP, the largest integer we can support is defined as PHP_INT_MAX. This is the number 9223372036854775807.

In fairness, I’m not sure many of us can count this high. But it’s also a relatively small number so far as computers are concerned. It has 19 digits, which seems like a lot. For security, though, we want to use at least 1024-bit numbers, which have 309 digits! Most secure systems require a minimum of 2048-bit numbers, which top out at 617 digits.

Our existing algorithms are insufficient to handle numbers of this size.

Arbitrary precision numbers

PHP supports two different modules that will allow us to leverage numbers of (almost) any size: BCMath and GNU Multiple Precision (GMP). Both extensions support modulo exponentiation natively through the bcmod() and gmp_powm() functions, respectively.

The problem is that both extensions encode large numbers as strings, so you can’t use the same integer functions with them once you’ve leveraged one of these functions. BCMath returns everything as a string. GMP wraps the string in a GMP object, which helps distinguish these large numbers from regular strings in the program.

BCMath also has upper limits on the size of integers, so incredibly large numbers will break. Again, for cryptography, the minimum size we’re talking about is 309-digit numbers, so GMP is our only option.

Assume we have a very large, 1024-bit integer modulus, and we want to raise another integer to a 1024-bit power bound by that modulus. To do this, we need to first import our large numbers (as strings) then leverage native GMP functions moving forward as follows:

$mod = <<<MOD
$mod = str_replace(["\r", "\n"], '', $mod);

$exp = <<<EXP
$exp = str_replace(["\r", "\n"], '', $exp);

$result = gmp_powm(2, gmp_init($exp, 16), gmp_init($mod, 16));

Userland implementation

We already have a userland implementation of modulo exponentiation from yesterday. Rather than blindly use a packaged version, we can modify our function to leverage the large number interfaces of the GMP extension.

Recall our optimized, memory-efficient algorithm from yesterday:

function modexp_binary(int $base, int $exponent, int $modulus): int
  if ($modulus === 1) return 0;

  $result = 1;

  $base = $base % $modulus;
  while ($exponent > 0) {
    if ($exponent % 2 === 1) $result = ($result * $base) % $modulus;

    $exponent = $exponent >> 1;
    $base = ($base * $base) % $modulus;

  return $result;

This can be updated to receive either integers or GMP objects (which wrap large integers). Internally we’ll use GMP functions on these presumably large integers, and we always return a GMP object.

function modexp(int|GMP $base, int|GMP $exponent, int|GMP $modulus): GMP
    if (gmp_cmp($modulus, 1) === 0) return gmp_init(0);

    $result = gmp_init(1);
    $base = gmp_mod($base, $modulus);
    while(gmp_cmp($exponent, 0) > 0) {
        if(gmp_cmp(gmp_mod($exponent, 2), 1) === 0)
            $result = gmp_mod(gmp_mul($result, $base), $modulus);
            $exponent = gmp_div($exponent, 2);
            $base = gmp_mod(gmp_mul($base, $base), $modulus);

    return $result;

This function works in theory, but it is somewhat slower than the C-level GMP implementation. It’s useful to walk through the experiment of how we’d implement things by hand. However, for cryptography work speed is vital! Moving forward with any work in this space requires leveraging the native gmp_powm() function for modulo exponentiation.