BigInteger.ModPow asserting in SubtractSelf #97780
Comments
ghost
added
the
|
Tagging subscribers to this area: @dotnet/area-system-numerics Issue DetailsDescriptionTrying to use BigInteger for test authoring is currently impeded by it asserting. Reproduction Stepsbyte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
BigInteger m = new BigInteger(buf, true, true);
BigInteger e = 65537;
buf = new byte[]
{
0xB1, 0x7C, 0xEE, 0x77, 0xB4, 0x59, 0xA4, 0x65,
0x92, 0x8D, 0x7F, 0x55, 0x77, 0x80, 0x39, 0xBA,
0x22, 0xBA, 0x29, 0xA5, 0xFF, 0xE5, 0x53, 0xFB,
0x40, 0x98, 0xA8, 0x35, 0xE5, 0x2D, 0x0A, 0xDC,
0x85, 0x17, 0x6E, 0xE4, 0xD6, 0x93, 0x82, 0x20,
0x71, 0x8D, 0xE9, 0xDD, 0xC9, 0xD5, 0xBD, 0x30,
0x47, 0xEE, 0x59, 0xB9, 0xE6, 0xA8, 0x79, 0x9E,
0x47, 0x96, 0x8E, 0x63, 0xCD, 0xA6, 0x28, 0x9D,
0x7B, 0x6D, 0x83, 0xAA, 0x68, 0xE2, 0x46, 0xD6,
0x1C, 0x8C, 0x2B, 0xA1, 0xC4, 0x04, 0x12, 0xAE,
0x61, 0x07, 0xAF, 0x6F, 0xE9, 0x2B, 0x48, 0x5C,
0xCA, 0xC2, 0x0E, 0x52, 0x71, 0x21, 0x03, 0xE0,
0x05, 0x1C, 0x07, 0xC0, 0x56, 0xFD, 0x8A, 0x61,
0x7A, 0x95, 0x39, 0x4B, 0xAA, 0x5A, 0x9D, 0x03,
0x6D, 0x7A, 0x51, 0x3E, 0x7A, 0xE4, 0xAB, 0xED,
0xB4, 0x0A, 0x88, 0x80, 0x3C, 0x07, 0xED, 0x19,
0x21, 0xA2, 0xDC, 0xD7, 0x9C, 0x3F, 0x3B, 0x19,
0x59, 0x33, 0x39, 0x8A, 0x25, 0xDB, 0xCE, 0x8D,
0x8E, 0x10, 0xDA, 0xB1, 0x38, 0x32, 0xCA, 0x59,
0xA1, 0x69, 0x3C, 0x23, 0x76, 0x50, 0x37, 0xB3,
0xBF, 0x73, 0x58, 0x77, 0x38, 0xC5, 0x16, 0x03,
0x60, 0x36, 0x0D, 0x31, 0x8C, 0xBE, 0xA5, 0x12,
0x2F, 0xE5, 0x16, 0xAD, 0x1C, 0x80, 0x01, 0x50,
0xEB, 0x3C, 0x86, 0x79, 0x22, 0xD3, 0x7F, 0xD4,
0x90, 0x85, 0xB8, 0xEB, 0xB0, 0x7D, 0xD8, 0xC8,
0x8B, 0xBB, 0x88, 0xBE, 0xFE, 0xB8, 0xBA, 0xAD,
0x61, 0xC7, 0xF9, 0x68, 0x20, 0xB2, 0xA9, 0x1D,
0xB4, 0xDC, 0xB0, 0x5B, 0xC7, 0xB3, 0xF2, 0x83,
0x35, 0x43, 0xB0, 0xAE, 0x19, 0x2B, 0xA6, 0xFA,
0x88, 0x48, 0xB9, 0xFB, 0xB3, 0xCD, 0xF8, 0xA9,
0x9C, 0x20, 0x6F, 0x63, 0x23, 0xE5, 0xC2, 0x85,
0xCD, 0x75, 0x7A, 0x55, 0x04, 0xA4, 0x08, 0x99,
};
BigInteger n = new BigInteger(buf, true, true);
BigInteger c = BigInteger.ModPow(m, e, n);Expected behaviorNo assertion. Actual behaviorRegression?No response Known WorkaroundsNo response ConfigurationNo response Other informationDefinitely happens on bc0b28f on both osx and win. The osx build merged up through 3bf9bee (main as of about an hour ago) and still sees the assert.
|
|
Tentatively marked this as 9.0.0. If it's not fully blocking though, we'll move it to Future. |
|
This is blocking test authoring for #97738; so, yes, it's "fully blocking" |
|
It appears that there is a flaw in the in that it incorrectly assumes that Minimal ReproductionBigInteger modulus = (BigInteger)3 << 1024;
BigInteger value = modulus;
int exponent = 2;
BigInteger.ModPow(value, exponent, value); // Assertion failure in debug buildsIt should be noted that superficially, the result appears to be correct using the following validation logic: BigInteger result = BigInteger.ModPow(value, exponent, modulus);
BigInteger expectedResult = 1;
for (int i = 0; i < exponent; i++)
{
expectedResult = (expectedResult * value) % modulus;
}
Assert.Equal(expectedResult, result); // Passes for given inputsHowever, I don't think it would be safe to simply comment out the asserts. The The final assert checking that |
|
I fuzzed the .NET 8 implementation with FsCheck, using parameters that trigger the assert failing: using FsCheck;
using FsCheck.Fluent;
using System.Numerics;
Config configuration = Config.Quick.WithMaxTest(10_000_000);
Parallel.For(0, Environment.ProcessorCount, i =>
{
Prop.ForAll<(int, int, byte)>(t => ModPowPropertyTest(t.Item1, t.Item2, t.Item3))
.Check(configuration);
});
static bool ModPowPropertyTest(int valueSeed, int modulusSpread, ushort exponent)
{
if (Math.Abs(valueSeed) < 2 || exponent < 2)
{
return true; // Skip trivial values
}
// Arrange
BigInteger value = (BigInteger)valueSeed << 1024; // To trigger the bug, uint[] representation needs to start with at least 32 zeros.
BigInteger modulus = value + modulusSpread; // The modulus must be approximately the same size as the value.
// Act
BigInteger result = BigInteger.ModPow(value, exponent, modulus);
// Assert
BigInteger expectedResult = 1;
for (int i = 0; i < exponent; i++)
{
expectedResult = (expectedResult * value) % modulus;
}
return expectedResult == result;
}After 160 million runs, no invalid outputs were detected. @jeffhandley I think we could try removing the asserts to unblock @bartonjs's work. |
If keeping a bit set in the least significant segment works around the problem, I'll give that a go. |
|
It seems to be more nuanced than just keeping a low bit set, since the number described by byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);
buf[^1] = 1;still asserted; but |
byte[] buf = new byte[2048 >> 3];
buf[1] = 2;
buf.AsSpan(2, 8).Fill(1);yields adding in yields Which looks the same to me. |
|
The two inputs trigger the same condition. TL;DR the implementation calculates the value If the least significant digits of the input value |
Description
Trying to use BigInteger for test authoring is currently impeded by it asserting.
Reproduction Steps
Expected behavior
No assertion.
Actual behavior
Regression?
No response
Known Workarounds
No response
Configuration
No response
Other information
Definitely happens on bc0b28f on both osx and win. The osx build merged up through 3bf9bee (main as of about an hour ago) and still sees the assert.
The text was updated successfully, but these errors were encountered: