`nx_pow_mod.nx` source

1// nx_pow_mod.nx -- fast modular exponentiation (binary method).
2//
3// genealogy_id: knuth_taocp_4_6_3_evaluation_of_powers
4// lineage_id:   modular_arithmetic_foundation
5// references:   Knuth TAoCP Vol 2 4.6.3; Cohen 'Computational Algebraic Number Theory'.
6// license:      public_domain
7// complexity:   O(log exp) multiplications mod m.
8//
9// Tier discipline: all arithmetic uses nx_int.  Caller must ensure
10// m^2 fits in nx_int (or use nx_i128 / nx_i256 variants for wider m).
11
12// nx_safety_envelope:
13//   intended_use:       AUTO_APPLIED -- primitive-specific tuning queued
14//   sil_target:         SIL1
15//   evidence:           [bulk_applied_2026-05-16, see-file-comment-for-detail]
16//   verdict:            NOT_YET_EVALUATED
17
18import "nx_syscalls.nx"
19import "nx_tier.nx"
20
21// Compute (base ^ exp) mod m.  Requires exp >= 0, m > 0.
22// Returns 0 for invalid inputs (defensive).
23func nx_pow_mod(base: nx_int, exp: nx_int, m: nx_int) -> nx_int {
24    if m <= 0 { return 0 }
25    if m == 1 { return 0 }
26    var b: nx_int = base - (base / m) * m              // base mod m
27    if b < 0 { b = b + m }
28    var e: nx_int = exp
29    var result: nx_int = 1
30    while e > 0 {
31        if (e - (e / 2) * 2) == 1 {                    // e is odd
32            result = (result * b) - ((result * b) / m) * m
33        }
34        e = e / 2
35        if e > 0 {
36            b = (b * b) - ((b * b) / m) * m
37        }
38    }
39    return result
40}
nx_pow_mod.nx source

`nx_pow_mod.nx` source
