Montgomery Orbit

Ciphers & Number Theory

A rotating multiplicative-group star polygon, computed with Montgomery modular multiplication — a·b mod N using only a multiply, a shift, a mask, and one conditional subtract, with no divide. The 65816 has no hardware divide, so this is how real crypto runs there. The build gate disassembles the loop and asserts zero division library calls. The orbit g⁰, g¹, g², … mod N traces the star. Compiler stress-test #84.

loading core…

Self-running — the multiplicative-group orbit rotates as a star polygon.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

In the integers mod a prime N, multiplication by a fixed generator g cycles through the whole group: 1, g, g², g³, … This demo maps each residue to an angle on a circle and connects consecutive orbit points, drawing a star polygon. Every frame the entire orbit is recomputed — and every one of those multiplications is done modulo N without a divide, using Montgomery reduction.

// Montgomery reduction: a*b mod N with NO divide — just multiply, shift, mask, subtract.
uint16_t redc(uint32_t T) {            // T = a*b, both < N
  uint16_t m = (uint16_t)((uint16_t)T * Nprime);   // __mulhi3 + mask (mod R)
  uint32_t t = (T + (uint32_t)m * N) >> 16;        // __mulsi3, then G_LSHR by 16
  uint16_t r = (uint16_t)t;
  if (r >= N) r -= N;                              // conditional subtract
  return r;                                        // in [0, N)
}
uint16_t mont_mul(uint16_t a, uint16_t b) { return redc((uint32_t)a * b); }  // __mulsi3

Montgomery form keeps numbers pre-scaled by R = 2¹⁶ so the reduction step is a shift instead of a divide. The result is exact integer arithmetic — bit-identical on the host and on the 65816 in all code-generation modes.

Compiler stress-test

Item	What it exercises
Montgomery REDC	Modular multiplication a·b mod N normally needs a divide (a·b then mod N). Montgomery's trick replaces the divide with a multiply-by-a-precomputed-constant, a shift, a mask, and one conditional subtract — all cheap on a CPU with no divide instruction. The 65816 has no hardware divide (software divide is dozens of cycles), so this is exactly how real crypto code runs there.
division-free (the gate proves it)	The build gate disassembles the hot loop and asserts it contains __mulsi3/__mulhi3 (32- and 16-bit multiply) and rep/sep, and ZERO division library calls (__udivsi3, __umodsi3, __udivmodsi4). If any divide crept in, the gate fails. This is the demo's whole point: modular arithmetic with no divide.
distinct from #61 / #20	#61 dhmix does 64-bit modular exponentiation the division-based way (__udivdi3/__umoddi3). #20 factorial and #19 pi use base-10000 bignums with __udivmodsi4. This is the only battery demo that does modmul entirely without a divide.
the orbit	The multiplicative group mod N is cyclic; iterating x → x·g mod N walks an orbit g⁰, g¹, g², … Each residue maps to an angle on a circle, and connecting consecutive points draws a star polygon whose density reflects the order of g. The whole orbit is recomputed every frame with Montgomery modmul (no divide), then rotated.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (modmul CRC 0xBA9B — a fold of the orbit residues) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean, and zero division library calls in the hot loop.