MillerRabinPrimalityChecker reuses a single random witness across all rounds (rounds parameter has no effect)

[aimasteracc]

Describe the bug

MillerRabinPrimalityChecker.IsProbablyPrimeNumber draws the random witness a once, before the rounds loop, and never re-draws it. Every round therefore tests the same base, which defeats the purpose of the rounds parameter and weakens the test below its documented accuracy.

Algorithms/Numeric/MillerRabinPrimalityChecker.cs:

BigInteger a = rand.Next(2, nMaxValue - 2); // line 52 — drawn ONCE, outside the loop

while (rounds > 0)                          // line 54
{
    rounds--;
    var x = BigInteger.ModPow(a, d, n);     // line 57 — same `a` every iteration
    ...
}

The Miller–Rabin test's accuracy bound (a composite is reported prime with probability ≤ 4⁻ᵏ for k rounds) requires an independent random base each round. With a fixed base, running k rounds is equivalent to running a single round: there is no accuracy gain, and a composite that is a strong pseudoprime to the one drawn base is reported "probably prime" regardless of how large rounds is. The XML doc on the parameter — "the parameter determines the accuracy of the test, recommended value is Log2(n)" — does not hold.

To Reproduce

For any fixed seed, the result and the witness are identical no matter how many rounds are requested:

// Same seed → same single witness → identical result; rounds has no effect.
bool a = MillerRabinPrimalityChecker.IsProbablyPrimeNumber(n, rounds: 1,    seed: 12345);
bool b = MillerRabinPrimalityChecker.IsProbablyPrimeNumber(n, rounds: 1000, seed: 12345);
// a == b always — extra rounds never change the answer.

Concrete consequence with a strong pseudoprime — n = 2047 = 23 × 89 is composite and is a strong pseudoprime to base 2. If the single drawn witness is 2, the method returns true ("probably prime") for rounds = 1 and for rounds = 1_000_000, because the would-be independent later rounds all re-use the liar base 2. A correct implementation re-randomizes the base each round and catches it with overwhelming probability.

Expected behavior

Each round should pick a fresh independent random base in [2, n − 2], so that increasing rounds increases accuracy and strong-liar bases are caught by subsequent rounds (matching the documented behavior and the standard algorithm).

Actual behavior

The base a is fixed for the whole call. rounds > 1 provides no additional accuracy, and a composite that fools the single drawn base is reported as probably prime for any number of rounds.

Suggested fix

Move the witness draw inside the loop:

while (rounds > 0)
{
    rounds--;
    BigInteger a = rand.Next(2, nMaxValue - 1); // fresh base each round
    var x = BigInteger.ModPow(a, d, n);
    ...
}

(Minor, same line: rand.Next(2, nMaxValue - 2) excludes n − 2 because Random.Next's upper bound is exclusive; rand.Next(2, nMaxValue - 1) yields the intended [2, n − 2] range.)

Additional context

The existing tests in Algorithms.Tests/Numeric/MillerRabinPrimalityTest.cs pass because each asserts a fixed (number, seed) pair where the single drawn base happens to give the correct verdict; none assert that additional rounds change/strengthen the outcome, so the defect is not currently covered. A regression test could assert that a known strong pseudoprime (e.g. 2047 to base 2) is reported composite once witnesses are re-randomized per round.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

[siriak]

Hi, feel free to pick it up and make a fix!

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.