System.Number.BigInteger.DivRem can output an incorrect remainder #72113
Description
Summary
Number.BigInteger.DivRem outputs an incorrect remainder when some of the computed remainder blocks are zero.
Explanation
Number.BigInteger is an internal helper type (not to be confused with the public System.Numerics.BigInteger), so reproduction is tricky, but I can outline the scenario that led to me discovering this bug.
Number.BigInteger is internally represented as an array of uints called _blocks, and an array length _length. This array is ordered from least significant to most significant.
Number.BigInteger.DivRem outputs a remainder called BigInteger rem. Right before returning, the algorithm attempts to cull rem blocks with value 0 by subtracting 1 from _length, essentially removing those extra unneeded blocks. However, while removing leading zero blocks is useful and harmless, the current algorithm also reduces the length when it finds a trailing zero block. For example, if the algorithm is intending to return a rem where _blocks = [0, 1], _length = 2, because of that trailing zero block it will reduce the length and end up returning _blocks = [0], _length = 1, which is incorrect.
Impact
The current usage of BigInteger.DivRem is limited, so I'd imagine it hasn't yet been called with an expected remainder that has a non-zero _block[1] and a zero _block[0]. I'm currently working on something that hits this case.
