evaluate-modular: integer literals are not reduced modulo the modulus (wrong, out-of-range results)

[GuoYH97]

Integer literals are stored into the modular register file unreduced, so evaluate-modular with a --modulus smaller than some literal in the trace returns wrong values — including values that are not residues at all. Tested against 88646ca7b65c24bfce3a8be6e1093a9b89731f23 (current master), built from a clean clone.

The one-line demonstration

Ask for the value of the constant -134217728 (= -2^27) modulo p = 134217689 (= 2^27 - 39):

$ echo -n '-134217728' > e.txt
$ ratracer trace-expression e.txt evaluate-modular --modulus=134217689
  18446744073709551577;

The answer should be 134217650. What comes back is 18446744073709551577 (= 2^64 - 39) — a number larger than the modulus, so it is not a residue under any convention.

Why

ratbox.h (lines 977–978):

#define INSTR_INT(dst, a, b, c) data[dst] = a;
#define INSTR_NEGINT(dst, a, b, c) data[dst] = nmod_neg(a, mod);

The literal a is copied in as-is. A trace is symbolic and modulus-independent — the modulus is only chosen later, at evaluate-modular/reconstruct time — so literals are stored raw (up to 2^40; Tracer::of_fmpz, ratracer.h:976, routes anything bigger through HOP_BIGINT, which is correct, since it goes through fmpz_get_nmod). Consequently data[] can hold a value >= mod.n, while FLINT's nmod_* primitives require reduced operands. Above, nmod_neg(a, mod) computes n - a with a = 134217728 > n = 134217689, which underflows to 2^64 - 39.

Whether it then shows depends on the arithmetic:

replay instruction	primitive	tolerant of unreduced input?
INSTR_MUL	nmod_mul (full 128-bit product, then reduce)	yes, accidentally
INSTR_ADD / INSTR_SUB	_nmod_add / _nmod_sub (one conditional subtraction)	no
INSTR_NEG / INSTR_NEGINT	nmod_neg (n - a)	no
INSTR_SHOUP_MUL, INSTR_ADDMUL	require reduced operands	no

That mix is what makes it unpleasant in practice: a wrong literal can pass through several operations and come out as a perfectly plausible-looking residue. Test 2 below is that case — 134217727 instead of 38, with nothing suspicious about it.

Two further points suggesting this is an oversight rather than an intended contract:

• the tracing path already reduces the same literal — Tracer::of_int (ratracer.h:952-971) records the opcode and keeps a shadow value that it reduces explicitly with NMOD_RED(c, x, tr.mod); only the two replay evaluators (code_evaluate_hi, code_evaluate_lo*) omit it;
• cmd_evaluate_modular reduces the user's other 64-bit input — values supplied with --set go through NMOD_RED(v, (ncoef_t)n, mod) before use. Inputs are reduced on entry, literals are not, though both feed the same register file and the same FLINT primitives.

Scope

The trigger is just some literal in the trace >= the modulus, and both sides are bounded:

• literals are capped at 2^40 by of_fmpz (ratracer.h:974), which is the only path by which parsed expressions and equations enter a trace (ratbox.h:1433); the two entry points that would bypass the cap, Tracer::mulint and Tracer::addint, appear to have no callers in the code base;
• all 1000 built-in primes are ~2^63 (9223372036854732683 … 9223372036854775783), and evaluate-modular defaults to 2^63-25.

So reconstruct — the main workflow — has a margin of about 2^23 and can never hit this. It is reachable only via a user-supplied evaluate-modular --modulus=p with p below the largest literal in the trace, i.e. a verification/debugging path, which is presumably why it has gone unnoticed. Nothing in the manual restricts the modulus (the entry for evaluate-modular reads only "Evaluate the trace modulo the given (small) integer modulus"), and there is no check or warning in the code.

We also checked that empirically, since it decides whether anything computed at the built-in primes is affected: on a real 2.1 GB trace, a pristine build and a patched build produce byte-identical output at 2^63-25 (all 174,684 values, and six to-series derivative runs), while 99.9 % of the same values differ at p = 134217689.

Reproducer

Needs nothing but /bin/sh and a ratracer binary. Exit status 0 = correct, 1 = bug present.

test	expression	modulus	got	correct
1	-2^27	2^27-39	18446744073709551577	134217650
2	2^27 + x, x = 134217688	2^27-39	134217727	38
3	-2^27 (control)	2^61-1	2305843009079476223	same — OK
4	2-equation system, solve-equations	2^27-39	131557463	134204347

Test 3 is the control: raise the modulus above the literal and everything is correct again, which isolates the literal-vs-modulus relation. Test 4 shows it surviving a load-equations/solve-equations pipeline.

reproduce.sh

#!/bin/sh
# Reproducer: ratracer's `evaluate-modular` returns wrong values when the traced
# expression contains an integer literal >= the evaluation modulus.
#
# Usage:  ./reproduce.sh [path-to-ratracer]      (default: `ratracer` on $PATH)

RATRACER=${1:-ratracer}
TMP=$(mktemp -d) || exit 1
trap 'rm -rf "$TMP"' EXIT

P=134217689          # prime, = 2^27 - 39
LIT=134217728        # = 2^27, the literal in the test expressions;  LIT > P

fail=0

ev() { # ev <expr-file> <modulus> [extra ratracer args...]
    f=$1; m=$2; shift 2
    "$RATRACER" trace-expression "$f" "$@" evaluate-modular --modulus="$m" 2>/dev/null \
        | tail -1 | tr -d ' ;'
}

check() { # check <name> <got> <want>
    if [ "$2" = "$3" ]; then
        printf '  %-46s %-22s OK\n' "$1" "$2"
    else
        printf '  %-46s %-22s WRONG (expected %s)\n' "$1" "$2" "$3"
        fail=1
    fi
}

echo "ratracer binary: $RATRACER"
echo "modulus p = $P (prime),   literal = $LIT = 2^27 > p"
echo

# Test 1.  The whole expression is the single constant -2^27.
#          Correct answer: (-2^27) mod p = 134217650.
echo "Test 1: constant -2^27, evaluated mod p"
printf -- '-134217728' > "$TMP/t1"
check "-2^27 mod p" "$(ev "$TMP/t1" $P)" 134217650

# Test 2.  Same thing, silent version: the wrong answer is a plausible residue.
#          (2^27 + 134217688) mod p = 268435416 - 2*134217689 = 38;
#          only one subtraction is performed: 268435416 - p = 134217727.
echo "Test 2: 2^27 + x  at x = 134217688 (the failure is silent here)"
printf '134217728+x' > "$TMP/t2"
v=$("$RATRACER" trace-expression "$TMP/t2" evaluate-modular --modulus=$P --set x 134217688 \
      2>/dev/null | tail -1 | tr -d ' ;')
check "(2^27 + 134217688) mod p" "$v" 38

# Test 3.  Control: same expression, modulus larger than the literal.
echo "Test 3: control, modulus 2^61-1 > 2^27 (must pass on any build)"
check "-2^27 mod (2^61-1)" "$(ev "$TMP/t1" 2305843009213693951)" 2305843009079476223

# Test 4.  A two-equation linear system in Kira format:
#            W@2 = W@1 ;  T@1 = (-2^27*x^3 + 5*x) * W@2
#          so CO[T@1,W@1] = -2^27*x^3 + 5*x, at x = 7:
#            -134217728*343 + 35 = -46036680669 == 134204347 (mod p)
echo "Test 4: two-equation system solved by ratracer (same literal)"
cat > "$TMP/t4.eqns" <<'EOF'
W@2*(1)
W@1*(-1)

T@1*(1)
W@2*(-(-134217728*x^3 + 5*x))
EOF
v=$("$RATRACER" load-equations "$TMP/t4.eqns" solve-equations \
      choose-equation-outputs --family=T \
      evaluate-modular --modulus=$P --set x 7 2>/dev/null | tail -1 | tr -d ' ;')
check "CO[T@1,W@1] at x=7" "$v" 134204347

echo
if [ $fail -eq 0 ]; then
    echo "RESULT: all tests pass -- this build reduces integer literals correctly."
else
    echo "RESULT: BUG REPRODUCED -- this build evaluates traces containing integer"
    echo "        literals >= the modulus incorrectly."
fi
exit $fail

A possible fix

Reduce the literal at evaluation time, with a fast path because almost every literal is already reduced. Both evaluators share these macros, so one edit covers both.

patch against ratbox.h at 88646ca

--- a/ratbox.h
+++ b/ratbox.h
@@ -974,8 +974,18 @@
 #define INSTR_VAR(dst, a, b, c) data[dst] = inputs[a];
-#define INSTR_INT(dst, a, b, c) data[dst] = a;
-#define INSTR_NEGINT(dst, a, b, c) data[dst] = nmod_neg(a, mod);
+/* Integer literals are stored in the trace unreduced (the trace is symbolic;
+ * the modulus is only known at evaluation time), so they must be reduced here.
+ * Fast path first, since almost every literal is already reduced. */
+#define NMOD_REDUCE_LIT(out, a) \
+    do { \
+        mp_limb_t lit_ = (mp_limb_t)(a); \
+        if (likely(lit_ < mod.n)) { (out) = lit_; } \
+        else { NMOD_RED((out), lit_, mod); } \
+    } while (0)
+#define INSTR_INT(dst, a, b, c) NMOD_REDUCE_LIT(data[dst], a);
+#define INSTR_NEGINT(dst, a, b, c) \
+    do { mp_limb_t t_; NMOD_REDUCE_LIT(t_, a); data[dst] = nmod_neg(t_, mod); } while (0);

The same treatment applies to INSTR_ASSERT_INT and INSTR_ASSERT_NEGINT, which compare against an unreduced literal. INSTR_BIGINT needs nothing.

On a patched build: all four tests pass; ./check passes before and after, so the change is regression-free (and the existing suite does not cover this case); and evaluation speed is unchanged — 3.34/3.39/3.34 µs per evaluation pristine vs 3.26/3.27/3.37 µs patched on a 4000-term two-variable expression at a 63-bit prime, with identical output.

The reduction could also be done once when the trace is loaded rather than per instruction, which would be cheaper still; it cannot be done at trace construction time, since the trace must stay modulus-independent. You may well prefer a different placement — the point of this report is the defect and the reproducer, not this particular patch. Happy to open a PR in whatever form suits you.

Context

We hit this in a Feynman-integral reduction: coefficients carrying literals such as 2^26 and 2^27 were evaluated at primes just below them (a small modulus chosen deliberately so that a wide integer matrix multiplication would stay exact), producing wrong but plausible numbers. Because the high- and low-level evaluators schedule operations differently, an unreduced literal can land in a tolerant operation in one and an intolerant one in the other, so finalized and un-finalized traces of the same system disagreed — which we first misdiagnosed as two separate defects and then as a physics problem. After the change above, both pipelines agree and our consistency checks pass.

Thanks for ratracer — it has been excellent to work with.

[magv]

Thanks a lot for finding this. I'll commit a fix (it in two weeks or so).