abstract class Barrett extends Base (View source)

PHP Barrett Modular Exponentiation Engine

Constants

VALUE

$result[self::VALUE] contains the value.

SIGN

$result[self::SIGN] contains the sign.

KARATSUBA_CUTOFF

Karatsuba Cutoff

At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?

FAST_BITWISE

Can Bitwise operations be done fast?

ENGINE_DIR

Engine Directory

VARIABLE

Cache constants

$cache[self::VARIABLE] tells us whether or not the cached data is still valid.

DATA

$cache[self::DATA] contains the cached data.

Properties

protected mixed $value Holds the BigInteger's value from  Engine
protected bool $is_negative Holds the BigInteger's sign from  Engine
protected $precision Precision from  Engine
protected $bitmask Precision Bitmask from  Engine
protected callable $reduce Recurring Modulo Function from  Engine

Methods

__construct(mixed $x = 0, int $base = 10)

Default constructor

from  PHP
static 
setModExpEngine(string $engine)

Sets engine type.

from  Engine
string
toBytesHelper()

Converts a BigInteger to a byte string (eg. base-256).

from  Engine
string
toHex(bool $twos_compliment = false)

Converts a BigInteger to a hex string (eg. base-16).

from  Engine
string
toBits(bool $twos_compliment = false)

Converts a BigInteger to a bit string (eg. base-2).

from  Engine
Engine|false
modInverseHelper(Engine $n)

Calculates modular inverses.

from  Engine
string
serialize()

Serialize

from  Engine
unserialize(string $serialized)

Serialize

from  Engine
string
__toString()

Converts a BigInteger to a base-10 number.

from  Engine
__debugInfo()

__debugInfo() magic method

from  Engine
setPrecision(int $bits)

Set Precision

from  Engine
int
getPrecision()

Get Precision

from  Engine
static Engine
setBitmask(int $bits)

Set Bitmask

from  Engine
Engine|string
bitwise_not()

Logical Not

from  Engine
static string
base256_lshift(string $x, int $shift)

Logical Left Shift

from  Engine
bitwise_leftRotate(int $shift)

Logical Left Rotate

from  Engine
bitwise_rightRotate(int $shift)

Logical Right Rotate

from  Engine
static Engine[]
minMaxBits(int $bits)

Returns the smallest and largest n-bit number

from  Engine
int
getLength()

Return the size of a BigInteger in bits

from  Engine
int
getLengthInBytes()

Return the size of a BigInteger in bytes

from  Engine
bool|Engine
powModOuter(Engine $e, Engine $n)

Performs some pre-processing for powMod

from  Engine
static Engine
slidingWindow(Engine $x, Engine $e, Engine $n, string $class)

Sliding Window k-ary Modular Exponentiation

from  Engine
static Engine
random(int $size)

Generates a random number of a certain size

from  Engine
static Engine
randomPrime(int $size)

Generates a random prime number of a certain size

from  Engine
static bool|Engine
randomRangePrimeOuter(Engine $min, Engine $max)

Performs some pre-processing for randomRangePrime

from  Engine
static Engine
randomRangeHelper(Engine $min, Engine $max)

Generate a random number between a range

from  Engine
static bool|Engine
randomRangePrimeInner(Engine $x, Engine $min, Engine $max)

Performs some post-processing for randomRangePrime

from  Engine
int
setupIsPrime()

Sets the $t parameter for primality testing

from  Engine
bool
testPrimality(int $t)

Tests Primality

from  Engine
bool
isPrime(int|bool $t = false)

Checks a numer to see if it's prime

from  Engine
rootHelper(int $n)

Performs a few preliminary checks on root

from  Engine
rootInner(int $n)

Calculates the nth root of a biginteger.

from  Engine
Engine
root(int $n = 2)

Calculates the nth root of a biginteger.

from  Engine
static Engine
minHelper(array $nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

from  Engine
static Engine
maxHelper(array $nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

from  Engine
callable
createRecurringModuloFunction()

Create Recurring Modulo Function

from  Engine
Engine
extendedGCDHelper(Engine $n, Engine $stop = null)

Calculates the greatest common divisor and Bezout's identity.

from  Engine
Engine[]
bitwise_split(int $split)

Bitwise Split

from  PHP
Engine
bitwiseAndHelper(Engine $x)

Logical And

from  Engine
Engine
bitwiseOrHelper(Engine $x)

Logical Or

from  Engine
Engine
bitwiseXorHelper(Engine $x)

Logical Exclusive Or

from  Engine
initialize(int $base)

Initialize a PHP BigInteger Engine instance

from  PHP
string
pad(string $str)

Pads strings so that unpack may be used on them

from  PHP
string
toString()

Converts a BigInteger to a base-10 number.

from  PHP
string
toBytes(bool $twos_compliment = false)

Converts a BigInteger to a byte string (eg. base-256).

from  PHP
static array
addHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs addition.

from  PHP
static array
subtractHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs subtraction.

from  PHP
static array
multiplyHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs multiplication.

from  PHP
static array
regularMultiply(array $x_value, array $y_value)

Performs long multiplication on two BigIntegers

from  PHP
array
divideHelper(PHP $y)

Divides two BigIntegers.

from  PHP
convertToObj(array $arr)

No description

from  PHP
PHP
normalize(PHP $result)

Normalize

from  PHP
static 
compareHelper(array $x_value, $x_negative, array $y_value, $y_negative)

No description

from  PHP
PHP
abs()

Absolute value.

from  PHP
static PHP
trim(array $value)

Trim

from  PHP
PHP
bitwise_rightShift(int $shift)

Logical Right Shift

from  PHP
PHP
bitwise_leftShift(int $shift)

Logical Left Shift

from  PHP
static array
array_repeat(int $input, int $multiplier)

Array Repeat

from  PHP
lshift(int $shift)

Logical Left Shift

from  PHP
rshift(int $shift)

Logical Right Shift

from  PHP
PHP
powModInner(PHP $e, PHP $n)

Performs modular exponentiation.

from  PHP
static array
square(array $x)

Performs squaring

from  PHP
static array
baseSquare(array $value)

Performs traditional squaring on two BigIntegers

from  PHP
static array
karatsubaSquare(array $value)

Performs Karatsuba "squaring" on two BigIntegers

from  PHP
make_odd()

Make the current number odd

from  PHP
testSmallPrimes()

Test the number against small primes.

from  PHP
static int
scan1divide(PHP $r)

Scan for 1 and right shift by that amount

from  PHP
PHP
powHelper(PHP $n)

Performs exponentiation.

from  PHP
bool
isOdd()

Is Odd?

from  PHP
bool
testBit($x)

Tests if a bit is set

from  PHP
bool
isNegative()

Is Negative?

from  PHP
BigInteger
negate()

Negate

from  PHP
static bool
isValidEngine()

Test for engine validity

from  Base
static PHP
powModHelper(PHP $x, PHP $e, PHP $n, string $class)

Performs modular exponentiation.

from  Base
static array
prepareReduce(array $x, array $n, string $class)

Modular reduction preparation

from  Base
static array
multiplyReduce(array $x, array $y, array $n, string $class)

Modular multiply

from  Base
static array
squareReduce(array $x, array $n, string $class)

Modular square

from  Base
static array
reduce(array $n, array $m, string $class)

Barrett Modular Reduction

Details

__construct(mixed $x = 0, int $base = 10)

Default constructor

Parameters

mixed $x integer Base-10 number or base-$base number if $base set.
int $base

See also

\parent::__construct()

static setModExpEngine(string $engine)

Sets engine type.

Throws an exception if the type is invalid

Parameters

string $engine

protected string toBytesHelper()

Converts a BigInteger to a byte string (eg. base-256).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Return Value

string

string toHex(bool $twos_compliment = false)

Converts a BigInteger to a hex string (eg. base-16).

Parameters

bool $twos_compliment

Return Value

string

string toBits(bool $twos_compliment = false)

Converts a BigInteger to a bit string (eg. base-2).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Parameters

bool $twos_compliment

Return Value

string

protected Engine|false modInverseHelper(Engine $n)

Calculates modular inverses.

Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.

{@internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.}

Parameters

Engine $n

Return Value

Engine|false

string serialize()

Serialize

Will be called, automatically, when serialize() is called on a BigInteger object.

Return Value

string

unserialize(string $serialized)

Serialize

Will be called, automatically, when unserialize() is called on a BigInteger object.

Parameters

string $serialized

string __toString()

Converts a BigInteger to a base-10 number.

Return Value

string

__debugInfo()

__debugInfo() magic method

Will be called, automatically, when print_r() or var_dump() are called

setPrecision(int $bits)

Set Precision

Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates.

Parameters

int $bits

int getPrecision()

Get Precision

Returns the precision if it exists, -1 if it doesn't

Return Value

int

static protected Engine setBitmask(int $bits)

Set Bitmask

Parameters

int $bits

Return Value

Engine

See also

\self::setPrecision()

Engine|string bitwise_not()

Logical Not

Return Value

Engine|string

static protected string base256_lshift(string $x, int $shift)

Logical Left Shift

Shifts binary strings $shift bits, essentially multiplying by 2**$shift.

Parameters

string $x
int $shift

Return Value

string

Engine bitwise_leftRotate(int $shift)

Logical Left Rotate

Instead of the top x bits being dropped they're appended to the shifted bit string.

Parameters

int $shift

Return Value

Engine

Engine bitwise_rightRotate(int $shift)

Logical Right Rotate

Instead of the bottom x bits being dropped they're prepended to the shifted bit string.

Parameters

int $shift

Return Value

Engine

static Engine[] minMaxBits(int $bits)

Returns the smallest and largest n-bit number

Parameters

int $bits

Return Value

Engine[]

int getLength()

Return the size of a BigInteger in bits

Return Value

int

int getLengthInBytes()

Return the size of a BigInteger in bytes

Return Value

int

protected bool|Engine powModOuter(Engine $e, Engine $n)

Performs some pre-processing for powMod

Parameters

Engine $e
Engine $n

Return Value

bool|Engine

static protected Engine slidingWindow(Engine $x, Engine $e, Engine $n, string $class)

Sliding Window k-ary Modular Exponentiation

Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 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.

Parameters

Engine $x
Engine $e
Engine $n
string $class

Return Value

Engine

static Engine random(int $size)

Generates a random number of a certain size

Bit length is equal to $size

Parameters

int $size

Return Value

Engine

static Engine randomPrime(int $size)

Generates a random prime number of a certain size

Bit length is equal to $size

Parameters

int $size

Return Value

Engine

static protected bool|Engine randomRangePrimeOuter(Engine $min, Engine $max)

Performs some pre-processing for randomRangePrime

Parameters

Engine $min
Engine $max

Return Value

bool|Engine

static protected Engine randomRangeHelper(Engine $min, Engine $max)

Generate a random number between a range

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)

Parameters

Engine $min
Engine $max

Return Value

Engine

static protected bool|Engine randomRangePrimeInner(Engine $x, Engine $min, Engine $max)

Performs some post-processing for randomRangePrime

Parameters

Engine $x
Engine $min
Engine $max

Return Value

bool|Engine

protected int setupIsPrime()

Sets the $t parameter for primality testing

Return Value

int

protected bool testPrimality(int $t)

Tests Primality

Uses the {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24} for more info.

Parameters

int $t

Return Value

bool

bool isPrime(int|bool $t = false)

Checks a numer to see if it's prime

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.

Parameters

int|bool $t

Return Value

bool

protected Engine rootHelper(int $n)

Performs a few preliminary checks on root

Parameters

int $n

Return Value

Engine

protected Engine rootInner(int $n)

Calculates the nth root of a biginteger.

Returns the nth root of a positive biginteger, where n defaults to 2

{@internal This function is based off of {@link http://mathforum.org/library/drmath/view/52605.html this page} and {@link http://stackoverflow.com/questions/11242920/calculating-nth-root-with-bcmath-in-php this stackoverflow question}.}

Parameters

int $n

Return Value

Engine

Engine root(int $n = 2)

Calculates the nth root of a biginteger.

Parameters

int $n

Return Value

Engine

static protected Engine minHelper(array $nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Parameters

array $nums

Return Value

Engine

static protected Engine maxHelper(array $nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Parameters

array $nums

Return Value

Engine

callable createRecurringModuloFunction()

Create Recurring Modulo Function

Sometimes it may be desirable to do repeated modulos with the same number outside of modular exponentiation

Return Value

callable

protected Engine extendedGCDHelper(Engine $n, Engine $stop = null)

Calculates the greatest common divisor and Bezout's identity.

Parameters

Engine $n
Engine $stop (optional)

Return Value

Engine

Engine[] bitwise_split(int $split)

Bitwise Split

Splits BigInteger's into chunks of $split bits

Parameters

int $split

Return Value

Engine[]

protected Engine bitwiseAndHelper(Engine $x)

Logical And

Parameters

Engine $x

Return Value

Engine

protected Engine bitwiseOrHelper(Engine $x)

Logical Or

Parameters

Engine $x

Return Value

Engine

protected Engine bitwiseXorHelper(Engine $x)

Logical Exclusive Or

Parameters

Engine $x

Return Value

Engine

protected initialize(int $base)

Initialize a PHP BigInteger Engine instance

Parameters

int $base

See also

\parent::__construct()

protected string pad(string $str)

Pads strings so that unpack may be used on them

Parameters

string $str

Return Value

string

string toString()

Converts a BigInteger to a base-10 number.

Return Value

string

string toBytes(bool $twos_compliment = false)

Converts a BigInteger to a byte string (eg. base-256).

Parameters

bool $twos_compliment

Return Value

string

static protected array addHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs addition.

Parameters

array $x_value
bool $x_negative
array $y_value
bool $y_negative

Return Value

array

static array subtractHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs subtraction.

Parameters

array $x_value
bool $x_negative
array $y_value
bool $y_negative

Return Value

array

static protected array multiplyHelper(array $x_value, bool $x_negative, array $y_value, bool $y_negative)

Performs multiplication.

Parameters

array $x_value
bool $x_negative
array $y_value
bool $y_negative

Return Value

array

static protected array regularMultiply(array $x_value, array $y_value)

Performs long multiplication on two BigIntegers

Modeled after 'multiply' in MutableBigInteger.java.

Parameters

array $x_value
array $y_value

Return Value

array

protected array divideHelper(PHP $y)

Divides two BigIntegers.

Returns an array whose first element contains the quotient and whose second element contains the "common residue". If the remainder would be positive, the "common residue" and the remainder are the same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder and the divisor (basically, the "common residue" is the first positive modulo).

Parameters

PHP $y

Return Value

array

protected convertToObj(array $arr)

Parameters

array $arr

protected PHP normalize(PHP $result)

Normalize

Removes leading zeros and truncates (if necessary) to maintain the appropriate precision

Parameters

PHP $result

Return Value

PHP

static protected compareHelper(array $x_value, $x_negative, array $y_value, $y_negative)

Parameters

array $x_value
$x_negative
array $y_value
$y_negative

PHP abs()

Absolute value.

Return Value

PHP

static protected PHP trim(array $value)

Trim

Removes leading zeros

Parameters

array $value

Return Value

PHP

PHP bitwise_rightShift(int $shift)

Logical Right Shift

Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.

Parameters

int $shift

Return Value

PHP

PHP bitwise_leftShift(int $shift)

Logical Left Shift

Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.

Parameters

int $shift

Return Value

PHP

static protected array array_repeat(int $input, int $multiplier)

Array Repeat

Parameters

int $input
int $multiplier

Return Value

array

protected lshift(int $shift)

Logical Left Shift

Shifts BigInteger's by $shift bits.

Parameters

int $shift

protected rshift(int $shift)

Logical Right Shift

Shifts BigInteger's by $shift bits.

Parameters

int $shift

protected PHP powModInner(PHP $e, PHP $n)

Performs modular exponentiation.

Parameters

PHP $e
PHP $n

Return Value

PHP

static protected array square(array $x)

Performs squaring

Parameters

array $x

Return Value

array

static protected array baseSquare(array $value)

Performs traditional squaring on two BigIntegers

Squaring can be done faster than multiplying a number by itself can be. See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.

Parameters

array $value

Return Value

array

static protected array karatsubaSquare(array $value)

Performs Karatsuba "squaring" on two BigIntegers

See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.

Parameters

array $value

Return Value

array

protected make_odd()

Make the current number odd

If the current number is odd it'll be unchanged. If it's even, one will be added to it.

See also

\self::randomPrime()

protected testSmallPrimes()

Test the number against small primes.

See also

\self::isPrime()

static int scan1divide(PHP $r)

Scan for 1 and right shift by that amount

ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));

Parameters

PHP $r

Return Value

int

See also

\self::isPrime()

protected PHP powHelper(PHP $n)

Performs exponentiation.

Parameters

PHP $n

Return Value

PHP

bool isOdd()

Is Odd?

Return Value

bool

bool testBit($x)

Tests if a bit is set

Parameters

$x

Return Value

bool

bool isNegative()

Is Negative?

Return Value

bool

BigInteger negate()

Negate

Given $k, returns -$k

Return Value

BigInteger

static bool isValidEngine()

Test for engine validity

Return Value

bool

static protected PHP powModHelper(PHP $x, PHP $e, PHP $n, string $class)

Performs modular exponentiation.

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. {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.

Parameters

PHP $x
PHP $e
PHP $n
string $class

Return Value

PHP

static protected array prepareReduce(array $x, array $n, string $class)

Modular reduction preparation

Parameters

array $x
array $n
string $class

Return Value

array

See also

\self::slidingWindow()

static protected array multiplyReduce(array $x, array $y, array $n, string $class)

Modular multiply

Parameters

array $x
array $y
array $n
string $class

Return Value

array

See also

\self::slidingWindow()

static protected array squareReduce(array $x, array $n, string $class)

Modular square

Parameters

array $x
array $n
string $class

Return Value

array

See also

\self::slidingWindow()

static protected array reduce(array $n, array $m, string $class)

Barrett Modular Reduction

See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 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 {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 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 {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 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.

Parameters

array $n
array $m
string $class

Return Value

array