src/NeinMath/IntegerFunctions.cs
/// <summary>
/// Performs modulus division on an Integer raised to the power of
/// another Integer.
/// </summary>
/// <param name="value">
/// The Integer to raise to the exponent power.
/// </param>
/// <param name="power">The exponent to raise the Integer by.</param>
/// <param name="modulus">The Integer by which to divide.</param>
/// <returns>
/// The result of raising the Integer to the exponent power.
/// </returns>
Performs modulus division on an Integer raised to the power of
another Integer.
Performs modulus division on an Integer raised to the power of another Integer .
public static Integer ModPow(this Integer value, Integer power,
                                     Integer modulus)
        {
            if (power < 0)
                throw new ArgumentOutOfRangeException(nameof(power));
            if (modulus < 1)
                throw new ArgumentOutOfRangeException(nameof(modulus));
            if (power == 0)
                return modulus == 1 ? 0 : 1;
            var barrett = Barrett.Begin(modulus);
            var v = new Integer[256];
            v[0] = 1;
            v[1] = barrett.Reduce(value);
            v[2] = barrett.Reduce(v[1] * v[1]);
            for (var j = 4; j < v.Length; j *= 2)
                v[j] = barrett.Reduce(v[j / 2] * v[j / 2]);
            for (var i = 3; i < v.Length; i += 2)
            {
                v[i] = barrett.Reduce(v[i - 1] * v[1]);
                for (var j = i * 2; j < v.Length; j *= 2)
                    v[j] = barrett.Reduce(v[j / 2] * v[j / 2]);
            }
            var p = power.ToByteArray();
            Integer result = v[p[p.Length - 1]];
            for (var i = p.Length - 2; i >= 0; i--)
            {
                for (var j = 0; j < 8; j++)
                    result = barrett.Reduce(result * result);
                result = barrett.Reduce(result * v[p[i]]);
            }
            return result;
        }
public static Integer ModPow ( this Integer value , Integer power , Integer modulus ) { if ( power < 0 ) throw new ArgumentOutOfRangeException ( nameof ( power ) ) ; if ( modulus < 1 ) throw new ArgumentOutOfRangeException ( nameof ( modulus ) ) ; if ( power == 0 ) return modulus == 1 ? 0 : 1 ; var barrett = Barrett . Begin ( modulus ) ; var v = new Integer [ 256 ] ; v [ 0 ] = 1 ; v [ 1 ] = barrett . Reduce ( value ) ; v [ 2 ] = barrett . Reduce ( v [ 1 ] * v [ 1 ] ) ; for ( var j = 4 ; j < v . Length ; j *= 2 ) v [ j ] = barrett . Reduce ( v [ j / 2 ] * v [ j / 2 ] ) ; for ( var i = 3 ; i < v . Length ; i += 2 ) { v [ i ] = barrett . Reduce ( v [ i - 1 ] * v [ 1 ] ) ; for ( var j = i * 2 ; j < v . Length ; j *= 2 ) v [ j ] = barrett . Reduce ( v [ j / 2 ] * v [ j / 2 ] ) ; } var p = power . ToByteArray ( ) ; Integer result = v [ p [ p . Length - 1 ] ] ; for ( var i = p . Length - 2 ; i >= 0 ; i -- ) { for ( var j = 0 ; j < 8 ; j ++ ) result = barrett . Reduce ( result * result ) ; result = barrett . Reduce ( result * v [ p [ i ] ] ) ; } return result ; }
Performs modulus division on an Integer raised to the power of
another Integer.
Performs modulus division on an Integer raised to the power of another Integer .
The result of raising the Integer to the exponent power.
The result of raising the Integer to the exponent power .
Integer
this
power
Integer
The exponent to raise the Integer by.
The exponent to raise the Integer by .
modulus
Integer
The Integer by which to divide.
The Integer by which to divide .
value
The Integer to raise to the exponent power.
The Integer to raise to the exponent power .