Documentation

PHP extends Engine
in package

AbstractYes

Pure-PHP Engine.

Tags
author

Jim Wigginton terrafrost@php.net

access

public

Table of Contents

Constants

ENGINE_DIR  = 'PHP'
Engine Directory
FAST_BITWISE  = true
Can Bitwise operations be done fast?
KARATSUBA_CUTOFF  = 25
Karatsuba Cutoff
SIGN  = 1
$result[self::SIGN] contains the sign.
VALUE  = 0
$result[self::VALUE] contains the value.

Properties

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

Methods

__construct()  : PHP
Default constructor
__debugInfo()  : mixed
__debugInfo() magic method
__toString()  : string
Converts a BigInteger to a base-10 number.
abs()  : PHP
Absolute value.
bitwise_leftRotate()  : Engine
Logical Left Rotate
bitwise_leftShift()  : PHP
Logical Left Shift
bitwise_not()  : Engine|string
Logical Not
bitwise_rightRotate()  : Engine
Logical Right Rotate
bitwise_rightShift()  : PHP
Logical Right Shift
bitwise_split()  : array<string|int, PHP>
Bitwise Split
createRecurringModuloFunction()  : callable
Create Recurring Modulo Function
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
minMaxBits()  : array<string|int, Engine>
Returns the smallest and largest n-bit number
negate()  : BigInteger
Negate
random()  : Engine
Generates a random number of a certain size
randomPrime()  : Engine
Generates a random prime number of a certain size
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
subtractHelper()  : array<string|int, mixed>
Performs subtraction.
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
addHelper()  : array<string|int, mixed>
Performs addition.
array_repeat()  : array<string|int, mixed>
Array Repeat
base256_lshift()  : string
Logical Left Shift
baseSquare()  : array<string|int, mixed>
Performs traditional squaring on two BigIntegers
bitwiseAndHelper()  : Engine
Logical And
bitwiseOrHelper()  : Engine
Logical Or
bitwiseXorHelper()  : Engine
Logical Exclusive Or
compareHelper()  : mixed
convertToObj()  : mixed
extendedGCDHelper()  : Engine
Calculates the greatest common divisor and Bezout's identity.
initialize()  : mixed
Initialize a PHP BigInteger Engine instance
karatsubaSquare()  : array<string|int, mixed>
Performs Karatsuba "squaring" on two BigIntegers
lshift()  : mixed
Logical Left Shift
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.
multiplyHelper()  : array<string|int, mixed>
Performs multiplication.
normalize()  : PHP
Normalize
pad()  : string
Pads strings so that unpack may be used on them
powHelper()  : PHP
Performs exponentiation.
powModInner()  : PHP
Performs modular exponentiation.
powModOuter()  : bool|Engine
Performs some pre-processing for powMod
randomRangeHelper()  : Engine
Generate a random number between a range
randomRangePrimeInner()  : bool|Engine
Performs some post-processing for randomRangePrime
randomRangePrimeOuter()  : bool|Engine
Performs some pre-processing for randomRangePrime
regularMultiply()  : array<string|int, mixed>
Performs long multiplication on two BigIntegers
rootHelper()  : Engine
Performs a few preliminary checks on root
rootInner()  : Engine
Calculates the nth root of a biginteger.
rshift()  : mixed
Logical Right Shift
setBitmask()  : Engine
Set Bitmask
setupIsPrime()  : int
Sets the $t parameter for primality testing
slidingWindow()  : Engine
Sliding Window k-ary Modular Exponentiation
square()  : array<string|int, mixed>
Performs squaring
testPrimality()  : bool
Tests Primality
testSmallPrimes()  : mixed
Test the number against small primes.
toBytesHelper()  : string
Converts a BigInteger to a byte string (eg. base-256).
trim()  : PHP
Trim
bitwise_small_split()  : array<string|int, PHP>
Bitwise Split where $split < static::BASE
divide_digit()  : array<string|int, mixed>
Divides a BigInteger by a regular integer
int2bytes()  : string
Converts 32-bit integers to bytes.
karatsuba()  : array<string|int, mixed>
Performs Karatsuba multiplication on two BigIntegers
safe_divide()  : int
Single digit division

Constants

ENGINE_DIR

Engine Directory

public mixed ENGINE_DIR = 'PHP'
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

KARATSUBA_CUTOFF

Karatsuba Cutoff

public mixed KARATSUBA_CUTOFF = 25

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

Tags
access

private

SIGN

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

public mixed SIGN = 1

VALUE

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

public mixed VALUE = 0

Properties

$bitmask

Precision Bitmask

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

$is_negative

Holds the BigInteger's sign

protected bool $is_negative

$precision

Precision

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

$reduce

Recurring Modulo Function

protected callable $reduce

$value

Holds the BigInteger's value

protected mixed $value

Methods

__construct()

Default constructor

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

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

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

__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() : PHP
Return values
PHP

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) : PHP

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

Parameters
$shift : int
Return values
PHP

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) : PHP

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

Parameters
$shift : int
Return values
PHP

bitwise_split()

Bitwise Split

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

Splits BigInteger's into chunks of $split bits

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

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

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

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>

negate()

Negate

public negate() : BigInteger

Given $k, returns -$k

Return values
BigInteger

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

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(PHP $r) : int

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

Parameters
$r : PHP
Tags
see
self::isPrime()
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

subtractHelper()

Performs subtraction.

public static subtractHelper(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>
Parameters
$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool
Return values
array<string|int, mixed>

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

addHelper()

Performs addition.

protected static addHelper(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>
Parameters
$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool
Return values
array<string|int, mixed>

array_repeat()

Array Repeat

protected static array_repeat(int $input, int $multiplier) : array<string|int, mixed>
Parameters
$input : int
$multiplier : int
Return values
array<string|int, mixed>

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

baseSquare()

Performs traditional squaring on two BigIntegers

protected static baseSquare(array<string|int, mixed> $value) : array<string|int, mixed>

Squaring can be done faster than multiplying a number by itself can be. See HAC 14.2.4 / MPM 5.3 for more information.

Parameters
$value : array<string|int, mixed>
Return values
array<string|int, mixed>

compareHelper()

protected static compareHelper(array<string|int, mixed> $x_value, mixed $x_negative, array<string|int, mixed> $y_value, mixed $y_negative) : mixed
Parameters
$x_value : array<string|int, mixed>
$x_negative : mixed
$y_value : array<string|int, mixed>
$y_negative : mixed

convertToObj()

protected convertToObj(array<string|int, mixed> $arr) : mixed
Parameters
$arr : array<string|int, mixed>

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 PHP BigInteger Engine instance

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

karatsubaSquare()

Performs Karatsuba "squaring" on two BigIntegers

protected static karatsubaSquare(array<string|int, mixed> $value) : array<string|int, mixed>

See Karatsuba algorithm and MPM 5.3.4.

Parameters
$value : array<string|int, mixed>
Return values
array<string|int, mixed>

lshift()

Logical Left Shift

protected lshift(int $shift) : mixed

Shifts BigInteger's by $shift bits.

Parameters
$shift : int

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

multiplyHelper()

Performs multiplication.

protected static multiplyHelper(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>
Parameters
$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool
Return values
array<string|int, mixed>

normalize()

Normalize

protected normalize(PHP $result) : PHP

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

Parameters
$result : PHP
Return values
PHP

pad()

Pads strings so that unpack may be used on them

protected pad(string $str) : string
Parameters
$str : string
Return values
string

powHelper()

Performs exponentiation.

protected powHelper(PHP $n) : PHP
Parameters
$n : PHP
Return values
PHP

powModInner()

Performs modular exponentiation.

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

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

regularMultiply()

Performs long multiplication on two BigIntegers

protected static regularMultiply(array<string|int, mixed> $x_value, array<string|int, mixed> $y_value) : array<string|int, mixed>

Modeled after 'multiply' in MutableBigInteger.java.

Parameters
$x_value : array<string|int, mixed>
$y_value : array<string|int, mixed>
Return values
array<string|int, mixed>

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) : Engine

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

Parameters
$n : int
Return values
Engine

rshift()

Logical Right Shift

protected rshift(int $shift) : mixed

Shifts BigInteger's by $shift bits.

Parameters
$shift : int

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

square()

Performs squaring

protected static square(array<string|int, mixed> $x) : array<string|int, mixed>
Parameters
$x : array<string|int, mixed>
Return values
array<string|int, mixed>

testSmallPrimes()

Test the number against small primes.

protected testSmallPrimes() : mixed
Tags
see
self::isPrime()

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

trim()

Trim

protected static trim(array<string|int, mixed> $value) : PHP

Removes leading zeros

Parameters
$value : array<string|int, mixed>
Return values
PHP

bitwise_small_split()

Bitwise Split where $split < static::BASE

private bitwise_small_split(int $split) : array<string|int, PHP>
Parameters
$split : int
Return values
array<string|int, PHP>

divide_digit()

Divides a BigInteger by a regular integer

private static divide_digit(array<string|int, mixed> $dividend, int $divisor) : array<string|int, mixed>

abc / x = a00 / x + b0 / x + c / x

Parameters
$dividend : array<string|int, mixed>
$divisor : int
Return values
array<string|int, mixed>

int2bytes()

Converts 32-bit integers to bytes.

private static int2bytes(int $x) : string
Parameters
$x : int
Return values
string

karatsuba()

Performs Karatsuba multiplication on two BigIntegers

private static karatsuba(array<string|int, mixed> $x_value, array<string|int, mixed> $y_value) : array<string|int, mixed>

See Karatsuba algorithm and MPM 5.2.3.

Parameters
$x_value : array<string|int, mixed>
$y_value : array<string|int, mixed>
Return values
array<string|int, mixed>

safe_divide()

Single digit division

private static safe_divide(int $x, int $y) : int

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.

Parameters
$x : int
$y : int
Return values
int

        
On this page

Search results