-//
+//
// BigInteger.cs - Big Integer implementation
//
// Authors:
//
// Copyright (c) 2002 Chew Keong TAN
// All rights reserved.
+//
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
using System;
using System.Security.Cryptography;
namespace Mono.Math {
- [CLSCompliant(false)]
#if INSIDE_CORLIB
internal
#else
/// </code>
/// </para>
/// </remarks>
- public static readonly uint [] smallPrimes = {
+ internal static readonly uint [] smallPrimes = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
public BigInteger ()
{
data = new uint [DEFAULT_LEN];
+ this.length = DEFAULT_LEN;
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger (Sign sign, uint len)
{
this.data = new uint [len];
this.length = bi.length;
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger (BigInteger bi, uint len)
{
this.Normalize ();
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger (uint [] inData)
{
length = (uint)inData.Length;
this.Normalize ();
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger (uint ui)
{
data = new uint [] {ui};
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger (ulong ul)
{
data = new uint [2] { (uint)ul, (uint)(ul >> 32)};
this.Normalize ();
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public static implicit operator BigInteger (uint value)
{
return (new BigInteger (value));
return (new BigInteger ((uint)value));
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public static implicit operator BigInteger (ulong value)
{
return (new BigInteger (value));
return -(int)Kernel.DwordMod (bi, (uint)-i);
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public static uint operator % (BigInteger bi, uint ui)
{
return Kernel.DwordMod (bi, (uint)ui);
#endregion
+ #region Friendly names for operators
+
+ // with names suggested by FxCop 1.30
+
+ public static BigInteger Add (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 + bi2);
+ }
+
+ public static BigInteger Subtract (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 - bi2);
+ }
+
+ public static int Modulus (BigInteger bi, int i)
+ {
+ return (bi % i);
+ }
+
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static uint Modulus (BigInteger bi, uint ui)
+ {
+ return (bi % ui);
+ }
+
+ public static BigInteger Modulus (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 % bi2);
+ }
+
+ public static BigInteger Divid (BigInteger bi, int i)
+ {
+ return (bi / i);
+ }
+
+ public static BigInteger Divid (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 / bi2);
+ }
+
+ public static BigInteger Multiply (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 * bi2);
+ }
+
+ public static BigInteger Multiply (BigInteger bi, int i)
+ {
+ return (bi * i);
+ }
+
+ #endregion
+
#region Random
private static RandomNumberGenerator rng;
private static RandomNumberGenerator Rng {
/// <param name="bits">The number of bits for the new number.</param>
/// <param name="rng">A random number generator to use to obtain the bits.</param>
/// <returns>A random number of the specified length.</returns>
- public static BigInteger genRandom (int bits, RandomNumberGenerator rng)
+ public static BigInteger GenerateRandom (int bits, RandomNumberGenerator rng)
{
int dwords = bits >> 5;
int remBits = bits & 0x1F;
/// </summary>
/// <param name="bits">The number of bits for the new number.</param>
/// <returns>A random number of the specified length.</returns>
- public static BigInteger genRandom (int bits)
+ public static BigInteger GenerateRandom (int bits)
{
- return genRandom (bits, Rng);
+ return GenerateRandom (bits, Rng);
}
/// <summary>
/// Randomizes the bits in "this" from the specified RNG.
/// </summary>
/// <param name="rng">A RNG.</param>
- public void randomize (RandomNumberGenerator rng)
+ public void Randomize (RandomNumberGenerator rng)
{
- int bits = this.bitCount ();
+ if (this == 0)
+ return;
+
+ int bits = this.BitCount ();
int dwords = bits >> 5;
int remBits = bits & 0x1F;
/// <summary>
/// Randomizes the bits in "this" from the default RNG.
/// </summary>
- public void randomize ()
+ public void Randomize ()
{
- randomize (Rng);
+ Randomize (Rng);
}
#endregion
#region Bitwise
- public int bitCount ()
+ public int BitCount ()
{
this.Normalize ();
/// </summary>
/// <param name="bitNum">The bit to test. The least significant bit is 0.</param>
/// <returns>True if bitNum is set to 1, else false.</returns>
- public bool testBit (uint bitNum)
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public bool TestBit (uint bitNum)
{
uint bytePos = bitNum >> 5; // divide by 32
byte bitPos = (byte)(bitNum & 0x1F); // get the lowest 5 bits
return ((this.data [bytePos] & mask) != 0);
}
- public bool testBit (int bitNum)
+ public bool TestBit (int bitNum)
{
if (bitNum < 0) throw new IndexOutOfRangeException ("bitNum out of range");
return ((this.data [bytePos] | mask) == this.data [bytePos]);
}
- public void setBit (uint bitNum)
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void SetBit (uint bitNum)
{
- setBit (bitNum, true);
+ SetBit (bitNum, true);
}
- public void clearBit (uint bitNum)
+
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void ClearBit (uint bitNum)
{
- setBit (bitNum, false);
+ SetBit (bitNum, false);
}
- public void setBit (uint bitNum, bool val)
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void SetBit (uint bitNum, bool value)
{
uint bytePos = bitNum >> 5; // divide by 32
if (bytePos < this.length) {
uint mask = (uint)1 << (int)(bitNum & 0x1F);
- if (val)
+ if (value)
this.data [bytePos] |= mask;
else
this.data [bytePos] &= ~mask;
{
if (this == 0) return -1;
int i = 0;
- while (!testBit (i)) i++;
+ while (!TestBit (i)) i++;
return i;
}
- public byte [] getBytes ()
+ public byte[] GetBytes ()
{
if (this == 0) return new byte [1];
- int numBits = bitCount ();
+ int numBits = BitCount ();
int numBytes = numBits >> 3;
if ((numBits & 0x7) != 0)
numBytes++;
#region Compare
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public static bool operator == (BigInteger bi1, uint ui)
{
if (bi1.length != 1) bi1.Normalize ();
return bi1.length == 1 && bi1.data [0] == ui;
}
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public static bool operator != (BigInteger bi1, uint ui)
{
if (bi1.length != 1) bi1.Normalize ();
#region Formatting
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public string ToString (uint radix)
{
return ToString (radix, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ");
}
- public string ToString (uint radix, string charSet)
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public string ToString (uint radix, string characterSet)
{
- if (charSet.Length < radix)
- throw new ArgumentException ("charSet length less than radix", "charSet");
+ if (characterSet.Length < radix)
+ throw new ArgumentException ("charSet length less than radix", "characterSet");
if (radix == 1)
throw new ArgumentException ("There is no such thing as radix one notation", "radix");
while (a != 0) {
uint rem = Kernel.SingleByteDivideInPlace (a, radix);
- result = charSet [ (int)rem] + result;
+ result = characterSet [(int) rem] + result;
}
return result;
#region Number Theory
- public BigInteger gcd (BigInteger bi)
+ public BigInteger GCD (BigInteger bi)
{
return Kernel.gcd (this, bi);
}
- public BigInteger modInverse (BigInteger mod)
+ public BigInteger ModInverse (BigInteger modulus)
{
- return Kernel.modInverse (this, mod);
+ return Kernel.modInverse (this, modulus);
}
- public BigInteger modPow (BigInteger exp, BigInteger n)
+ public BigInteger ModPow (BigInteger exp, BigInteger n)
{
ModulusRing mr = new ModulusRing (n);
return mr.Pow (this, exp);
#region Prime Testing
- public bool isProbablePrime ()
+ public bool IsProbablePrime ()
{
-
- for (int p = 0; p < smallPrimes.Length; p++) {
- if (this % smallPrimes [p] == 0)
- return this == smallPrimes [p];
+ if (this < smallPrimes [smallPrimes.Length - 1]) {
+ for (int p = 0; p < smallPrimes.Length; p++) {
+ if (this == smallPrimes [p])
+ return true;
+ }
}
- for (int p = 0; p < smallPrimes.Length; p++) {
- if (this == smallPrimes [p])
- return true;
- if (this % smallPrimes [p] == 0)
- return false;
+ else {
+ for (int p = 0; p < smallPrimes.Length; p++) {
+ if (this % smallPrimes [p] == 0)
+ return false;
+ }
}
return PrimalityTests.RabinMillerTest (this, Prime.ConfidenceFactor.Medium);
}
/// </summary>
/// <param name="bi">A BigInteger</param>
/// <returns>The smallest prime >= bi. More mathematically, if bi is prime: bi, else Prime [PrimePi [bi] + 1].</returns>
- public static BigInteger NextHightestPrime (BigInteger bi)
+ public static BigInteger NextHighestPrime (BigInteger bi)
{
NextPrimeFinder npf = new NextPrimeFinder ();
return npf.GenerateNewPrime (0, bi);
}
- public static BigInteger genPseudoPrime (int bits)
+ public static BigInteger GeneratePseudoPrime (int bits)
{
SequentialSearchPrimeGeneratorBase sspg = new SequentialSearchPrimeGeneratorBase ();
return sspg.GenerateNewPrime (bits);
BigInteger mod, constant;
- public ModulusRing (BigInteger mod)
+ public ModulusRing (BigInteger modulus)
{
- this.mod = mod;
+ this.mod = modulus;
// calculate constant = b^ (2k) / m
uint i = mod.length << 1;
r2.Normalize ();
- if (r2 < x) {
+ if (r2 <= x) {
Kernel.MinusEq (x, r2);
} else {
BigInteger val = new BigInteger (Sign.Positive, kPlusOne + 1);
BigInteger resultNum = new BigInteger ((BigInteger)1, mod.length << 1);
BigInteger tempNum = new BigInteger (b % mod, mod.length << 1); // ensures (tempNum * tempNum) < b^ (2k)
- uint totalBits = (uint)exp.bitCount ();
+ uint totalBits = (uint)exp.BitCount ();
uint [] wkspace = new uint [mod.length << 1];
// perform squaring and multiply exponentiation
for (uint pos = 0; pos < totalBits; pos++) {
- if (exp.testBit (pos)) {
+ if (exp.TestBit (pos)) {
Array.Clear (wkspace, 0, wkspace.Length);
Kernel.Multiply (resultNum.data, 0, resultNum.length, tempNum.data, 0, tempNum.length, wkspace, 0);
BigInteger resultNum = new BigInteger (Montgomery.ToMont (1, mod), mod.length << 1);
BigInteger tempNum = new BigInteger (Montgomery.ToMont (b, mod), mod.length << 1); // ensures (tempNum * tempNum) < b^ (2k)
uint mPrime = Montgomery.Inverse (mod.data [0]);
- uint totalBits = (uint)exp.bitCount ();
+ uint totalBits = (uint)exp.BitCount ();
uint [] wkspace = new uint [mod.length << 1];
// perform squaring and multiply exponentiation
for (uint pos = 0; pos < totalBits; pos++) {
- if (exp.testBit (pos)) {
+ if (exp.TestBit (pos)) {
Array.Clear (wkspace, 0, wkspace.Length);
Kernel.Multiply (resultNum.data, 0, resultNum.length, tempNum.data, 0, tempNum.length, wkspace, 0);
// TODO: Make tests for this, not really needed b/c prime stuff
// checks it, but still would be nice
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
public BigInteger Pow (uint b, BigInteger exp)
{
- if (b != 2) {
- if ((mod.data [0] & 1) == 1) return OddPow (b, exp);
- else return EvenPow (b, exp);
+// if (b != 2) {
+ if ((mod.data [0] & 1) == 1)
+ return OddPow (b, exp);
+ else
+ return EvenPow (b, exp);
+/* buggy in some cases (like the well tested primes)
} else {
- if ((mod.data [0] & 1) == 1) return OddModTwoPow (exp);
- else return EvenModTwoPow (exp);
- }
+ if ((mod.data [0] & 1) == 1)
+ return OddModTwoPow (exp);
+ else
+ return EvenModTwoPow (exp);
+ }*/
}
private unsafe BigInteger OddPow (uint b, BigInteger exp)
uint mPrime = Montgomery.Inverse (mod.data [0]);
- uint pos = (uint)exp.bitCount () - 2;
+ uint pos = (uint)exp.BitCount () - 2;
//
// We know that the first itr will make the val b
Kernel.SquarePositive (resultNum, ref wkspace);
resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
- if (exp.testBit (pos)) {
+ if (exp.TestBit (pos)) {
//
// r = r * b % m
// We would rather have this estimate overshoot,
// so we add one to the divisor
- uint divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
- (mod.data [mod.length-1] + 1));
+ uint divEstimate;
+ if (mod.data [mod.length - 1] < UInt32.MaxValue) {
+ divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
+ (mod.data [mod.length-1] + 1));
+ }
+ else {
+ // guess but don't divide by 0
+ divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
+ (mod.data [mod.length-1]));
+ }
uint t;
uint [] wkspace = new uint [mod.length << 1 + 1];
BigInteger resultNum = new BigInteger ((BigInteger)b, mod.length << 1 + 1);
- uint pos = (uint)exp.bitCount () - 2;
+ uint pos = (uint)exp.BitCount () - 2;
//
// We know that the first itr will make the val b
if (!(resultNum.length < mod.length))
BarrettReduction (resultNum);
- if (exp.testBit (pos)) {
+ if (exp.TestBit (pos)) {
//
// r = r * b % m
return resultNum;
}
+/* known to be buggy in some cases
private unsafe BigInteger EvenModTwoPow (BigInteger exp)
{
exp.Normalize ();
//
// TODO: eat small bits, the ones we can do with no modular reduction
//
- uint pos = (uint)exp.bitCount () - 2;
+ uint pos = (uint)exp.BitCount () - 2;
do {
Kernel.SquarePositive (resultNum, ref wkspace);
resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
- if (exp.testBit (pos)) {
+ if (exp.TestBit (pos)) {
//
// resultNum = (resultNum * 2) % mod
//
resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
return resultNum;
}
-
+*/
#endregion
}
- public sealed class Montgomery {
+ internal sealed class Montgomery {
+
+ private Montgomery ()
+ {
+ }
+
public static uint Inverse (uint n)
{
uint y = n, z;
// aDP = destination for bits
uint* mP = mm, aSP = a, aDP = a;
- ulong c = (ulong)u_i * (ulong)*(mP++) + *(aSP++);
+ ulong c = (ulong)u_i * ((ulong)*(mP++)) + *(aSP++);
c >>= 32;
uint j = 1;
return A;
}
-
+#if _NOT_USED_
public static BigInteger Reduce (BigInteger n, BigInteger m)
{
return Reduce (n, m, Inverse (m.data [0]));
}
+#endif
}
/// <summary>
}
}
- public static bool Double (uint [] u, int l)
+/*
+ * Never called in BigInteger (and part of a private class)
+ * public static bool Double (uint [] u, int l)
{
uint x, carry = 0;
uint i = 0;
}
if (carry != 0) u [l] = carry;
return carry != 0;
- }
+ }*/
#endregion
projects / mono.git / blobdiff