Latest Results
perf: drop the Montgomery-form comparison from Pollard's rho
pollard_rho's inner loop computed the walker difference as an
abs-diff, comparing the two walkers before every subtraction.
Comparing two values in Montgomery form is meaningless numerically,
so Ord::cmp first converts both operands back through residue() --
a full REDC reduction each. That is two extra REDC reductions per
iteration, on top of the two the loop already performs (x^2 + c and
the batched-gcd accumulator update), and roughly half of the loop's
static instructions in the SmallMint<u64> instantiation.
For the accumulator the sign of the difference is irrelevant:
gcd(n, -t) = gcd(n, t). Replace the compare-and-subtract with the
modular subtraction subm, which is also total for the unsigned
big-integer instantiations where a plain subtraction could underflow.
This resolves the FIXME that pointed at the line.
Measured on 12 fixed semiprimes with ~25-bit factors, best of 20
in-process rounds, median of 3 runs, x86-64 release:
production 156.6 -> 179.7 Miter/s (+14.7%)
The walk is unchanged -- with fixed seeds the loop performs exactly
the same 69632 iterations as before. perf: drop the Montgomery-form comparison from Pollard's rho
pollard_rho's inner loop computed the walker difference as an
abs-diff, comparing the two walkers before every subtraction.
Comparing two values in Montgomery form is meaningless numerically,
so Ord::cmp first converts both operands back through residue() --
a full REDC reduction each. That is two extra REDC reductions per
iteration, on top of the two the loop already performs (x^2 + c and
the batched-gcd accumulator update), and roughly half of the loop's
static instructions in the SmallMint<u64> instantiation.
For the accumulator the sign of the difference is irrelevant:
gcd(n, -t) = gcd(n, t). Replace the compare-and-subtract with the
modular subtraction subm, which is also total for the unsigned
big-integer instantiations where a plain subtraction could underflow.
This resolves the FIXME that pointed at the line.
Measured on 12 fixed semiprimes with ~25-bit factors, best of 20
in-process rounds, median of 3 runs, x86-64 release:
production 156.6 -> 179.7 Miter/s (+14.7%)
The walk is unchanged -- with fixed seeds the loop performs exactly
the same 69632 iterations as before. Latest Branches
0%
xtqqczze:ci/minimal-permissions +24%
0%
renovate/either-1.x-lockfile © 2026 CodSpeed Technology