PHP Barrett Modular Exponentiation Engine
author | Jim Wigginton terrafrost@php.net |
---|---|
package | Default |
__construct(integer|\phpseclib3\Math\BigInteger\Engines\numeric-string $x,integer $base = 10)
integer|\phpseclib3\Math\BigInteger\Engines\numeric-string
integer Base-10 number or base-$base number if $base set.
integer
__debugInfo(): array
Will be called, automatically, when print_r() or var_dump() are called
array
__sleep(): array
Will be called, automatically, when serialize() is called on a BigInteger object.
array
__toString(): string
string
__wakeup(): void
Will be called, automatically, when unserialize() is called on a BigInteger object.
abs(): \phpseclib3\Math\BigInteger\Engines\PHP
addHelper(array $x_value,boolean $x_negative,array $y_value,boolean $y_negative): array
array
boolean
array
boolean
array
array_repeat(integer $input,integer $multiplier): array
integer
integer
array
base256_lshift(string &$x,integer $shift): void
Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
string
integer
baseSquare(array $value): array
Squaring can be done faster than multiplying a number by itself can be. See HAC 14.2.4 / MPM 5.3 for more information.
array
array
bitwise_leftRotate(integer $shift): \phpseclib3\Math\BigInteger\Engines\Engine
Instead of the top x bits being dropped they're appended to the shifted bit string.
integer
\phpseclib3\Math\BigInteger\Engines\Engine
bitwise_leftShift(integer $shift): \phpseclib3\Math\BigInteger\Engines\PHP
Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
integer
\phpseclib3\Math\BigInteger\Engines\PHP
bitwise_not(): \phpseclib3\Math\BigInteger\Engines\Engine|string
bitwise_rightRotate(integer $shift): \phpseclib3\Math\BigInteger\Engines\Engine
Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
integer
\phpseclib3\Math\BigInteger\Engines\Engine
bitwise_rightShift(integer $shift): \phpseclib3\Math\BigInteger\Engines\PHP
Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
integer
\phpseclib3\Math\BigInteger\Engines\PHP
bitwise_small_split(integer $split): \phpseclib3\Math\BigInteger\Engines\list<int>
integer
\phpseclib3\Math\BigInteger\Engines\list
bitwise_split(integer $split): array<mixed,\phpseclib3\Math\BigInteger\Engines\Engine>
Splits BigInteger's into chunks of $split bits
integer
array<mixed,\phpseclib3\Math\BigInteger\Engines\Engine>
bitwiseAndHelper(\phpseclib3\Math\BigInteger\Engines\Engine $x): \phpseclib3\Math\BigInteger\Engines\Engine
bitwiseOrHelper(\phpseclib3\Math\BigInteger\Engines\Engine $x): \phpseclib3\Math\BigInteger\Engines\Engine
bitwiseXorHelper(\phpseclib3\Math\BigInteger\Engines\Engine $x): \phpseclib3\Math\BigInteger\Engines\Engine
compareHelper(array $x_value,boolean $x_negative,array $y_value,boolean $y_negative): integer
see | static::compare() |
---|
array
boolean
array
boolean
integer
convertToObj(array $arr): static
array
static
createRecurringModuloFunction(): callable
Sometimes it may be desirable to do repeated modulos with the same number outside of modular exponentiation
callable
divide_digit(array $dividend,integer $divisor): array
abc / x = a00 / x + b0 / x + c / x
array
integer
array
extendedGCDHelper(\phpseclib3\Math\BigInteger\Engines\Engine $n): \phpseclib3\Math\BigInteger\Engines\array{gcd:
\phpseclib3\Math\BigInteger\Engines\array{gcd:
Engine, x: Engine, y: Engine}
getLength(): integer
integer
getLengthInBytes(): integer
integer
getPrecision(): integer
Returns the precision if it exists, -1 if it doesn't
integer
initialize(integer $base)
see | \phpseclib3\Math\BigInteger\Engines\parent::__construct() |
---|---|
integer
int2bytes(integer $x): string
integer
string
isNegative(): boolean
boolean
isOdd(): boolean
boolean
isPrime(integer|boolean $t = false): boolean
Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads on a website instead of just one.
integer|boolean
boolean
isValidEngine(): boolean
boolean
jsonSerialize()
karatsuba(array $x_value,array $y_value): array
karatsubaSquare(array $value): array
lshift(integer $shift)
Shifts BigInteger's by $shift bits.
integer
make_odd()
If the current number is odd it'll be unchanged. If it's even, one will be added to it.
see | self::randomPrime() |
---|---|
maxHelper(array $nums): \phpseclib3\Math\BigInteger\Engines\Engine
minHelper(array $nums): \phpseclib3\Math\BigInteger\Engines\Engine
minMaxBits(integer $bits): \phpseclib3\Math\BigInteger\Engines\array{min:
integer
\phpseclib3\Math\BigInteger\Engines\array{min:
static, max: static}
modInverseHelper(\phpseclib3\Math\BigInteger\Engines\Engine $n): static|false
Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
{@internal See HAC 14.64 for more information.}
static|false
multiplyHelper(array $x_value,boolean $x_negative,array $y_value,boolean $y_negative): array
array
boolean
array
boolean
array
multiplyLower(array $x_value,boolean $x_negative,array $y_value,boolean $y_negative,integer $stop,string $class): array
If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
see | \phpseclib3\Math\BigInteger\Engines\PHP\Reductions\Barrett::regularBarrett() |
---|
array
boolean
array
boolean
integer
string
array
multiplyReduce(array $x,array $y,array $n,string $class): array
see | self::slidingWindow() |
---|
array
array
array
string
array
negate(): static
Given $k, returns -$k
static
normalize(\phpseclib3\Math\BigInteger\Engines\PHP $result): static
Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
static
pad(string $str): string
string
string
powHelper(\phpseclib3\Math\BigInteger\Engines\PHP $n): \phpseclib3\Math\BigInteger\Engines\PHP
powModHelper(\phpseclib3\Math\BigInteger\Engines\PHP $x,\phpseclib3\Math\BigInteger\Engines\PHP $e,\phpseclib3\Math\BigInteger\Engines\PHP $n,string $class): \phpseclib3\Math\BigInteger\Engines\PHP
The most naive approach to modular exponentiation has very unreasonable requirements, and and although the approach involving repeated squaring does vastly better, it, too, is impractical for our purposes. The reason being that division - by far the most complicated and time-consuming of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
Modular reductions resolve this issue. Although an individual modular reduction takes more time then an individual division, when performed in succession (with the same modulo), they're a lot faster.
The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because the product of two odd numbers is odd), but what about when RSA isn't used?
In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and the other, a power of two - and recombine them, later. This is the method that this modPow function uses. Montgomery Reduction with Even Modulus elaborates.
string
\phpseclib3\Math\BigInteger\Engines\PHP
powModInner(\phpseclib3\Math\BigInteger\Engines\PHP $e,\phpseclib3\Math\BigInteger\Engines\PHP $n): \phpseclib3\Math\BigInteger\Engines\PHP
powModOuter(\phpseclib3\Math\BigInteger\Engines\Engine $e,\phpseclib3\Math\BigInteger\Engines\Engine $n): static|false
static|false
prepareReduce(array $x,array $n,string $class): array
see | self::slidingWindow() |
---|
array
array
string
array
random(integer $size): \phpseclib3\Math\BigInteger\Engines\Engine
Bit length is equal to $size
integer
\phpseclib3\Math\BigInteger\Engines\Engine
randomPrime(integer $size): \phpseclib3\Math\BigInteger\Engines\Engine
Bit length is equal to $size
integer
\phpseclib3\Math\BigInteger\Engines\Engine
randomRangeHelper(\phpseclib3\Math\BigInteger\Engines\Engine $min,\phpseclib3\Math\BigInteger\Engines\Engine $max): \phpseclib3\Math\BigInteger\Engines\Engine
Returns a random number between $min and $max where $min and $max can be defined using one of the two methods:
BigInteger::randomRange($min, $max) BigInteger::randomRange($max, $min)
\phpseclib3\Math\BigInteger\Engines\Engine
randomRangePrimeInner(\phpseclib3\Math\BigInteger\Engines\Engine $x,\phpseclib3\Math\BigInteger\Engines\Engine $min,\phpseclib3\Math\BigInteger\Engines\Engine $max): static|false
static|false
randomRangePrimeOuter(\phpseclib3\Math\BigInteger\Engines\Engine $min,\phpseclib3\Math\BigInteger\Engines\Engine $max): static|false
static|false
reduce(array $n,array $m,\phpseclib3\Math\BigInteger\Engines\PHP\Reductions\class-string<PHP> $class): array
See HAC 14.3.3 / MPM 6.2.5 for more information. Modified slightly, so as not to require negative numbers (initially, this script didn't support negative numbers).
Employs "folding", as described at thesis-149.pdf#page=66. To quote from it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that usable on account of (1) its not using reasonable radix points as discussed in MPM 6.2.2 and (2) the fact that, even with reasonable radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that (x >> 1) + (x >> 1) != x / 2 + x / 2. If x is even, they're the same, but if x is odd, they're not. See the in-line comments for details.
array
array
\phpseclib3\Math\BigInteger\Engines\PHP\Reductions\class-string
array
regularBarrett(array $x,array $n,string $class): array
For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this is that this function does not fold the denominator into a smaller form.
array
array
string
array
regularMultiply(array $x_value,array $y_value): array
Modeled after 'multiply' in MutableBigInteger.java.
array
array
array
root(integer $n = 2): \phpseclib3\Math\BigInteger\Engines\Engine
rootHelper(integer $n): \phpseclib3\Math\BigInteger\Engines\Engine
rootInner(integer $n): \phpseclib3\Math\BigInteger\Engines\Engine
Returns the nth root of a positive biginteger, where n defaults to 2
{@internal This function is based off of this page and this stackoverflow question.}
integer
\phpseclib3\Math\BigInteger\Engines\Engine
rshift(integer $shift)
Shifts BigInteger's by $shift bits.
integer
safe_divide(integer $x,integer $y): integer
Even if int64 is being used the division operator will return a float64 value if the dividend is not evenly divisible by the divisor. Since a float64 doesn't have the precision of int64 this is a problem so, when int64 is being used, we'll guarantee that the dividend is divisible by first subtracting the remainder.
integer
integer
integer
scan1divide(\phpseclib3\Math\BigInteger\Engines\PHP $r): integer
ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
see | self::isPrime() |
---|
integer
setBitmask(integer $bits): static
see | \phpseclib3\Math\BigInteger\Engines\Engine::setPrecision() |
---|
integer
static
setModExpEngine(\phpseclib3\Math\BigInteger\Engines\class-string<Engine> $engine)
Throws an exception if the type is invalid
\phpseclib3\Math\BigInteger\Engines\class-string
setPrecision(integer $bits)
Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates.
integer
setupIsPrime(): integer
integer
slidingWindow(\phpseclib3\Math\BigInteger\Engines\Engine $x,\phpseclib3\Math\BigInteger\Engines\Engine $e,\phpseclib3\Math\BigInteger\Engines\Engine $n,\phpseclib3\Math\BigInteger\Engines\class-string<T> $class): \phpseclib3\Math\BigInteger\Engines\T
Based on HAC 14.85 / MPM 7.7. In a departure from those algorithims, however, this function performs a modular reduction after every multiplication and squaring operation. As such, this function has the same preconditions that the reductions being used do.
template | T of Engine |
---|
\phpseclib3\Math\BigInteger\Engines\class-string
\phpseclib3\Math\BigInteger\Engines\T
square(\phpseclib3\Math\BigInteger\Engines\list<static> $x): \phpseclib3\Math\BigInteger\Engines\list<static>
\phpseclib3\Math\BigInteger\Engines\list
\phpseclib3\Math\BigInteger\Engines\list
squareReduce(array $x,array $n,string $class): array
see | self::slidingWindow() |
---|
array
array
string
array
subtractHelper(array $x_value,boolean $x_negative,array $y_value,boolean $y_negative): array
array
boolean
array
boolean
array
testBit( $x): boolean
boolean
testPrimality(integer $t): boolean
Uses the Miller-Rabin primality test. See HAC 4.24 for more info.
integer
boolean
testSmallPrimes()
see | self::isPrime() |
---|---|
toBits(boolean $twos_compliment = false): string
Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.
boolean
string
toBytes(boolean $twos_compliment = false): string
boolean
string
toBytesHelper(): string
Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.
string
toHex(boolean $twos_compliment = false): string
boolean
string
toString(): string
string
trim(\phpseclib3\Math\BigInteger\Engines\list<static> $value): \phpseclib3\Math\BigInteger\Engines\list<static>
Removes leading zeros
\phpseclib3\Math\BigInteger\Engines\list
\phpseclib3\Math\BigInteger\Engines\list
VARIABLE
$cache[self::VARIABLE] tells us whether or not the cached data is still valid.
DATA
VALUE
SIGN
KARATSUBA_CUTOFF
At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
FAST_BITWISE
see | |
---|---|
ENGINE_DIR
see | |
---|---|
PRIMES
zero :\phpseclib3\Math\BigInteger\Engines\array<class-string<static>,
var | static> |
---|
\phpseclib3\Math\BigInteger\Engines\array,
one :\phpseclib3\Math\BigInteger\Engines\array<class-string<static>,
var | static> |
---|
\phpseclib3\Math\BigInteger\Engines\array,
two :\phpseclib3\Math\BigInteger\Engines\array<class-string<static>,
var | static> |
---|
\phpseclib3\Math\BigInteger\Engines\array,
modexpEngine :\phpseclib3\Math\BigInteger\Engines\array<class-string<static>,
var | class-string |
---|
\phpseclib3\Math\BigInteger\Engines\array,
isValidEngine :\phpseclib3\Math\BigInteger\Engines\array<class-string<static>,
var | bool> |
---|
\phpseclib3\Math\BigInteger\Engines\array,
value :\GMP|string|array|integer
var |
---|
\GMP|string|array|integer
is_negative :boolean
var |
---|
boolean
precision :integer
see | |
---|---|
var |
integer
bitmask :static|false
see | |
---|---|
var |
static|false
reduce :callable
var |
---|
callable
hex :string
see | |
---|---|
var |
string