Barrett reduction requires x < 2^(2*bits(m)); the gate condition only
required x->sz >= y->sz + 2, which let x.sz reach 25 limbs against a
4-limb modulus. When the precondition is violated, mpz_barrett_reduce
silently truncates high limbs and returns garbage.
Integer#remainder, which routes through mpz_mod, was affected:
(3**500).remainder((2**100)+3) returned the wrong value. Integer#%
took the udiv path via mpz_mmod and was unaffected.
Add x->sz <= 2 * y->sz to the gate so out-of-range inputs fall
through to the general udiv path.
Co-authored-by: Claude <noreply@anthropic.com>
REDC's input T must satisfy T < R*N; mpz_powm_montgomery() computed
T = base * R^2 without first reducing base modulo n. When base >= n,
T exceeds R*N and REDC silently truncates upper limbs, producing a
wrong base_mont and ultimately a wrong result.
Use mpz_mmod (general division path) to pre-reduce base mod n before
the multiplication by R^2.
Visible effect: (2**160).pow(2, (2**40)+1) returned 0 instead of 1.
A separate pre-existing issue in mpz_mod's Barrett path (broken
precondition check) means that path could return a wrong reduction
for large operands; mmod sidesteps that path entirely.
Co-authored-by: Claude <noreply@anthropic.com>
Cover zero operands, power-of-2 fast path, negative operands,
balanced multi-limb pairs with a shared Fibonacci factor, highly
unbalanced pairs (to exercise the Euclidean fallback), and
Fibonacci neighbors (always coprime). Declare a test dependency
on mruby-numeric-ext since Integer#gcd is defined there.
Co-authored-by: Claude <noreply@anthropic.com>
Fixed non-commutative multiplication bug where operands with different
limb counts would produce different results based on order (a*b \!= b*a).
Root cause was asymmetric carry propagation in the multiplication algorithm.
The fix ensures consistent operand ordering by always processing the smaller
operand first in the nested loops, making multiplication truly commutative.
Also fixed division algorithm quotient allocation and qhat refinement.
Co-authored-by: Claude <noreply@anthropic.com>
Yukihiro "Matz" Matsumoto