For safe prime p, prime q = (p - 1)/2, and generator g = 2, we have a distinct sequence (mod p):
g^0,g^1,...,g^q-1
Then the sequence repeats,
g^q (mod p) = g^0 (mod p)
The largest necessary bigint is g^q-1, but can't be computed, npx ts-node Test.ts:
const crypto = require('crypto');
const dh = crypto.createDiffieHellman(1024);
const p = BigInt(`0x${dh.getPrime().toString('hex')}`);
const g = BigInt(`0x${dh.getGenerator().toString('hex')}`);
const q = (p - 1n)/2n;
console.log(g ** 0n % p)
console.log(g ** 1n % p)
console.log(g ** (q-1n) % p)
As expect, 1n and 2n are output, then:
console.log(g ** (q-1n) % p)
^
RangeError: Maximum BigInt size exceeded
What's going wrong?
g ** (q-1n) % p is too big because the reduction mod p is done only at the end and g ** (q-1n) is indeed too big for the standard representation as a BigInt: it has more hex digits than there are atoms in the universe.
This "intermediate overflow" would not happen if you reduced mod p after each multiplication (this does not change the result):
function powermod(base, exp, p) {
var result = 1n;
while (exp !== 0n) {
if (exp % 2n === 1n) result = result * base % p;
base = base * base % p;
exp >>= 1n;
}
return result;
}
console.log(powermod(g, q-1n, p));
(This is not necessarily the fastest way to compute the power, see taocp, section 4.6.3.)
powermod is a ternary operation which cannot be expressed in terms of the binary operations ** and %, unless a Javascript engine is able to recognize an expression like base ** exp % p and treat it as ternary. I don't know if such Javascript engines exist. But there are npm packages for "finite fields" that implement this operation.