Documentation

DefaultEngine extends GMP
in package

AbstractYes

GMP Modular Exponentiation Engine

Tags
author

Jim Wigginton terrafrost@php.net

access

public

Table of Contents

Constants

ENGINE_DIR  = 'GMP'
Engine Directory
FAST_BITWISE  = true
Can Bitwise operations be done fast?

Properties

$bitmask  : mixed
Precision Bitmask
$is_negative  : bool
Holds the BigInteger's sign
$isValidEngine  : bool
Engine Validity Flag
$modexpEngine  : string
Modular Exponentiation Engine
$one  : GMP
BigInteger(1)
$precision  : mixed
Precision
$primes  : mixed
Primes > 2 and < 1000
$reduce  : callable
Recurring Modulo Function
$two  : GMP
BigInteger(2)
$value  : mixed
Holds the BigInteger's value
$zero  : GMP
BigInteger(0)

Methods

__construct()  : GMP
Default constructor
__debugInfo()  : mixed
__debugInfo() magic method
__toString()  : string
Converts a BigInteger to a base-10 number.
abs()  : GMP
Absolute value.
add()  : GMP
Adds two BigIntegers.
between()  : bool
Tests BigInteger to see if it is between two integers, inclusive
bitwise_and()  : GMP
Logical And
bitwise_leftRotate()  : Engine
Logical Left Rotate
bitwise_leftShift()  : GMP
Logical Left Shift
bitwise_not()  : Engine|string
Logical Not
bitwise_or()  : GMP
Logical Or
bitwise_rightRotate()  : Engine
Logical Right Rotate
bitwise_rightShift()  : GMP
Logical Right Shift
bitwise_split()  : array<string|int, Engine>
Bitwise Split
bitwise_xor()  : GMP
Logical Exclusive Or
compare()  : int
Compares two numbers.
createRecurringModuloFunction()  : callable
Create Recurring Modulo Function
divide()  : GMP
Divides two BigIntegers.
equals()  : bool
Tests the equality of two numbers.
extendedGCD()  : array<string|int, GMP>
Calculates the greatest common divisor and Bezout's identity.
gcd()  : GMP
Calculates the greatest common divisor
getLength()  : int
Return the size of a BigInteger in bits
getLengthInBytes()  : int
Return the size of a BigInteger in bytes
getPrecision()  : int
Get Precision
isNegative()  : bool
Is Negative?
isOdd()  : bool
Is Odd?
isPrime()  : bool
Checks a numer to see if it's prime
isValidEngine()  : bool
Test for engine validity
max()  : GMP
Return the maximum BigInteger between an arbitrary number of BigIntegers.
min()  : GMP
Return the minimum BigInteger between an arbitrary number of BigIntegers.
minMaxBits()  : array<string|int, Engine>
Returns the smallest and largest n-bit number
modInverse()  : false|GMP
Calculates modular inverses.
modPow()  : GMP
Performs modular exponentiation.
multiply()  : GMP
Multiplies two BigIntegers.
negate()  : GMP
Negate
pow()  : GMP
Performs exponentiation.
powMod()  : GMP
Performs modular exponentiation.
random()  : Engine
Generates a random number of a certain size
randomPrime()  : Engine
Generates a random prime number of a certain size
randomRange()  : GMP
Generate a random number between a range
randomRangePrime()  : false|GMP
Generate a random prime number between a range
root()  : Engine
Calculates the nth root of a biginteger.
scan1divide()  : int
Scan for 1 and right shift by that amount
serialize()  : string
Serialize
setModExpEngine()  : mixed
Sets engine type.
setPrecision()  : mixed
Set Precision
subtract()  : GMP
Subtracts two BigIntegers.
testBit()  : bool
Tests if a bit is set
toBits()  : string
Converts a BigInteger to a bit string (eg. base-2).
toBytes()  : string
Converts a BigInteger to a byte string (eg. base-256).
toHex()  : string
Converts a BigInteger to a hex string (eg. base-16).
toString()  : string
Converts a BigInteger to a base-10 number.
unserialize()  : mixed
Serialize
base256_lshift()  : string
Logical Left Shift
bitwiseAndHelper()  : Engine
Logical And
bitwiseOrHelper()  : Engine
Logical Or
bitwiseXorHelper()  : Engine
Logical Exclusive Or
extendedGCDHelper()  : Engine
Calculates the greatest common divisor and Bezout's identity.
initialize()  : mixed
Initialize a GMP BigInteger Engine instance
make_odd()  : mixed
Make the current number odd
maxHelper()  : Engine
Return the minimum BigInteger between an arbitrary number of BigIntegers.
minHelper()  : Engine
Return the minimum BigInteger between an arbitrary number of BigIntegers.
modInverseHelper()  : Engine|false
Calculates modular inverses.
normalize()  : GMP
Normalize
powModHelper()  : GMP
Performs modular exponentiation.
powModInner()  : GMP
Performs modular exponentiation.
powModOuter()  : bool|Engine
Performs some pre-processing for powMod
randomRangeHelper()  : Engine
Generate a random number between a range
randomRangePrimeInner()  : GMP
Performs some post-processing for randomRangePrime
randomRangePrimeOuter()  : bool|Engine
Performs some pre-processing for randomRangePrime
rootHelper()  : Engine
Performs a few preliminary checks on root
rootInner()  : GMP
Calculates the nth root of a biginteger.
setBitmask()  : Engine
Set Bitmask
setupIsPrime()  : int
Sets the $t parameter for primality testing
slidingWindow()  : Engine
Sliding Window k-ary Modular Exponentiation
testPrimality()  : bool
Tests Primality
toBytesHelper()  : string
Converts a BigInteger to a byte string (eg. base-256).

Constants

ENGINE_DIR

Engine Directory

public mixed ENGINE_DIR = 'GMP'
Tags
see
parent::setModExpEngine
access

protected

FAST_BITWISE

Can Bitwise operations be done fast?

public mixed FAST_BITWISE = true
Tags
see
parent::bitwise_leftRotate()
see
parent::bitwise_rightRotate()
access

protected

Properties

$bitmask

Precision Bitmask

protected mixed $bitmask = false
Tags
see
static::setPrecision()

$is_negative

Holds the BigInteger's sign

protected bool $is_negative

$isValidEngine

Engine Validity Flag

protected static bool $isValidEngine

$modexpEngine

Modular Exponentiation Engine

protected static string $modexpEngine

$one

BigInteger(1)

protected static GMP $one

$precision

Precision

protected mixed $precision = -1
Tags
see
static::setPrecision()

$primes

Primes > 2 and < 1000

protected static mixed $primes

Unused for GMP Engine

$reduce

Recurring Modulo Function

protected callable $reduce

$two

BigInteger(2)

protected static GMP $two

$value

Holds the BigInteger's value

protected mixed $value

$zero

BigInteger(0)

protected static GMP $zero

Methods

__construct()

Default constructor

public __construct([mixed $x = 0 ][, int $base = 10 ]) : GMP
Parameters
$x : mixed = 0

integer Base-10 number or base-$base number if $base set.

$base : int = 10
Tags
see
parent::__construct()
Return values
GMP

__debugInfo()

__debugInfo() magic method

public __debugInfo() : mixed

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

__toString()

Converts a BigInteger to a base-10 number.

public __toString() : string
Return values
string

abs()

Absolute value.

public abs() : GMP
Tags
access

public

Return values
GMP

add()

Adds two BigIntegers.

public add(GMP $y) : GMP
Parameters
$y : GMP
Return values
GMP

between()

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

public between(GMP $min, GMP $max) : bool
Parameters
$min : GMP
$max : GMP
Return values
bool

bitwise_and()

Logical And

public bitwise_and(GMP $x) : GMP
Parameters
$x : GMP
Return values
GMP

bitwise_leftRotate()

Logical Left Rotate

public bitwise_leftRotate(int $shift) : Engine

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

Parameters
$shift : int
Return values
Engine

bitwise_leftShift()

Logical Left Shift

public bitwise_leftShift(int $shift) : GMP

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

Parameters
$shift : int
Return values
GMP

bitwise_or()

Logical Or

public bitwise_or(GMP $x) : GMP
Parameters
$x : GMP
Return values
GMP

bitwise_rightRotate()

Logical Right Rotate

public bitwise_rightRotate(int $shift) : Engine

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

Parameters
$shift : int
Return values
Engine

bitwise_rightShift()

Logical Right Shift

public bitwise_rightShift(int $shift) : GMP

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

Parameters
$shift : int
Return values
GMP

bitwise_split()

Bitwise Split

public bitwise_split(int $split) : array<string|int, Engine>

Splits BigInteger's into chunks of $split bits

Parameters
$split : int
Return values
array<string|int, Engine>

bitwise_xor()

Logical Exclusive Or

public bitwise_xor(GMP $x) : GMP
Parameters
$x : GMP
Return values
GMP

compare()

Compares two numbers.

public compare(GMP $y) : int

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).

Parameters
$y : GMP
Tags
access

public

see
self::equals()
Return values
int

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

createRecurringModuloFunction()

Create Recurring Modulo Function

public createRecurringModuloFunction() : callable

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

Return values
callable

divide()

Divides two BigIntegers.

public divide(GMP $y) : GMP

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
$y : GMP
Return values
GMP

equals()

Tests the equality of two numbers.

public equals(GMP $x) : bool

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

Parameters
$x : GMP
Return values
bool

extendedGCD()

Calculates the greatest common divisor and Bezout's identity.

public extendedGCD(GMP $n) : array<string|int, GMP>

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 Bezout's identity - Wikipedia for more information.

Parameters
$n : GMP
Return values
array<string|int, GMP>

gcd()

Calculates the greatest common divisor

public gcd(GMP $n) : GMP

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

Parameters
$n : GMP
Return values
GMP

getLength()

Return the size of a BigInteger in bits

public getLength() : int
Return values
int

getLengthInBytes()

Return the size of a BigInteger in bytes

public getLengthInBytes() : int
Return values
int

getPrecision()

Get Precision

public getPrecision() : int

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

Return values
int

isNegative()

Is Negative?

public isNegative() : bool
Return values
bool

isOdd()

Is Odd?

public isOdd() : bool
Return values
bool

isPrime()

Checks a numer to see if it's prime

public isPrime([int|bool $t = false ]) : bool

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
$t : int|bool = false
Return values
bool

isValidEngine()

Test for engine validity

public static isValidEngine() : bool
Tags
see
parent::__construct()
Return values
bool

max()

Return the maximum BigInteger between an arbitrary number of BigIntegers.

public static max(GMP ...$nums) : GMP
Parameters
$nums : GMP
Return values
GMP

min()

Return the minimum BigInteger between an arbitrary number of BigIntegers.

public static min(GMP ...$nums) : GMP
Parameters
$nums : GMP
Return values
GMP

minMaxBits()

Returns the smallest and largest n-bit number

public static minMaxBits(int $bits) : array<string|int, Engine>
Parameters
$bits : int
Return values
array<string|int, Engine>

modInverse()

Calculates modular inverses.

public modInverse(GMP $n) : false|GMP

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

Parameters
$n : GMP
Return values
false|GMP

modPow()

Performs modular exponentiation.

public modPow(GMP $e, GMP $n) : GMP
Parameters
$e : GMP
$n : GMP
Return values
GMP

multiply()

Multiplies two BigIntegers.

public multiply(GMP $x) : GMP
Parameters
$x : GMP
Return values
GMP

negate()

Negate

public negate() : GMP

Given $k, returns -$k

Return values
GMP

pow()

Performs exponentiation.

public pow(GMP $n) : GMP
Parameters
$n : GMP
Return values
GMP

powMod()

Performs modular exponentiation.

public powMod(GMP $e, GMP $n) : GMP

Alias for modPow().

Parameters
$e : GMP
$n : GMP
Return values
GMP

random()

Generates a random number of a certain size

public static random(int $size) : Engine

Bit length is equal to $size

Parameters
$size : int
Return values
Engine

randomPrime()

Generates a random prime number of a certain size

public static randomPrime(int $size) : Engine

Bit length is equal to $size

Parameters
$size : int
Return values
Engine

randomRange()

Generate a random number between a range

public static randomRange(GMP $min, GMP $max) : GMP

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
$min : GMP
$max : GMP
Return values
GMP

randomRangePrime()

Generate a random prime number between a range

public static randomRangePrime(GMP $min, GMP $max) : false|GMP

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

Parameters
$min : GMP
$max : GMP
Return values
false|GMP

root()

Calculates the nth root of a biginteger.

public root([int $n = 2 ]) : Engine
Parameters
$n : int = 2
Return values
Engine

scan1divide()

Scan for 1 and right shift by that amount

public static scan1divide(GMP $r) : int

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

Parameters
$r : GMP
Return values
int

serialize()

Serialize

public serialize() : string

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

Return values
string

setModExpEngine()

Sets engine type.

public static setModExpEngine(string $engine) : mixed

Throws an exception if the type is invalid

Parameters
$engine : string

setPrecision()

Set Precision

public setPrecision(int $bits) : mixed

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

Parameters
$bits : int

subtract()

Subtracts two BigIntegers.

public subtract(GMP $y) : GMP
Parameters
$y : GMP
Return values
GMP

testBit()

Tests if a bit is set

public testBit(mixed $x) : bool
Parameters
$x : mixed
Return values
bool

toBits()

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

public toBits([bool $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.

Parameters
$twos_compliment : bool = false
Return values
string

toBytes()

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

public toBytes([bool $twos_compliment = false ]) : string
Parameters
$twos_compliment : bool = false
Return values
string

toHex()

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

public toHex([bool $twos_compliment = false ]) : string
Parameters
$twos_compliment : bool = false
Return values
string

toString()

Converts a BigInteger to a base-10 number.

public toString() : string
Return values
string

unserialize()

Serialize

public unserialize(string $serialized) : mixed

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

Parameters
$serialized : string

base256_lshift()

Logical Left Shift

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

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

Parameters
$x : string
$shift : int
Return values
string

extendedGCDHelper()

Calculates the greatest common divisor and Bezout's identity.

protected extendedGCDHelper(Engine $n[, Engine $stop = null ]) : Engine
Parameters
$n : Engine
$stop : Engine = null

(optional)

Return values
Engine

initialize()

Initialize a GMP BigInteger Engine instance

protected initialize(int $base) : mixed
Parameters
$base : int
Tags
see
parent::__construct()

make_odd()

Make the current number odd

protected make_odd() : mixed

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

Tags
see
self::randomPrime()

maxHelper()

Return the minimum BigInteger between an arbitrary number of BigIntegers.

protected static maxHelper(array<string|int, mixed> $nums) : Engine
Parameters
$nums : array<string|int, mixed>
Return values
Engine

minHelper()

Return the minimum BigInteger between an arbitrary number of BigIntegers.

protected static minHelper(array<string|int, mixed> $nums) : Engine
Parameters
$nums : array<string|int, mixed>
Return values
Engine

modInverseHelper()

Calculates modular inverses.

protected modInverseHelper(Engine $n) : Engine|false

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

Parameters
$n : Engine
Return values
Engine|false

normalize()

Normalize

protected normalize(GMP $result) : GMP

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

Parameters
$result : GMP
Return values
GMP

powModInner()

Performs modular exponentiation.

protected powModInner(GMP $e, GMP $n) : GMP
Parameters
$e : GMP
$n : GMP
Return values
GMP

randomRangeHelper()

Generate a random number between a range

protected static randomRangeHelper(Engine $min, Engine $max) : 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)

Parameters
$min : Engine
$max : Engine
Return values
Engine

randomRangePrimeOuter()

Performs some pre-processing for randomRangePrime

protected static randomRangePrimeOuter(Engine $min, Engine $max) : bool|Engine
Parameters
$min : Engine
$max : Engine
Return values
bool|Engine

rootHelper()

Performs a few preliminary checks on root

protected rootHelper(int $n) : Engine
Parameters
$n : int
Return values
Engine

rootInner()

Calculates the nth root of a biginteger.

protected rootInner(int $n) : GMP

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

Parameters
$n : int
Return values
GMP

setBitmask()

Set Bitmask

protected static setBitmask(int $bits) : Engine
Parameters
$bits : int
Tags
see
self::setPrecision()
Return values
Engine

setupIsPrime()

Sets the $t parameter for primality testing

protected setupIsPrime() : int
Return values
int

slidingWindow()

Sliding Window k-ary Modular Exponentiation

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

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.

Parameters
$x : Engine
$e : Engine
$n : Engine
$class : string
Return values
Engine

testPrimality()

Tests Primality

protected testPrimality(int $t) : bool
Parameters
$t : int
Return values
bool

toBytesHelper()

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

protected 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.

Return values
string

        
On this page

Search results