nx_modinv.nx source
↩ module page · 33 lines · 1252 B
1// nx_modinv.nx -- modular multiplicative inverse via extended Euclidean.
2//
3// genealogy_id: bezout_1624_extended_via_knuth_taocp
4// lineage_id: modular_arithmetic
5// references: Knuth TAoCP Vol 2 4.5.2; Cohen 'CCANT' Alg 1.3.6.
6// license: public_domain
7// complexity: O(log m) divisions.
8
9// nx_safety_envelope:
10// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
11// sil_target: SIL1
12// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
13// verdict: NOT_YET_EVALUATED
14
15import "nx_syscalls.nx"
16import "nx_tier.nx"
17import "nx_extended_gcd.nx"
18
19// Returns the multiplicative inverse of a modulo m, in [0, m).
20// Returns 0 if no inverse exists (i.e. gcd(a, m) != 1) -- caller must
21// distinguish from the legitimate inverse value 0 when m == 1.
22func nx_modinv(a: nx_int, m: nx_int) -> nx_int {
23 if m <= 1 { return 0 }
24 let scratch_x: *u8 = sys_mmap(8)
25 let scratch_y: *u8 = sys_mmap(8)
26 let x: *nx_int = scratch_x as *nx_int
27 let y: *nx_int = scratch_y as *nx_int
28 let g: nx_int = nx_extended_gcd(a, m, x, y)
29 if g != 1 { return 0 }
30 var inv: nx_int = x[0] - (x[0] / m) * m // x mod m
31 if inv < 0 { inv = inv + m }
32 return inv
33}