mod_inverse

std.elementwise.mod_inverse · Level L4

The inverse of a modulo m, elementwise: the x in 0 … m − 1 with a·x ≡ 1 (mod m), from the Bézout certificate a·x + m·y = 1 that bezout gives. Where gcd(a, m) ≠ 1 there is no inverse: inv is 0 and ok is 0. Python's pow(a, −1, m).

a·x ≡ 1 (mod m)

Signature

mod_inverse(a: i64[n], m: i64[n]) → i64[n], f64[n]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference pow(a, -1, m) where gcd(a, m) = 1, else 0 in exact rational arithmetic, on all 40 test cases.
All 320 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 100%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 0

Identity

Calls

bezout

Called by

—

sha256:61244faf1e1ea3a4a0c070394f97c056ac8e9814af63b1386a8f348db8556761

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.elementwise.mod_inverse · Ω:mod_inverse
Pins: sha256:4b1bae5f60f6bda0ef3e1f01c9ab9a771b4223ff788de155a7583139c2bd65d8this graph and the 3 it reaches through calls
Evidence: sha256:98132437d412595d45315c58d45ac30e3fa25301790d053b3890681b8422aab6the hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.