diff options
| author | Peter Dettman <peter.dettman@bouncycastle.org> | 2023-12-06 22:42:30 +0700 |
|---|---|---|
| committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2023-12-06 22:42:30 +0700 |
| commit | fc3e516d427e5359f9b7d8deed8bfd7c5c2c90c9 (patch) | |
| tree | f3f1c05d3bfb66b590f3cdcb6082c55352cc7560 /crypto/src/util | |
| parent | Refactoring in Math.Raw.Nat (diff) | |
| download | BouncyCastle.NET-ed25519-fc3e516d427e5359f9b7d8deed8bfd7c5c2c90c9.tar.xz | |
Add fast coprime test
Diffstat (limited to 'crypto/src/util')
| -rw-r--r-- | crypto/src/util/BigIntegers.cs | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs index d1b15f869..8c2068688 100644 --- a/crypto/src/util/BigIntegers.cs +++ b/crypto/src/util/BigIntegers.cs @@ -265,5 +265,69 @@ namespace Org.BouncyCastle.Utilities return Nat.ToBigInteger(len, z); } } + + public static bool ModOddIsCoprime(BigInteger M, BigInteger X) + { + if (!M.TestBit(0)) + throw new ArgumentException("must be odd", nameof(M)); + if (M.SignValue != 1) + throw new ArithmeticException("BigInteger: modulus not positive"); + if (X.SignValue < 0 || X.CompareTo(M) >= 0) + { + X = X.Mod(M); + } + + int bits = M.BitLength; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + if (bits <= 2048) + { + int len = Nat.GetLengthForBits(bits); + Span<uint> m = stackalloc uint[len]; + Span<uint> x = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + return 0 != Mod.ModOddIsCoprime(m, x); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + return 0 != Mod.ModOddIsCoprime(m, x); + } + } + + public static bool ModOddIsCoprimeVar(BigInteger M, BigInteger X) + { + if (!M.TestBit(0)) + throw new ArgumentException("must be odd", nameof(M)); + if (M.SignValue != 1) + throw new ArithmeticException("BigInteger: modulus not positive"); + if (X.SignValue < 0 || X.CompareTo(M) >= 0) + { + X = X.Mod(M); + } + + int bits = M.BitLength; + +#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER + if (bits <= 2048) + { + int len = Nat.GetLengthForBits(bits); + Span<uint> m = stackalloc uint[len]; + Span<uint> x = stackalloc uint[len]; + Nat.FromBigInteger(bits, M, m); + Nat.FromBigInteger(bits, X, x); + return Mod.ModOddIsCoprimeVar(m, x); + } + else +#endif + { + uint[] m = Nat.FromBigInteger(bits, M); + uint[] x = Nat.FromBigInteger(bits, X); + return Mod.ModOddIsCoprimeVar(m, x); + } + } } } |