abstract class Barrett extends Base (View source)

PHP Barrett Modular Exponentiation Engine

Constants

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
static protected string $modexpEngine Modular Exponentiation Engine from  BCMath
static protected bool $isValidEngine Engine Validity Flag from  BCMath
static protected BCMath $zero BigInteger(0) from  BCMath
static protected BCMath $one BigInteger(1) from  BCMath
static protected BCMath $two BigInteger(2) from  BCMath
static protected array $primes Primes > 2 and < 1000 from  BCMath

Methods

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

Default constructor

from  BCMath
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  BCMath
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  Engine
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
static bool
isValidEngine()

Test for engine validity

from  Base
initialize(int $base)

Initialize a BCMath BigInteger Engine instance

from  BCMath
string
toString()

Converts a BigInteger to a base-10 number.

from  BCMath
string
toBytes(bool $twos_compliment = false)

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

from  BCMath
BCMath
add(BCMath $y)

Adds two BigIntegers.

from  BCMath
BCMath
subtract(BCMath $y)

Subtracts two BigIntegers.

from  BCMath
BCMath
multiply(BCMath $x)

Multiplies two BigIntegers.

from  BCMath
BCMath
divide(BCMath $y)

Divides two BigIntegers.

from  BCMath
false|BCMath
modInverse(BCMath $n)

Calculates modular inverses.

from  BCMath
BCMath
extendedGCD(BCMath $n)

Calculates the greatest common divisor and Bezout's identity.

from  BCMath
BCMath
gcd(BCMath $n)

Calculates the greatest common divisor

from  BCMath
abs()

Absolute value.

from  BCMath
BCMath
bitwise_and(BCMath $x)

Logical And

from  BCMath
BCMath
bitwise_or(BCMath $x)

Logical Or

from  BCMath
BCMath
bitwise_xor(BCMath $x)

Logical Exclusive Or

from  BCMath
bitwise_rightShift(int $shift)

Logical Right Shift

from  BCMath
bitwise_leftShift(int $shift)

Logical Left Shift

from  BCMath
int
compare(BCMath $y)

Compares two numbers.

from  BCMath
bool
equals(BCMath $x)

Tests the equality of two numbers.

from  BCMath
BCMath
modPow(BCMath $e, BCMath $n)

Performs modular exponentiation.

from  BCMath
BCMath
powMod(BCMath $e, BCMath $n)

Performs modular exponentiation.

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

Performs modular exponentiation.

from  BCMath
BCMath
normalize(BCMath $result)

Normalize

from  BCMath
static false|BCMath
randomRangePrime(BCMath $min, BCMath $max)

Generate a random prime number between a range

from  BCMath
static BCMath
randomRange(BCMath $min, BCMath $max)

Generate a random number between a range

from  BCMath
make_odd()

Make the current number odd

from  BCMath
testSmallPrimes()

Test the number against small primes.

from  BCMath
static int
scan1divide(BCMath $r)

Scan for 1 and right shift by that amount

from  BCMath
BCMath
pow(BCMath $n)

Performs exponentiation.

from  BCMath
static BCMath
min(BCMath ...$nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

from  BCMath
static BCMath
max(BCMath ...$nums)

Return the maximum BigInteger between an arbitrary number of BigIntegers.

from  BCMath
bool
between(BCMath $min, BCMath $max)

Tests BigInteger to see if it is between two integers, inclusive

from  BCMath
bool
isOdd()

Is Odd?

from  BCMath
bool
testBit($x)

Tests if a bit is set

from  BCMath
bool
isNegative()

Is Negative?

from  BCMath
BCMath
negate()

Negate

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

Performs modular exponentiation.

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

Modular reduction preparation

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

Modular multiply

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

Modular square

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

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

static bool isValidEngine()

Test for engine validity

Return Value

bool

protected initialize(int $base)

Initialize a BCMath BigInteger Engine instance

Parameters

int $base

See also

\parent::__construct()

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

BCMath add(BCMath $y)

Adds two BigIntegers.

Parameters

BCMath $y

Return Value

BCMath

BCMath subtract(BCMath $y)

Subtracts two BigIntegers.

Parameters

BCMath $y

Return Value

BCMath

BCMath multiply(BCMath $x)

Multiplies two BigIntegers.

Parameters

BCMath $x

Return Value

BCMath

BCMath divide(BCMath $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

BCMath $y

Return Value

BCMath

false|BCMath modInverse(BCMath $n)

Calculates modular inverses.

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

Parameters

BCMath $n

Return Value

false|BCMath

BCMath extendedGCD(BCMath $n)

Calculates the greatest common divisor and Bezout's identity.

Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 693x + 609y == 21. In point of fact, there are actually an infinite number of x and y combinations and which combination is returned is dependent upon which mode is in use. See {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.

Parameters

BCMath $n

Return Value

BCMath

BCMath gcd(BCMath $n)

Calculates the greatest common divisor

Say you have 693 and 609. The GCD is 21.

Parameters

BCMath $n

Return Value

BCMath

BCMath abs()

Absolute value.

Return Value

BCMath

BCMath bitwise_and(BCMath $x)

Logical And

Parameters

BCMath $x

Return Value

BCMath

BCMath bitwise_or(BCMath $x)

Logical Or

Parameters

BCMath $x

Return Value

BCMath

BCMath bitwise_xor(BCMath $x)

Logical Exclusive Or

Parameters

BCMath $x

Return Value

BCMath

BCMath bitwise_rightShift(int $shift)

Logical Right Shift

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

Parameters

int $shift

Return Value

BCMath

BCMath bitwise_leftShift(int $shift)

Logical Left Shift

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

Parameters

int $shift

Return Value

BCMath

int compare(BCMath $y)

Compares two numbers.

Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is demonstrated thusly:

$x > $y: $x->compare($y) > 0 $x < $y: $x->compare($y) < 0 $x == $y: $x->compare($y) == 0

Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).

{@internal Could return $this->subtract($x), but that's not as fast as what we do do.}

Parameters

BCMath $y

Return Value

int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.

See also

\self::equals()

bool equals(BCMath $x)

Tests the equality of two numbers.

If you need to see if one number is greater than or less than another number, use BigInteger::compare()

Parameters

BCMath $x

Return Value

bool

BCMath modPow(BCMath $e, BCMath $n)

Performs modular exponentiation.

Parameters

BCMath $e
BCMath $n

Return Value

BCMath

BCMath powMod(BCMath $e, BCMath $n)

Performs modular exponentiation.

Alias for modPow().

Parameters

BCMath $e
BCMath $n

Return Value

BCMath

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

Performs modular exponentiation.

Parameters

BCMath $e
BCMath $n

Return Value

BCMath

protected BCMath normalize(BCMath $result)

Normalize

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

Parameters

BCMath $result

Return Value

BCMath

static false|BCMath randomRangePrime(BCMath $min, BCMath $max)

Generate a random prime number between a range

If there's not a prime within the given range, false will be returned.

Parameters

BCMath $min
BCMath $max

Return Value

false|BCMath

static BCMath randomRange(BCMath $min, BCMath $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

BCMath $min
BCMath $max

Return Value

BCMath

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(BCMath $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

BCMath $r

Return Value

int

See also

\self::isPrime()

BCMath pow(BCMath $n)

Performs exponentiation.

Parameters

BCMath $n

Return Value

BCMath

static BCMath min(BCMath ...$nums)

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Parameters

BCMath ...$nums

Return Value

BCMath

static BCMath max(BCMath ...$nums)

Return the maximum BigInteger between an arbitrary number of BigIntegers.

Parameters

BCMath ...$nums

Return Value

BCMath

bool between(BCMath $min, BCMath $max)

Tests BigInteger to see if it is between two integers, inclusive

Parameters

BCMath $min
BCMath $max

Return Value

bool

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

BCMath negate()

Negate

Given $k, returns -$k

Return Value

BCMath

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

Performs modular exponentiation.

Parameters

BCMath $x
BCMath $e
BCMath $n
string $class

Return Value

BCMath

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

Modular reduction preparation

Parameters

string $x
string $n
string $class

Return Value

string

See also

\self::slidingWindow()

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

Modular multiply

Parameters

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

Return Value

string

See also

\self::slidingWindow()

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

Modular square

Parameters

string $x
string $n
string $class

Return Value

string

See also

\self::slidingWindow()

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

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

string $n
string $m

Return Value

array|string