Valore numerico più grande del long ?

di il
4 risposte

Valore numerico più grande del long ?

Come faccio ad "avere" un numero maggiore del Long ?

Devo calcolare il Fattoriale di numeri da 1 a 90 ma al massimo posso calcolare il fattoriale di 20 perchè 21 mi restituisce già un numero per il quale 64 bit del long non bastano ...

Esiste un modo/tecnica di operare ?

4 Risposte

  • Re: Valore numerico più grande del long ?

    Devo fare :
    cT = totale numeri , cQ = quanti numeri

    totComb = numero di combinazioni unice "non ripetitive"
    totComb = fattoriale(cQ)/fatt(cT)*fatt(cT-cQ)

    il valore "massimo" x fatt(cT) è cT = 20 (usando i long)
    (oppure 16, non ricordo)

    con cT = 90 , cQ = 10
    totComb = fatt(90)/fatt(10)*fatt(90-10)

    "a mano" si può "semplificare"
    = 90*89*88*87*86... / 10*9*8*7... * 80*79*78*77*76...

    all' interno di una funzione come si potrebbe fare ???
    o in um altro modo ???



    c'è un modo per "semplificare"
  • Re: Valore numerico più grande del long ?

    Su una rivista ho trovato:
    ... l'ultima spiaggia risulta la costruzione di un tipo. [cut] Per la costruzione di tali tipi si possono adottare, come strutture dati, delle liste a puntatori per le quali ogni nodo rappresenta una cifra del numero, in tal modo si possono trattare numeri molto grandi (l'unico limite è la memoria RAM). Però attenzione quest'ultima soluzione prevede la definizione delle operazioni sui nuovi tipi costruiti.

    come si potrebbe fare ?
  • Re: Valore numerico più grande del long ?

    Devi usare per forza il long? usa il double...
  • Re: Valore numerico più grande del long ?

    Ecco un implementazione della classe che hai visto sul giornale, si chiama BigInt
    Buon divertimento, Andrea




    mailto:

    using System;

    namespace Mathematics {

    /// <summary>
    /// Classe che gestisce numeri grandi
    /// </summary>
    public class BigInteger {
    // maximum length of the BigInteger in uint (4 bytes)
    // change this to suit the required level of precision.
    private const int maxLength = 1024;

    private uint[] data = null; // stores bytes from the Big Integer
    internal int dataLength; // number of actual chars used

    /// <summary>
    /// Constructor (Default value for BigInteger is 0
    /// </summary>
    public BigInteger() {
    data = new uint[maxLength];
    dataLength = 1;
    }
    /// <summary>
    /// Constructor (Default value provided by long)
    /// </summary>
    /// <param name="value"></param>
    public BigInteger(long value) {
    data = new uint[maxLength];
    long tempVal = value;

    // copy bytes from long to BigInteger without any assumption of
    // the length of the long datatype

    dataLength = 0;
    while(value != 0 && dataLength < maxLength) {
    data[dataLength] = (uint)(value & 0xFFFFFFFF);
    value >>= 32;
    dataLength++;
    }

    if(tempVal > 0) { // overflow check for +ve value
    if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
    throw(new ArithmeticException("Positive overflow in constructor."));
    }
    else if(tempVal < 0) { // underflow check for -ve value
    if(value != -1 || (data[dataLength-1] & 0x80000000) == 0)
    throw(new ArithmeticException("Negative underflow in constructor."));
    }

    if(dataLength == 0)
    dataLength = 1;
    }
    /// <summary>
    /// Constructor (Default value provided by ulong)
    /// </summary>
    /// <param name="value"></param>
    public BigInteger(ulong value) {
    data = new uint[maxLength];

    // copy bytes from ulong to BigInteger without any assumption of
    // the length of the ulong datatype

    dataLength = 0;
    while(value != 0 && dataLength < maxLength) {
    data[dataLength] = (uint)(value & 0xFFFFFFFF);
    value >>= 32;
    dataLength++;
    }

    if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
    throw(new ArithmeticException("Positive overflow in constructor."));

    if(dataLength == 0)
    dataLength = 1;
    }
    /// <summary>
    /// Constructor (Default value provided by BigInteger)
    /// </summary>
    /// <param name="bi"></param>
    public BigInteger(BigInteger bi) {
    data = new uint[maxLength];

    dataLength = bi.dataLength;

    for(int i = 0; i < dataLength; i++)
    data[i] = bi.data[i];
    }
    /// <summary>
    /// Constructor (Default value provided by a string of digits of the
    /// specified base)
    ///
    /// Example (base 10)
    /// -----------------
    /// To initialize "a" with the default value of 1234 in base 10
    /// BigInteger a = new BigInteger("1234", 10)
    ///
    /// To initialize "a" with the default value of -1234
    /// BigInteger a = new BigInteger("-1234", 10)
    ///
    /// Example (base 16)
    /// -----------------
    /// To initialize "a" with the default value of 0x1D4F in base 16
    /// BigInteger a = new BigInteger("1D4F", 16)
    ///
    /// To initialize "a" with the default value of -0x1D4F
    /// BigInteger a = new BigInteger("-1D4F", 16)
    ///
    /// Note that string values are specified in the sign magnitude
    /// format.
    /// </summary>
    /// <param name="value"></param>
    /// <param name="radix"></param>
    public BigInteger(string value, int radix) {
    BigInteger multiplier = new BigInteger(1);
    BigInteger result = new BigInteger();
    value = (value.ToUpper()).Trim();
    int limit = 0;

    if(value[0] == '-')
    limit = 1;

    for(int i = value.Length - 1; i >= limit ; i--) {
    int posVal = (int)value[i];

    if(posVal >= '0' && posVal <= '9')
    posVal -= '0';
    else if(posVal >= 'A' && posVal <= 'Z')
    posVal = (posVal - 'A') + 10;
    else
    posVal = 9999999; // arbitrary large


    if(posVal >= radix)
    throw(new ArithmeticException("Invalid string in constructor."));
    else {
    if(value[0] == '-')
    posVal = -posVal;

    result = result + (multiplier * posVal);

    if((i - 1) >= limit)
    multiplier = multiplier * radix;
    }
    }

    if(value[0] == '-') { // negative values
    if((result.data[maxLength-1] & 0x80000000) == 0)
    throw(new ArithmeticException("Negative underflow in constructor."));
    }
    else { // positive values
    if((result.data[maxLength-1] & 0x80000000) != 0)
    throw(new ArithmeticException("Positive overflow in constructor."));
    }

    data = new uint[maxLength];
    for(int i = 0; i < result.dataLength; i++)
    data[i] = result.data[i];

    dataLength = result.dataLength;
    }
    /// <summary>
    /// Constructor (Default value provided by an array of bytes)
    ///
    /// The lowest index of the input byte array (i.e [0]) should contain the
    /// most significant byte of the number, and the highest index should
    /// contain the least significant byte.
    ///
    /// E.g.
    /// To initialize "a" with the default value of 0x1D4F in base 16
    /// byte[] temp = { 0x1D, 0x4F };
    /// BigInteger a = new BigInteger(temp)
    ///
    /// Note that this method of initialization does not allow the
    /// sign to be specified.
    /// </summary>
    /// <param name="inData"></param>
    public BigInteger(byte[] inData) {
    dataLength = inData.Length >> 2;

    int leftOver = inData.Length & 0x3;
    if(leftOver != 0) // length not multiples of 4
    dataLength++;


    if(dataLength > maxLength)
    throw(new ArithmeticException("Byte overflow in constructor."));

    data = new uint[maxLength];

    for(int i = inData.Length - 1, j = 0; i >= 3; i -= 4, j++) {
    data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
    (inData[i-1] << 8) + inData[i]);
    }

    if(leftOver == 1)
    data[dataLength-1] = (uint)inData[0];
    else if(leftOver == 2)
    data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
    else if(leftOver == 3)
    data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);


    while(dataLength > 1 && data[dataLength-1] == 0)
    dataLength--;

    //Console.WriteLine("Len = " + dataLength);
    }
    /// <summary>
    /// Constructor (Default value provided by an array of bytes of the specified length.)
    /// </summary>
    /// <param name="inData"></param>
    /// <param name="inLen"></param>
    public BigInteger(byte[] inData, int inLen) {
    dataLength = inLen >> 2;

    int leftOver = inLen & 0x3;
    if(leftOver != 0) // length not multiples of 4
    dataLength++;

    if(dataLength > maxLength || inLen > inData.Length)
    throw(new ArithmeticException("Byte overflow in constructor."));


    data = new uint[maxLength];

    for(int i = inLen - 1, j = 0; i >= 3; i -= 4, j++) {
    data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
    (inData[i-1] << 8) + inData[i]);
    }

    if(leftOver == 1)
    data[dataLength-1] = (uint)inData[0];
    else if(leftOver == 2)
    data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
    else if(leftOver == 3)
    data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);


    if(dataLength == 0)
    dataLength = 1;

    while(dataLength > 1 && data[dataLength-1] == 0)
    dataLength--;

    //Console.WriteLine("Len = " + dataLength);
    }
    /// <summary>
    /// Constructor (Default value provided by an array of unsigned integers)
    /// </summary>
    /// <param name="inData"></param>
    public BigInteger(uint[] inData) {
    dataLength = inData.Length;

    if(dataLength > maxLength)
    throw(new ArithmeticException("Byte overflow in constructor."));

    data = new uint[maxLength];

    for(int i = dataLength - 1, j = 0; i >= 0; i--, j++)
    data[j] = inData[i];

    while(dataLength > 1 && data[dataLength-1] == 0)
    dataLength--;

    //Console.WriteLine("Len = " + dataLength);
    }
    /// <summary>
    /// Overloading of the typecast operator.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public static implicit operator BigInteger(long value) {
    return (new BigInteger(value));
    }
    /// <summary>
    /// Overloading of the typecast operator.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public static implicit operator BigInteger(ulong value) {
    return (new BigInteger(value));
    }
    /// <summary>
    /// Overloading of the typecast operator.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public static implicit operator BigInteger(int value) {
    return (new BigInteger((long)value));
    }
    /// <summary>
    /// Overloading of the typecast operator.
    /// </summary>
    /// <param name="value"></param>
    /// <returns></returns>
    public static implicit operator BigInteger(uint value) {
    return (new BigInteger((ulong)value));
    }
    /// <summary>
    /// Overloading of addition operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator +(BigInteger bi1, BigInteger bi2) {
    BigInteger result = new BigInteger();

    result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

    long carry = 0;
    for(int i = 0; i < result.dataLength; i++) {
    long sum = (long)bi1.data[i] + (long)bi2.data[i] + carry;
    carry = sum >> 32;
    result.data[i] = (uint)(sum & 0xFFFFFFFF);
    }

    if(carry != 0 && result.dataLength < maxLength) {
    result.data[result.dataLength] = (uint)(carry);
    result.dataLength++;
    }

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;


    // overflow check
    int lastPos = maxLength - 1;
    if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
    throw (new ArithmeticException());
    }

    return result;
    }
    /// <summary>
    /// Overloading of the unary ++ operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <returns></returns>
    public static BigInteger operator ++(BigInteger bi1) {
    BigInteger result = new BigInteger(bi1);

    long val, carry = 1;
    int index = 0;

    while(carry != 0 && index < maxLength) {
    val = (long)(result.data[index]);
    val++;

    result.data[index] = (uint)(val & 0xFFFFFFFF);
    carry = val >> 32;

    index++;
    }

    if(index > result.dataLength)
    result.dataLength = index;
    else {
    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;
    }

    // overflow check
    int lastPos = maxLength - 1;

    // overflow if initial value was +ve but ++ caused a sign
    // change to negative.

    if((bi1.data[lastPos] & 0x80000000) == 0 &&
    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
    throw (new ArithmeticException("Overflow in ++."));
    }
    return result;
    }
    /// <summary>
    /// Overloading of subtraction operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator -(BigInteger bi1, BigInteger bi2) {
    BigInteger result = new BigInteger();

    result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

    long carryIn = 0;
    for(int i = 0; i < result.dataLength; i++) {
    long diff;

    diff = (long)bi1.data[i] - (long)bi2.data[i] - carryIn;
    result.data[i] = (uint)(diff & 0xFFFFFFFF);

    if(diff < 0)
    carryIn = 1;
    else
    carryIn = 0;
    }

    // roll over to negative
    if(carryIn != 0) {
    for(int i = result.dataLength; i < maxLength; i++)
    result.data[i] = 0xFFFFFFFF;
    result.dataLength = maxLength;
    }

    // fixed in v1.03 to give correct datalength for a - (-b)
    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    // overflow check

    int lastPos = maxLength - 1;
    if((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
    throw (new ArithmeticException());
    }
    return result;
    }
    /// <summary>
    /// Overloading of the unary -- operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <returns></returns>
    public static BigInteger operator --(BigInteger bi1) {
    BigInteger result = new BigInteger(bi1);

    long val;
    bool carryIn = true;
    int index = 0;

    while(carryIn && index < maxLength) {
    val = (long)(result.data[index]);
    val--;

    result.data[index] = (uint)(val & 0xFFFFFFFF);

    if(val >= 0)
    carryIn = false;

    index++;
    }

    if(index > result.dataLength)
    result.dataLength = index;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    // overflow check
    int lastPos = maxLength - 1;

    // overflow if initial value was -ve but -- caused a sign
    // change to positive.

    if((bi1.data[lastPos] & 0x80000000) != 0 &&
    (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
    throw (new ArithmeticException("Underflow in --."));
    }

    return result;
    }
    /// <summary>
    /// Overloading of multiplication operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator *(BigInteger bi1, BigInteger bi2) {
    int lastPos = maxLength-1;
    bool bi1Neg = false, bi2Neg = false;

    // take the absolute value of the inputs
    try {
    if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
    bi1Neg = true; bi1 = -bi1;
    }
    if((bi2.data[lastPos] & 0x80000000) != 0) { // bi2 negative
    bi2Neg = true; bi2 = -bi2;
    }
    } catch {}

    BigInteger result = new BigInteger();

    // multiply the absolute values
    try {
    for(int i = 0; i < bi1.dataLength; i++) {
    if(bi1.data[i] == 0) continue;

    ulong mcarry = 0;
    for(int j = 0, k = i; j < bi2.dataLength; j++, k++) {
    // k = i + j
    ulong val = ((ulong)bi1.data[i] * (ulong)bi2.data[j]) +
    (ulong)result.data[k] + mcarry;

    result.data[k] = (uint)(val & 0xFFFFFFFF);
    mcarry = (val >> 32);
    }

    if(mcarry != 0)
    result.data[i+bi2.dataLength] = (uint)mcarry;
    }
    } catch(Exception) {
    throw(new ArithmeticException("Multiplication overflow."));
    }

    result.dataLength = bi1.dataLength + bi2.dataLength;
    if(result.dataLength > maxLength)
    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    // overflow check (result is -ve)
    if((result.data[lastPos] & 0x80000000) != 0) {
    if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000) { // different sign
    // handle the special case where multiplication produces
    // a max negative number in 2's complement.

    if(result.dataLength == 1)
    return result;
    else {
    bool isMaxNeg = true;
    for(int i = 0; i < result.dataLength - 1 && isMaxNeg; i++) {
    if(result.data[i] != 0)
    isMaxNeg = false;
    }

    if(isMaxNeg)
    return result;
    }
    }
    throw(new ArithmeticException("Multiplication overflow."));
    }

    // if input has different signs, then result is -ve
    if(bi1Neg != bi2Neg)
    return -result;

    return result;
    }
    /// <summary>
    /// Overloading of unary 'Left Shift' operators
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="shiftVal"></param>
    /// <returns></returns>
    public static BigInteger operator <<(BigInteger bi1, int shiftVal) {
    BigInteger result = new BigInteger(bi1);
    result.dataLength = shiftLeft(result.data, shiftVal);

    return result;
    }
    /// <summary>
    /// Left Shift
    /// </summary>
    /// <param name="buffer"></param>
    /// <param name="shiftVal"></param>
    /// <returns></returns>
    private static int shiftLeft(uint[] buffer, int shiftVal) {
    int shiftAmount = 32;
    int bufLen = buffer.Length;

    while(bufLen > 1 && buffer[bufLen-1] == 0)
    bufLen--;

    for(int count = shiftVal; count > 0;) {
    if(count < shiftAmount)
    shiftAmount = count;

    //Console.WriteLine("shiftAmount = {0}", shiftAmount);

    ulong carry = 0;
    for(int i = 0; i < bufLen; i++) {
    ulong val = ((ulong)buffer[i]) << shiftAmount;
    val |= carry;

    buffer[i] = (uint)(val & 0xFFFFFFFF);
    carry = val >> 32;
    }

    if(carry != 0) {
    if(bufLen + 1 <= buffer.Length) {
    buffer[bufLen] = (uint)carry;
    bufLen++;
    }
    }
    count -= shiftAmount;
    }
    return bufLen;
    }
    /// <summary>
    /// Overloading of unary >> operators
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="shiftVal"></param>
    /// <returns></returns>
    public static BigInteger operator >>(BigInteger bi1, int shiftVal) {
    BigInteger result = new BigInteger(bi1);
    result.dataLength = shiftRight(result.data, shiftVal);


    if((bi1.data[maxLength-1] & 0x80000000) != 0) { // negative
    for(int i = maxLength - 1; i >= result.dataLength; i--)
    result.data[i] = 0xFFFFFFFF;

    uint mask = 0x80000000;
    for(int i = 0; i < 32; i++) {
    if((result.data[result.dataLength-1] & mask) != 0)
    break;

    result.data[result.dataLength-1] |= mask;
    mask >>= 1;
    }
    result.dataLength = maxLength;
    }

    return result;
    }
    /// <summary>
    /// Right Shift
    /// </summary>
    /// <param name="buffer"></param>
    /// <param name="shiftVal"></param>
    /// <returns></returns>
    private static int shiftRight(uint[] buffer, int shiftVal) {
    int shiftAmount = 32;
    int invShift = 0;
    int bufLen = buffer.Length;

    while(bufLen > 1 && buffer[bufLen-1] == 0)
    bufLen--;

    //Console.WriteLine("bufLen = " + bufLen + " buffer.Length = " + buffer.Length);

    for(int count = shiftVal; count > 0;) {
    if(count < shiftAmount) {
    shiftAmount = count;
    invShift = 32 - shiftAmount;
    }

    //Console.WriteLine("shiftAmount = {0}", shiftAmount);

    ulong carry = 0;
    for(int i = bufLen - 1; i >= 0; i--) {
    ulong val = ((ulong)buffer[i]) >> shiftAmount;
    val |= carry;

    carry = ((ulong)buffer[i]) << invShift;
    buffer[i] = (uint)(val);
    }

    count -= shiftAmount;
    }

    while(bufLen > 1 && buffer[bufLen-1] == 0)
    bufLen--;

    return bufLen;
    }
    /// <summary>
    /// Overloading of the NOT operator (1's complement)
    /// </summary>
    /// <param name="bi1"></param>
    /// <returns></returns>
    public static BigInteger operator ~(BigInteger bi1) {
    BigInteger result = new BigInteger(bi1);

    for(int i = 0; i < maxLength; i++)
    result.data[i] = (uint)(~(bi1.data[i]));

    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    return result;
    }
    /// <summary>
    /// Overloading of the NEGATE operator (2's complement)
    /// </summary>
    /// <param name="bi1"></param>
    /// <returns></returns>
    public static BigInteger operator -(BigInteger bi1) {
    // handle neg of zero separately since it'll cause an overflow
    // if we proceed.

    if(bi1.dataLength == 1 && bi1.data[0] == 0)
    return (new BigInteger());

    BigInteger result = new BigInteger(bi1);

    // 1's complement
    for(int i = 0; i < maxLength; i++)
    result.data[i] = (uint)(~(bi1.data[i]));

    // add one to result of 1's complement
    long val, carry = 1;
    int index = 0;

    while(carry != 0 && index < maxLength) {
    val = (long)(result.data[index]);
    val++;

    result.data[index] = (uint)(val & 0xFFFFFFFF);
    carry = val >> 32;

    index++;
    }

    if((bi1.data[maxLength-1] & 0x80000000) == (result.data[maxLength-1] & 0x80000000))
    throw (new ArithmeticException("Overflow in negation.\n"));

    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;
    return result;
    }
    /// <summary>
    /// Overloading of equality operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator ==(BigInteger bi1, BigInteger bi2) {
    return bi1.Equals(bi2);
    }
    /// <summary>
    /// Overloading of inequality operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator !=(BigInteger bi1, BigInteger bi2) {
    return !(bi1.Equals(bi2));
    }
    /// <summary>
    /// Overloading of equality operator
    /// </summary>
    /// <param name="o"></param>
    /// <returns></returns>
    public override bool Equals(object o) {
    BigInteger bi = (BigInteger)o;

    if(this.dataLength != bi.dataLength)
    return false;

    for(int i = 0; i < this.dataLength; i++) {
    if(this.data[i] != bi.data[i])
    return false;
    }
    return true;
    }
    /// <summary>
    /// Restituisce il codice Hash per l'istanza
    /// </summary>
    /// <returns></returns>
    public override int GetHashCode() {
    return this.ToString().GetHashCode();
    }
    /// <summary>
    /// Overloading of > operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator >(BigInteger bi1, BigInteger bi2) {
    int pos = maxLength - 1;

    // bi1 is negative, bi2 is positive
    if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
    return false;

    // bi1 is positive, bi2 is negative
    else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
    return true;

    // same sign
    int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
    for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);

    if(pos >= 0) {
    if(bi1.data[pos] > bi2.data[pos])
    return true;
    return false;
    }
    return false;
    }
    /// <summary>
    /// Overloading of 'minor' operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator <(BigInteger bi1, BigInteger bi2) {
    int pos = maxLength - 1;

    // bi1 is negative, bi2 is positive
    if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
    return true;

    // bi1 is positive, bi2 is negative
    else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
    return false;

    // same sign
    int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
    for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);

    if(pos >= 0) {
    if(bi1.data[pos] < bi2.data[pos])
    return true;
    return false;
    }
    return false;
    }
    /// <summary>
    /// Overloading of >= operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator >=(BigInteger bi1, BigInteger bi2) {
    return (bi1 == bi2 || bi1 > bi2);
    }
    /// <summary>
    /// Overloading of 'minor or equals' operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static bool operator <=(BigInteger bi1, BigInteger bi2) {
    return (bi1 == bi2 || bi1 < bi2);
    }
    /// <summary>
    /// Private function that supports the division of two numbers with
    /// a divisor that has more than 1 digit.
    ///
    /// Algorithm taken from [1]
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <param name="outQuotient"></param>
    /// <param name="outRemainder"></param>
    private static void multiByteDivide(BigInteger bi1, BigInteger bi2, BigInteger outQuotient, BigInteger outRemainder) {
    uint[] result = new uint[maxLength];

    int remainderLen = bi1.dataLength + 1;
    uint[] remainder = new uint[remainderLen];

    uint mask = 0x80000000;
    uint val = bi2.data[bi2.dataLength - 1];
    int shift = 0, resultPos = 0;

    while(mask != 0 && (val & mask) == 0) {
    shift++; mask >>= 1;
    }

    //Console.WriteLine("shift = {0}", shift);
    //Console.WriteLine("Before bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);

    for(int i = 0; i < bi1.dataLength; i++)
    remainder[i] = bi1.data[i];
    shiftLeft(remainder, shift);
    bi2 = bi2 << shift;

    /*
    Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
    Console.WriteLine("dividend = " + bi1 + "\ndivisor = " + bi2);
    for(int q = remainderLen - 1; q >= 0; q--)
    Console.Write("{0:x2}", remainder[q]);
    Console.WriteLine();
    */

    int j = remainderLen - bi2.dataLength;
    int pos = remainderLen - 1;

    ulong firstDivisorByte = bi2.data[bi2.dataLength-1];
    ulong secondDivisorByte = bi2.data[bi2.dataLength-2];

    int divisorLen = bi2.dataLength + 1;
    uint[] dividendPart = new uint[divisorLen];

    while(j > 0) {
    ulong dividend = ((ulong)remainder[pos] << 32) + (ulong)remainder[pos-1];
    //Console.WriteLine("dividend = {0}", dividend);

    ulong q_hat = dividend / firstDivisorByte;
    ulong r_hat = dividend % firstDivisorByte;

    //Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat);

    bool done = false;
    while(!done) {
    done = true;

    if(q_hat == 0x100000000 ||
    (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-2])) {
    q_hat--;
    r_hat += firstDivisorByte;

    if(r_hat < 0x100000000)
    done = false;
    }
    }

    for(int h = 0; h < divisorLen; h++)
    dividendPart[h] = remainder[pos-h];

    BigInteger kk = new BigInteger(dividendPart);
    BigInteger ss = bi2 * (long)q_hat;

    //Console.WriteLine("ss before = " + ss);
    while(ss > kk) {
    q_hat--;
    ss -= bi2;
    //Console.WriteLine(ss);
    }
    BigInteger yy = kk - ss;

    //Console.WriteLine("ss = " + ss);
    //Console.WriteLine("kk = " + kk);
    //Console.WriteLine("yy = " + yy);

    for(int h = 0; h < divisorLen; h++)
    remainder[pos-h] = yy.data[bi2.dataLength-h];

    /*
    Console.WriteLine("dividend = ");
    for(int q = remainderLen - 1; q >= 0; q--)
    Console.Write("{0:x2}", remainder[q]);
    Console.WriteLine("\n************ q_hat = {0:X}\n", q_hat);
    */

    result[resultPos++] = (uint)q_hat;

    pos--;
    j--;
    }

    outQuotient.dataLength = resultPos;
    int y = 0;
    for(int x = outQuotient.dataLength - 1; x >= 0; x--, y++)
    outQuotient.data[y] = result[x];
    for(; y < maxLength; y++)
    outQuotient.data[y] = 0;

    while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
    outQuotient.dataLength--;

    if(outQuotient.dataLength == 0)
    outQuotient.dataLength = 1;

    outRemainder.dataLength = shiftRight(remainder, shift);

    for(y = 0; y < outRemainder.dataLength; y++)
    outRemainder.data[y] = remainder[y];
    for(; y < maxLength; y++)
    outRemainder.data[y] = 0;
    }
    /// <summary>
    /// Private function that supports the division of two numbers with
    /// a divisor that has only 1 digit.
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <param name="outQuotient"></param>
    /// <param name="outRemainder"></param>
    private static void singleByteDivide(BigInteger bi1, BigInteger bi2, BigInteger outQuotient, BigInteger outRemainder) {
    uint[] result = new uint[maxLength];
    int resultPos = 0;

    // copy dividend to reminder
    for(int i = 0; i < maxLength; i++)
    outRemainder.data[i] = bi1.data[i];
    outRemainder.dataLength = bi1.dataLength;

    while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
    outRemainder.dataLength--;

    ulong divisor = (ulong)bi2.data[0];
    int pos = outRemainder.dataLength - 1;
    ulong dividend = (ulong)outRemainder.data[pos];

    //Console.WriteLine("divisor = " + divisor + " dividend = " + dividend);
    //Console.WriteLine("divisor = " + bi2 + "\ndividend = " + bi1);

    if(dividend >= divisor) {
    ulong quotient = dividend / divisor;
    result[resultPos++] = (uint)quotient;

    outRemainder.data[pos] = (uint)(dividend % divisor);
    }
    pos--;

    while(pos >= 0) {
    //Console.WriteLine(pos);

    dividend = ((ulong)outRemainder.data[pos+1] << 32) + (ulong)outRemainder.data[pos];
    ulong quotient = dividend / divisor;
    result[resultPos++] = (uint)quotient;

    outRemainder.data[pos+1] = 0;
    outRemainder.data[pos--] = (uint)(dividend % divisor);
    //Console.WriteLine(">>>> " + bi1);
    }

    outQuotient.dataLength = resultPos;
    int j = 0;
    for(int i = outQuotient.dataLength - 1; i >= 0; i--, j++)
    outQuotient.data[j] = result[i];
    for(; j < maxLength; j++)
    outQuotient.data[j] = 0;

    while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
    outQuotient.dataLength--;

    if(outQuotient.dataLength == 0)
    outQuotient.dataLength = 1;

    while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
    outRemainder.dataLength--;
    }
    /// <summary>
    /// Overloading of division operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator /(BigInteger bi1, BigInteger bi2) {
    BigInteger quotient = new BigInteger();
    BigInteger remainder = new BigInteger();

    int lastPos = maxLength-1;
    bool divisorNeg = false, dividendNeg = false;

    if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
    bi1 = -bi1;
    dividendNeg = true;
    }
    if((bi2.data[lastPos] & 0x80000000) != 0) { // bi2 negative
    bi2 = -bi2;
    divisorNeg = true;
    }

    if(bi1 < bi2) {
    return quotient;
    }

    else {
    if(bi2.dataLength == 1)
    singleByteDivide(bi1, bi2, quotient, remainder);
    else
    multiByteDivide(bi1, bi2, quotient, remainder);

    if(dividendNeg != divisorNeg)
    return -quotient;

    return quotient;
    }
    }
    /// <summary>
    /// Overloading of modulus operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator %(BigInteger bi1, BigInteger bi2) {
    BigInteger quotient = new BigInteger();
    BigInteger remainder = new BigInteger(bi1);

    int lastPos = maxLength-1;
    bool dividendNeg = false;

    if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
    bi1 = -bi1;
    dividendNeg = true;
    }
    if((bi2.data[lastPos] & 0x80000000) != 0) // bi2 negative
    bi2 = -bi2;

    if(bi1 < bi2) {
    return remainder;
    }

    else {
    if(bi2.dataLength == 1)
    singleByteDivide(bi1, bi2, quotient, remainder);
    else
    multiByteDivide(bi1, bi2, quotient, remainder);

    if(dividendNeg)
    return -remainder;

    return remainder;
    }
    }
    /// <summary>
    /// Overloading of bitwise AND operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator &(BigInteger bi1, BigInteger bi2) {
    BigInteger result = new BigInteger();

    int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

    for(int i = 0; i < len; i++) {
    uint sum = (uint)(bi1.data[i] & bi2.data[i]);
    result.data[i] = sum;
    }

    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    return result;
    }
    /// <summary>
    /// Overloading of bitwise OR operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator |(BigInteger bi1, BigInteger bi2) {
    BigInteger result = new BigInteger();

    int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

    for(int i = 0; i < len; i++) {
    uint sum = (uint)(bi1.data[i] | bi2.data[i]);
    result.data[i] = sum;
    }

    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    return result;
    }
    /// <summary>
    /// Overloading of bitwise XOR operator
    /// </summary>
    /// <param name="bi1"></param>
    /// <param name="bi2"></param>
    /// <returns></returns>
    public static BigInteger operator ^(BigInteger bi1, BigInteger bi2) {
    BigInteger result = new BigInteger();

    int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;

    for(int i = 0; i < len; i++) {
    uint sum = (uint)(bi1.data[i] ^ bi2.data[i]);
    result.data[i] = sum;
    }

    result.dataLength = maxLength;

    while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
    result.dataLength--;

    return result;
    }
    /// <summary>
    /// Returns max(this, bi)
    /// </summary>
    /// <param name="bi"></param>
    /// <returns></returns>
    public BigInteger max(BigInteger bi) {
    if(this > bi)
    return (new BigInteger(this));
    else
    return (new BigInteger(bi));
    }
    /// <summary>
    /// Returns min(this, bi)
    /// </summary>
    /// <param name="bi"></param>
    /// <returns></returns>
    public BigInteger min(BigInteger bi) {
    if(this < bi)
    return (new BigInteger(this));
    else
    return (new BigInteger(bi));

    }
    /// <summary>
    /// Returns the absolute value
    /// </summary>
    /// <returns></returns>
    public BigInteger abs() {
    if((this.data[maxLength - 1] & 0x80000000) != 0)
    return (-this);
    else
    return (new BigInteger(this));
    }
    /// <summary>
    /// Returns a string representing the BigInteger in base 10.
    /// </summary>
    /// <returns></returns>
    public override string ToString() {
    return ToString(10);
    }
    /// <summary>
    /// Returns a string representing the BigInteger in sign-and-magnitude
    /// format in the specified radix.
    ///
    /// Example
    /// -------
    /// If the value of BigInteger is -255 in base 10, then
    /// ToString(16) returns "-FF"
    /// </summary>
    /// <param name="radix"></param>
    /// <returns></returns>
    public string ToString(int radix) {
    if(radix < 2 || radix > 36)
    throw (new ArgumentException("Radix must be >= 2 and <= 36"));

    string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string result = "";

    BigInteger a = this;

    bool negative = false;
    if((a.data[maxLength-1] & 0x80000000) != 0) {
    negative = true;
    try {
    a = -a;
    }
    catch(Exception) {}
    }

    BigInteger quotient = new BigInteger();
    BigInteger remainder = new BigInteger();
    BigInteger biRadix = new BigInteger(radix);

    if(a.dataLength == 1 && a.data[0] == 0)
    result = "0";
    else {
    while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0)) {
    singleByteDivide(a, biRadix, quotient, remainder);

    if(remainder.data[0] < 10)
    result = remainder.data[0] + result;
    else
    result = charSet[(int)remainder.data[0] - 10] + result;

    a = quotient;
    }
    if(negative)
    result = "-" + result;
    }

    return result;
    }
    /// <summary>
    /// Returns a hex string showing the contains of the BigInteger
    ///
    /// Examples
    /// -------
    /// 1) If the value of BigInteger is 255 in base 10, then
    /// ToHexString() returns "FF"
    ///
    /// 2) If the value of BigInteger is -255 in base 10, then
    /// ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
    /// which is the 2's complement representation of -255.
    /// </summary>
    /// <returns></returns>
    public string ToHexString() {
    string result = data[dataLength - 1].ToString("X");

    for(int i = dataLength - 2; i >= 0; i--) {
    result += data[i].ToString("X8");
    }

    return result;
    }
    /// <summary>
    /// Modulo Exponentiation
    /// </summary>
    /// <param name="exp"></param>
    /// <param name="n"></param>
    /// <returns></returns>
    public BigInteger modPow(BigInteger exp, BigInteger n) {
    if((exp.data[maxLength-1] & 0x80000000) != 0)
    throw (new ArithmeticException("Positive exponents only."));

    BigInteger resultNum = 1;
    BigInteger tempNum;
    bool thisNegative = false;

    if((this.data[maxLength-1] & 0x80000000) != 0) { // negative this
    tempNum = -this % n;
    thisNegative = true;
    }
    else
    tempNum = this % n; // ensures (tempNum * tempNum) < b^(2k)

    if((n.data[maxLength-1] & 0x80000000) != 0) // negative n
    n = -n;

    // calculate constant = b^(2k) / m
    BigInteger constant = new BigInteger();

    int i = n.dataLength << 1;
    constant.data[i] = 0x00000001;
    constant.dataLength = i + 1;

    constant = constant / n;
    int totalBits = exp.bitCount();
    int count = 0;

    // perform squaring and multiply exponentiation
    for(int pos = 0; pos < exp.dataLength; pos++) {
    uint mask = 0x01;
    //Console.WriteLine("pos = " + pos);

    for(int index = 0; index < 32; index++) {
    if((exp.data[pos] & mask) != 0)
    resultNum = BarrettReduction(resultNum * tempNum, n, constant);

    mask <<= 1;

    tempNum = BarrettReduction(tempNum * tempNum, n, constant);


    if(tempNum.dataLength == 1 && tempNum.data[0] == 1) {
    if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
    return -resultNum;
    return resultNum;
    }
    count++;
    if(count == totalBits)
    break;
    }
    }

    if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
    return -resultNum;

    return resultNum;
    }
    /// <summary>
    /// Fast calculation of modular reduction using Barrett's reduction.
    /// Requires b^(2k) > x, where b is the base. In this case, base is
    /// 2^32 (uint).
    ///
    /// Reference [4]
    /// </summary>
    /// <param name="x"></param>
    /// <param name="n"></param>
    /// <param name="constant"></param>
    /// <returns></returns>
    private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant) {
    int k = n.dataLength,
    kPlusOne = k+1,
    kMinusOne = k-1;

    BigInteger q1 = new BigInteger();

    // q1 = x / b^(k-1)
    for(int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
    q1.data[j] = x.data[i];
    q1.dataLength = x.dataLength - kMinusOne;
    if(q1.dataLength <= 0)
    q1.dataLength = 1;


    BigInteger q2 = q1 * constant;
    BigInteger q3 = new BigInteger();

    // q3 = q2 / b^(k+1)
    for(int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
    q3.data[j] = q2.data[i];
    q3.dataLength = q2.dataLength - kPlusOne;
    if(q3.dataLength <= 0)
    q3.dataLength = 1;


    // r1 = x mod b^(k+1)
    // i.e. keep the lowest (k+1) words
    BigInteger r1 = new BigInteger();
    int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
    for(int i = 0; i < lengthToCopy; i++)
    r1.data[i] = x.data[i];
    r1.dataLength = lengthToCopy;


    // r2 = (q3 * n) mod b^(k+1)
    // partial multiplication of q3 and n

    BigInteger r2 = new BigInteger();
    for(int i = 0; i < q3.dataLength; i++) {
    if(q3.data[i] == 0) continue;

    ulong mcarry = 0;
    int t = i;
    for(int j = 0; j < n.dataLength && t < kPlusOne; j++, t++) {
    // t = i + j
    ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
    (ulong)r2.data[t] + mcarry;

    r2.data[t] = (uint)(val & 0xFFFFFFFF);
    mcarry = (val >> 32);
    }

    if(t < kPlusOne)
    r2.data[t] = (uint)mcarry;
    }
    r2.dataLength = kPlusOne;
    while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
    r2.dataLength--;

    r1 -= r2;
    if((r1.data[maxLength-1] & 0x80000000) != 0) { // negative
    BigInteger val = new BigInteger();
    val.data[kPlusOne] = 0x00000001;
    val.dataLength = kPlusOne + 1;
    r1 += val;
    }

    while(r1 >= n)
    r1 -= n;

    return r1;
    }
    /// <summary>
    /// Returns gcd(this, bi)
    /// </summary>
    /// <param name="bi"></param>
    /// <returns></returns>
    public BigInteger gcd(BigInteger bi) {
    BigInteger x;
    BigInteger y;

    if((data[maxLength-1] & 0x80000000) != 0) // negative
    x = -this;
    else
    x = this;

    if((bi.data[maxLength-1] & 0x80000000) != 0) // negative
    y = -bi;
    else
    y = bi;

    BigInteger g = y;

    while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0)) {
    g = x;
    x = y % x;
    y = g;
    }

    return g;
    }
    /// <summary>
    /// Populates "this" with the specified amount of random bits
    /// </summary>
    /// <param name="bits"></param>
    /// <param name="rand"></param>
    public void genRandomBits(int bits, Random rand) {
    int dwords = bits >> 5;
    int remBits = bits & 0x1F;

    if(remBits != 0)
    dwords++;

    if(dwords > maxLength)
    throw (new ArithmeticException("Number of required bits > maxLength."));

    for(int i = 0; i < dwords; i++)
    data[i] = (uint)(rand.NextDouble() * 0x100000000);

    for(int i = dwords; i < maxLength; i++)
    data[i] = 0;

    if(remBits != 0) {
    uint mask = (uint)(0x01 << (remBits-1));
    data[dwords-1] |= mask;

    mask = (uint)(0xFFFFFFFF >> (32 - remBits));
    data[dwords-1] &= mask;
    }
    else
    data[dwords-1] |= 0x80000000;

    dataLength = dwords;

    if(dataLength == 0)
    dataLength = 1;
    }
    /// <summary>
    /// Returns the position of the most significant bit in the BigInteger.
    ///
    /// Eg. The result is 0, if the value of BigInteger is 0...0000 0000
    /// The result is 1, if the value of BigInteger is 0...0000 0001
    /// The result is 2, if the value of BigInteger is 0...0000 0010
    /// The result is 2, if the value of BigInteger is 0...0000 0011
    /// </summary>
    /// <returns></returns>
    public int bitCount() {
    while(dataLength > 1 && data[dataLength-1] == 0)
    dataLength--;

    uint value = data[dataLength - 1];
    uint mask = 0x80000000;
    int bits = 32;

    while(bits > 0 && (value & mask) == 0) {
    bits--;
    mask >>= 1;
    }
    bits += ((dataLength - 1) << 5);

    return bits;
    }
    /// <summary>
    /// Probabilistic prime test based on Fermat's little theorem
    ///
    /// for any p > a (p does not divide a) if
    /// a^(p-1) mod p != 1 then p is not prime.
    ///
    /// Otherwise, p is probably prime (pseudoprime to the chosen base).
    ///
    /// Returns
    /// -------
    /// True if "this" is a pseudoprime to randomly chosen
    /// bases. The number of chosen bases is given by the "confidence"
    /// parameter.
    ///
    /// False if "this" is definitely NOT prime.
    ///
    /// Note - this method is fast but fails for Carmichael numbers except
    /// when the randomly chosen base is a factor of the number.
    /// </summary>
    /// <param name="confidence"></param>
    /// <returns></returns>
    public bool FermatLittleTest(int confidence) {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    if(thisVal.dataLength == 1) {
    // test small numbers
    if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
    return false;
    else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
    return true;
    }

    if((thisVal.data[0] & 0x1) == 0) // even numbers
    return false;

    int bits = thisVal.bitCount();
    BigInteger a = new BigInteger();
    BigInteger p_sub1 = thisVal - (new BigInteger(1));
    Random rand = new Random();

    for(int round = 0; round < confidence; round++) {
    bool done = false;

    while(!done) { // generate a < n
    int testBits = 0;

    // make sure "a" has at least 2 bits
    while(testBits < 2)
    testBits = (int)(rand.NextDouble() * bits);

    a.genRandomBits(testBits, rand);

    int byteLen = a.dataLength;

    // make sure "a" is not 0
    if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
    done = true;
    }

    // check whether a factor exists (fix for version 1.03)
    BigInteger gcdTest = a.gcd(thisVal);
    if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
    return false;

    // calculate a^(p-1) mod p
    BigInteger expResult = a.modPow(p_sub1, thisVal);

    int resultLen = expResult.dataLength;

    // is NOT prime is a^(p-1) mod p != 1

    if(resultLen > 1 || (resultLen == 1 && expResult.data[0] != 1)) {
    //Console.WriteLine("a = " + a.ToString());
    return false;
    }
    }
    return true;
    }
    /// <summary>
    /// Probabilistic prime test based on Rabin-Miller's
    ///
    /// for any p > 0 with p - 1 = 2^s * t
    ///
    /// p is probably prime (strong pseudoprime) if for any p > a,
    /// 1) a^t mod p = 1 or
    /// 2) a^((2^j)*t) mod p = p-1 for some s-1 >= j >= 0
    ///
    /// Otherwise, p is composite.
    ///
    /// Returns
    /// -------
    /// True if "this" is a strong pseudoprime to randomly chosen
    /// bases. The number of chosen bases is given by the "confidence"
    /// parameter.
    ///
    /// False if "this" is definitely NOT prime.
    /// </summary>
    /// <param name="confidence"></param>
    /// <returns></returns>
    public bool RabinMillerTest(int confidence) {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    if(thisVal.dataLength == 1) {
    // test small numbers
    if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
    return false;
    else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
    return true;
    }

    if((thisVal.data[0] & 0x1) == 0) // even numbers
    return false;

    // calculate values of s and t
    BigInteger p_sub1 = thisVal - (new BigInteger(1));
    int s = 0;

    for(int index = 0; index < p_sub1.dataLength; index++) {
    uint mask = 0x01;

    for(int i = 0; i < 32; i++) {
    if((p_sub1.data[index] & mask) != 0) {
    index = p_sub1.dataLength; // to break the outer loop
    break;
    }
    mask <<= 1;
    s++;
    }
    }

    BigInteger t = p_sub1 >> s;

    int bits = thisVal.bitCount();
    BigInteger a = new BigInteger();
    Random rand = new Random();

    for(int round = 0; round < confidence; round++) {
    bool done = false;

    while(!done) { // generate a < n
    int testBits = 0;

    // make sure "a" has at least 2 bits
    while(testBits < 2)
    testBits = (int)(rand.NextDouble() * bits);

    a.genRandomBits(testBits, rand);

    int byteLen = a.dataLength;

    // make sure "a" is not 0
    if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
    done = true;
    }

    // check whether a factor exists (fix for version 1.03)
    BigInteger gcdTest = a.gcd(thisVal);
    if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
    return false;

    BigInteger b = a.modPow(t, thisVal);

    /*
    Console.WriteLine("a = " + a.ToString(10));
    Console.WriteLine("b = " + b.ToString(10));
    Console.WriteLine("t = " + t.ToString(10));
    Console.WriteLine("s = " + s);
    */

    bool result = false;

    if(b.dataLength == 1 && b.data[0] == 1) // a^t mod p = 1
    result = true;

    for(int j = 0; result == false && j < s; j++) {
    if(b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
    result = true;
    break;
    }

    b = (b * b) % thisVal;
    }
    if(result == false)
    return false;
    }
    return true;
    }
    /// <summary>
    /// Probabilistic prime test based on Solovay-Strassen (Euler Criterion)
    ///
    /// p is probably prime if for any p > a (a is not multiple of p),
    /// a^((p-1)/2) mod p = J(a, p)
    ///
    /// where J is the Jacobi symbol.
    ///
    /// Otherwise, p is composite.
    ///
    /// Returns
    /// -------
    /// True if "this" is a Euler pseudoprime to randomly chosen
    /// bases. The number of chosen bases is given by the "confidence"
    /// parameter.
    ///
    /// False if "this" is definitely NOT prime.
    /// </summary>
    /// <param name="confidence"></param>
    /// <returns></returns>
    public bool SolovayStrassenTest(int confidence) {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    if(thisVal.dataLength == 1) {
    // test small numbers
    if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
    return false;
    else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
    return true;
    }

    if((thisVal.data[0] & 0x1) == 0) // even numbers
    return false;

    int bits = thisVal.bitCount();
    BigInteger a = new BigInteger();
    BigInteger p_sub1 = thisVal - 1;
    BigInteger p_sub1_shift = p_sub1 >> 1;

    Random rand = new Random();

    for(int round = 0; round < confidence; round++) {
    bool done = false;

    while(!done) { // generate a < n
    int testBits = 0;

    // make sure "a" has at least 2 bits
    while(testBits < 2)
    testBits = (int)(rand.NextDouble() * bits);

    a.genRandomBits(testBits, rand);

    int byteLen = a.dataLength;

    // make sure "a" is not 0
    if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
    done = true;
    }

    // check whether a factor exists (fix for version 1.03)
    BigInteger gcdTest = a.gcd(thisVal);
    if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
    return false;

    // calculate a^((p-1)/2) mod p

    BigInteger expResult = a.modPow(p_sub1_shift, thisVal);
    if(expResult == p_sub1)
    expResult = -1;

    // calculate Jacobi symbol
    BigInteger jacob = Jacobi(a, thisVal);

    //Console.WriteLine("a = " + a.ToString(10) + " b = " + thisVal.ToString(10));
    //Console.WriteLine("expResult = " + expResult.ToString(10) + " Jacob = " + jacob.ToString(10));

    // if they are different then it is not prime
    if(expResult != jacob)
    return false;
    }
    return true;
    }
    /// <summary>
    /// Implementation of the Lucas Strong Pseudo Prime test.
    ///
    /// Let n be an odd number with gcd(n,D) = 1, and n - J(D, n) = 2^s * d
    /// with d odd and s >= 0.
    ///
    /// If Ud mod n = 0 or V2^r*d mod n = 0 for some s > r >= 0, then n
    /// is a strong Lucas pseudoprime with parameters (P, Q). We select
    /// P and Q based on Selfridge.
    ///
    /// Returns True if number is a strong Lucus pseudo prime.
    /// Otherwise, returns False indicating that number is composite.
    /// </summary>
    /// <returns></returns>
    public bool LucasStrongTest() {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    if(thisVal.dataLength == 1) {
    // test small numbers
    if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
    return false;
    else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
    return true;
    }

    if((thisVal.data[0] & 0x1) == 0) // even numbers
    return false;

    return LucasStrongTestHelper(thisVal);
    }
    private bool LucasStrongTestHelper(BigInteger thisVal) {
    // Do the test (selects D based on Selfridge)
    // Let D be the first element of the sequence
    // 5, -7, 9, -11, 13, ... for which J(D,n) = -1
    // Let P = 1, Q = (1-D) / 4

    long D = 5, sign = -1, dCount = 0;
    bool done = false;

    while(!done) {
    int Jresult = BigInteger.Jacobi(D, thisVal);

    if(Jresult == -1) {
    done = true; // J(D, this) = 1
    } else {
    if(Jresult == 0 && System.Math.Abs(D) < thisVal) // divisor found
    return false;

    if(dCount == 20) {
    // check for square
    BigInteger root = thisVal.sqrt();
    if(root * root == thisVal)
    return false;
    }

    //Console.WriteLine(D);
    D = (System.Math.Abs(D) + 2) * sign;
    sign = -sign;
    }
    dCount++;
    }

    long Q = (1 - D) >> 2;

    /*
    Console.WriteLine("D = " + D);
    Console.WriteLine("Q = " + Q);
    Console.WriteLine("(n,D) = " + thisVal.gcd(D));
    Console.WriteLine("(n,Q) = " + thisVal.gcd(Q));
    Console.WriteLine("J(D|n) = " + BigInteger.Jacobi(D, thisVal));
    */

    BigInteger p_add1 = thisVal + 1;
    int s = 0;

    for(int index = 0; index < p_add1.dataLength; index++) {
    uint mask = 0x01;

    for(int i = 0; i < 32; i++) {
    if((p_add1.data[index] & mask) != 0) {
    index = p_add1.dataLength; // to break the outer loop
    break;
    }
    mask <<= 1;
    s++;
    }
    }

    BigInteger t = p_add1 >> s;

    // calculate constant = b^(2k) / m
    // for Barrett Reduction
    BigInteger constant = new BigInteger();

    int nLen = thisVal.dataLength << 1;
    constant.data[nLen] = 0x00000001;
    constant.dataLength = nLen + 1;

    constant = constant / thisVal;

    BigInteger[] lucas = LucasSequenceHelper(1, Q, t, thisVal, constant, 0);
    bool isPrime = false;

    if((lucas[0].dataLength == 1 && lucas[0].data[0] == 0) ||
    (lucas[1].dataLength == 1 && lucas[1].data[0] == 0)) {
    // u(t) = 0 or V(t) = 0
    isPrime = true;
    }
    for(int i = 1; i < s; i++) {
    if(!isPrime) {
    // doubling of index
    lucas[1] = thisVal.BarrettReduction(lucas[1] * lucas[1], thisVal, constant);
    lucas[1] = (lucas[1] - (lucas[2] << 1)) % thisVal;

    //lucas[1] = ((lucas[1] * lucas[1]) - (lucas[2] << 1)) % thisVal;

    if((lucas[1].dataLength == 1 && lucas[1].data[0] == 0))
    isPrime = true;
    }
    lucas[2] = thisVal.BarrettReduction(lucas[2] * lucas[2], thisVal, constant); //Q^k
    }
    if(isPrime) { // additional checks for composite numbers
    // If n is prime and gcd(n, Q) == 1, then
    // Q^((n+1)/2) = Q * Q^((n-1)/2) is congruent to (Q * J(Q, n)) mod n

    BigInteger g = thisVal.gcd(Q);
    if(g.dataLength == 1 && g.data[0] == 1) { // gcd(this, Q) == 1
    if((lucas[2].data[maxLength-1] & 0x80000000) != 0)
    lucas[2] += thisVal;

    BigInteger temp = (Q * BigInteger.Jacobi(Q, thisVal)) % thisVal;
    if((temp.data[maxLength-1] & 0x80000000) != 0)
    temp += thisVal;

    if(lucas[2] != temp)
    isPrime = false;
    }
    }
    return isPrime;
    }
    /// <summary>
    /// Determines whether a number is probably prime, using the Rabin-Miller's
    /// test. Before applying the test, the number is tested for divisibility
    /// by some primes
    ///
    /// Returns true if number is probably prime.
    /// </summary>
    /// <param name="confidence"></param>
    /// <returns></returns>
    public bool isProbablePrime(int confidence) {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    int max = (Prime.PrimeTable.Length/4);
    for(int p = 0; p < max; p++) {
    BigInteger divisor = (uint) Prime.PrimeTable[p];

    if(divisor >= thisVal) return true;

    BigInteger resultNum = thisVal % divisor;
    if(resultNum.IntValue() == 0) {
    return false;
    }
    }

    if(thisVal.RabinMillerTest(confidence)) {
    return true;
    } else {
    return false;
    }
    }
    /// <summary>
    /// Determines whether this BigInteger is probably prime using a
    /// combination of base 2 strong pseudoprime test and Lucas strong
    /// pseudoprime test.
    ///
    /// The sequence of the primality test is as follows,
    ///
    /// 1) Trial divisions are carried out using prime numbers below 2000.
    /// if any of the primes divides this BigInteger, then it is not prime.
    ///
    /// 2) Perform base 2 strong pseudoprime test. If this BigInteger is a
    /// base 2 strong pseudoprime, proceed on to the next step.
    ///
    /// 3) Perform strong Lucas pseudoprime test.
    ///
    /// Returns True if this BigInteger is both a base 2 strong pseudoprime
    /// and a strong Lucas pseudoprime.
    ///
    /// For a detailed discussion of this primality test, see [6].
    /// </summary>
    /// <returns></returns>
    public bool isProbablePrime() {
    BigInteger thisVal;
    if((this.data[maxLength-1] & 0x80000000) != 0) // negative
    thisVal = -this;
    else
    thisVal = this;

    if(thisVal.dataLength == 1) {
    // test small numbers
    if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
    return false;
    else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
    return true;
    }

    if((thisVal.data[0] & 0x1) == 0) // even numbers
    return false;

    // test for divisibility by primes < 2000
    for(int p = 0; p < Prime.PrimeTable.Length; p++) {
    BigInteger divisor = (uint) Prime.PrimeTable[p];

    if(divisor >= thisVal)
    break;

    BigInteger resultNum = thisVal % divisor;
    if(resultNum.IntValue() == 0) {
    //Console.WriteLine("Not prime! Divisible by {0}\n",
    // primesBelow2000[p]);
    return false;
    }
    }

    // Perform BASE 2 Rabin-Miller Test

    // calculate values of s and t
    BigInteger p_sub1 = thisVal - (new BigInteger(1));
    int s = 0;

    for(int index = 0; index < p_sub1.dataLength; index++) {
    uint mask = 0x01;

    for(int i = 0; i < 32; i++) {
    if((p_sub1.data[index] & mask) != 0) {
    index = p_sub1.dataLength; // to break the outer loop
    break;
    }
    mask <<= 1;
    s++;
    }
    }

    BigInteger t = p_sub1 >> s;

    int bits = thisVal.bitCount();
    BigInteger a = 2;

    // b = a^t mod p
    BigInteger b = a.modPow(t, thisVal);
    bool result = false;

    if(b.dataLength == 1 && b.data[0] == 1) // a^t mod p = 1
    result = true;

    for(int j = 0; result == false && j < s; j++) {
    if(b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
    result = true;
    break;
    }
    b = (b * b) % thisVal;
    }

    // if number is strong pseudoprime to base 2, then do a strong lucas test
    if(result)
    result = LucasStrongTestHelper(thisVal);

    return result;
    }
    /// <summary>
    /// Returns the lowest 4 bytes of the BigInteger as an int.
    /// </summary>
    /// <returns></returns>
    public int IntValue() {
    return (int)data[0];
    }
    /// <summary>
    /// Returns the lowest 4 bytes of the BigInteger as an uint.
    /// </summary>
    /// <returns></returns>
    public uint uIntValue() {
    return (uint)data[0];
    }
    /// <summary>
    /// Returns the lowest 8 bytes of the BigInteger as a long.
    /// </summary>
    /// <returns></returns>
    public long LongValue() {
    long val = 0;

    val = (long)data[0];
    try {
    // exception if maxLength = 1
    val |= (long
Devi accedere o registrarti per scrivere nel forum
4 risposte