legendre_symbol

std.elementwise.legendre_symbol · Level L4

The Legendre symbol (a/p) for an odd prime p, elementwise: 0 if p divides a, 1 if a is a non-zero square modulo p, and −1 otherwise. Computed by Euler's criterion, a^((p−1)/2) mod p, through pow_mod. The reference instead searches for a square root, so the two routes are independent.

(a/p) ≡ a^((p−1)/2) (mod p)

Signature

legendre_symbol(a: i64[n], p: i64[n]) → i64[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 0 if p | a; 1 if some y has y² ≡ a (mod p); else −1 in exact rational arithmetic, on all 40 test cases.
All 146 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

p must be an odd prime; NOVA does not check it. For a composite p, Euler's criterion gives the Jacobi-like value it computes, not a Legendre symbol.

Identity

Calls

pow_mod

Called by

—

sha256:f311b124fb0716574d09ccb60b79f3ff2f4a71193db670326f4d4d906e9bca01

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

Control handle

Symbol: Ω:std.elementwise.legendre_symbol · Ω:legendre_symbol
Pins: sha256:45a7bd78ed494d87999454cb806db6211ee947ec9b7ee77ccb2a10878230def7this graph and the 3 it reaches through calls
Evidence: sha256:ba8081d56e8de2b8fb19b0d2a6dbf2aa39fcd8678b56084caa8423ab8b200728the 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.