Documentation

Montgomery extends Montgomery
in package

PHP

AbstractYes

PHP Montgomery Modular Exponentiation Engine

Constants

DATA = 1: $cache[self::DATA] contains the cached data.
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.
VARIABLE = 0: Cache constants

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
isValidEngine() : bool: Test for engine validity
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.
modInverse67108864() : int: Modular Inverse of a number mod 2**26 (eg. 67108864)
modInverseHelper() : Engine|false: Calculates modular inverses.
multiplyHelper() : array<string|int, mixed>: Performs multiplication.
multiplyReduce() : array<string|int, mixed>: Modular multiply
normalize() : PHP: Normalize
pad() : string: Pads strings so that unpack may be used on them
powHelper() : PHP: Performs exponentiation.
powModHelper() : PHP: Performs modular exponentiation.
powModInner() : PHP: Performs modular exponentiation.
powModOuter() : bool|Engine: Performs some pre-processing for powMod
prepareReduce() : array<string|int, mixed>: Prepare a number for use in Montgomery Modular Reductions
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
reduce() : array<string|int, mixed>: Montgomery Multiply
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: Performs modular exponentiation.
square() : array<string|int, mixed>: Performs squaring
squareReduce() : array<string|int, mixed>: Modular square
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

DATA

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


    public
        mixed
    DATA
    = 1

ENGINE_DIR

Engine Directory


    public
        mixed
    ENGINE_DIR
    = 'PHP'

FAST_BITWISE

Can Bitwise operations be done fast?


    public
        mixed
    FAST_BITWISE
    = true

KARATSUBA_CUTOFF

Karatsuba Cutoff


    public
        mixed
    KARATSUBA_CUTOFF
    = 25

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

SIGN

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


    public
        mixed
    SIGN
    = 1

VALUE

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


    public
        mixed
    VALUE
    = 0

VARIABLE

Cache constants


    public
        mixed
    VARIABLE
    = 0

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

$bitmask

Precision Bitmask


    protected
        mixed
    $bitmask
     = false

$is_negative

Holds the BigInteger's sign


    protected
        bool
    $is_negative

$precision

Precision


    protected
        mixed
    $precision
     = -1

$reduce

Recurring Modulo Function


    protected
        callable
    $reduce

$value

Holds the BigInteger's value


    protected
        mixed
    $value

__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

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_not()

Logical Not


    public
                    bitwise_not() : Engine|string

Return values

Engine|string

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

isValidEngine()

Test for engine validity


    public
            static        isValidEngine() : bool

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

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>

bitwiseAndHelper()

Logical And


    protected
                    bitwiseAndHelper(Engine $x) : Engine

Parameters

$x : Engine

Return values

Engine

bitwiseOrHelper()

Logical Or


    protected
                    bitwiseOrHelper(Engine $x) : Engine

Parameters

$x : Engine

Return values

Engine

bitwiseXorHelper()

Logical Exclusive Or


    protected
                    bitwiseXorHelper(Engine $x) : Engine

Parameters

$x : Engine

Return values

Engine

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

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.

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

modInverse67108864()

Modular Inverse of a number mod 2**26 (eg. 67108864)


    protected
            static        modInverse67108864(array<string|int, mixed> $x, string $class) : int

Based off of the bnpInvDigit function implemented and justified in the following URL:

The following URL provides more info:

As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 40 bits, which only 64-bit floating points will support.

Thanks to Pedro Gimeno Fortea for input!

Parameters

$x : array<string|int, mixed>
$class : string

Return values

int

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>

multiplyReduce()

Modular multiply


    protected
            static        multiplyReduce(array<string|int, mixed> $x, array<string|int, mixed> $y, array<string|int, mixed> $n, string $class) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$y : array<string|int, mixed>
$n : array<string|int, mixed>
$class : string

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

powModHelper()

Performs modular exponentiation.


    protected
            static        powModHelper(PHP $x, PHP $e, PHP $n, string $class) : 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.

Parameters

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

Return values

PHP

powModInner()

Performs modular exponentiation.


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

Parameters

$e : PHP
$n : PHP

Return values

PHP

powModOuter()

Performs some pre-processing for powMod


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

Parameters

$e : Engine
$n : Engine

Return values

bool|Engine

prepareReduce()

Prepare a number for use in Montgomery Modular Reductions


    protected
            static        prepareReduce(array<string|int, mixed> $x, array<string|int, mixed> $n, string $class) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$class : string

Return values

array<string|int, mixed>

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

randomRangePrimeInner()

Performs some post-processing for randomRangePrime


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

Parameters

$x : Engine
$min : Engine
$max : Engine

Return values

bool|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

reduce()

Montgomery Multiply


    protected
            static        reduce(array<string|int, mixed> $x, array<string|int, mixed> $n, string $class) : array<string|int, mixed>

Interleaves the montgomery reduction and long multiplication algorithms together as described in HAC 14.36

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$class : string

Return values

array<string|int, mixed>

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

Return values

Engine

setupIsPrime()

Sets the $t parameter for primality testing


    protected
                    setupIsPrime() : int

Return values

int

slidingWindow()

Performs modular exponentiation.


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

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>

squareReduce()

Modular square


    protected
            static        squareReduce(array<string|int, mixed> $x, array<string|int, mixed> $n, string $class) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$class : string

Return values

array<string|int, mixed>

testPrimality()

Tests Primality


    protected
                    testPrimality(int $t) : bool

Uses the Miller-Rabin primality test. See HAC 4.24 for more info.

Parameters

$t : int

Return values

bool

testSmallPrimes()

Test the number against small primes.


    protected
                    testSmallPrimes() : mixed

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

Montgomery extends Montgomery in package PHP

Tags

Table of Contents

Constants

Properties

Methods

Constants

DATA

Tags

ENGINE_DIR

Tags

FAST_BITWISE

Tags

KARATSUBA_CUTOFF

Tags

SIGN

VALUE

VARIABLE

Tags

Properties

$bitmask

Tags

$is_negative

$precision

Tags

$reduce

$value

Methods

__construct()

Parameters

Tags

Return values

__debugInfo()

__toString()

Return values

abs()

Return values

bitwise_leftRotate()

Parameters

Return values

bitwise_leftShift()

Parameters

Return values

bitwise_not()

Return values

bitwise_rightRotate()

Parameters

Return values

bitwise_rightShift()

Parameters

Return values

bitwise_split()

Parameters

Return values

createRecurringModuloFunction()

Return values

getLength()

Return values

getLengthInBytes()

Return values

getPrecision()

Return values

isNegative()

Return values

Montgomery extends Montgomery
in package

PHP