multiplicative_order

std.elementwise.multiplicative_order · Level L4

The multiplicative order of a modulo n, elementwise: the smallest k ≥ 1 with aᵏ ≡ 1 (mod n), for gcd(a, n) = 1, found by taking powers until the first return to 1. Where gcd(a, n) ≠ 1 there is no order, and the result is 0.

ordₙ(a) = min{k ≥ 1 : aᵏ ≡ 1 (mod n)}

Signature

multiplicative_order(a: i64[s], n: i64[s]) → i64[s]

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 the first k ≥ 1 with pow(a, k, n) == 1 % n; 0 if gcd(a, n) > 1 in exact rational arithmetic, on all 40 test cases.
All 161 int64 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 int64 nearest the exact value): 100%
bit-equal to the NumPy formula in int64: 100%
largest error, in units in the last place: 0

Note

The loop takes ordₙ(a) ≤ φ(n) < n steps, so it suits moduli up to about 10⁵; max_steps is 10⁵. The verification uses n ≤ 500.

Identity

Calls

gcd order_running order_step

Called by

—

sha256:7beabdf8079a3634ea3542e0779084227d4f3a20c982db6944c01e6f5bc1153f

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

Control handle

Symbol: Ω:std.elementwise.multiplicative_order · Ω:multiplicative_order
Pins: sha256:0467d4516f848e5671b7127738abfc90225a336c74acfc9127044253996b3415this graph and the 5 it reaches through calls
Evidence: sha256:f127997f08eb5d73098d0f5bae66f5fc879187f0b24a8e2845480b8066117ca3the 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.