Montgomery
extends Montgomery
in package
PHP Montgomery Modular Exponentiation Engine
Tags
Table of Contents
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
Constants
DATA
$cache[self::DATA] contains the cached data.
public
mixed
DATA
= 1
Tags
ENGINE_DIR
Engine Directory
public
mixed
ENGINE_DIR
= 'PHP'
Tags
FAST_BITWISE
Can Bitwise operations be done fast?
public
mixed
FAST_BITWISE
= true
Tags
KARATSUBA_CUTOFF
Karatsuba Cutoff
public
mixed
KARATSUBA_CUTOFF
= 25
At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
Tags
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.
Tags
Properties
$bitmask
Precision Bitmask
protected
mixed
$bitmask
= false
Tags
$is_negative
Holds the BigInteger's sign
protected
bool
$is_negative
$precision
Precision
protected
mixed
$precision
= -1
Tags
$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
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
stringabs()
Absolute value.
public
abs() : PHP
Return values
PHPbitwise_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
Enginebitwise_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
PHPbitwise_not()
Logical Not
public
bitwise_not() : Engine|string
Return values
Engine|stringbitwise_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
Enginebitwise_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
PHPbitwise_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
callablegetLength()
Return the size of a BigInteger in bits
public
getLength() : int
Return values
intgetLengthInBytes()
Return the size of a BigInteger in bytes
public
getLengthInBytes() : int
Return values
intgetPrecision()
Get Precision
public
getPrecision() : int
Returns the precision if it exists, -1 if it doesn't
Return values
intisNegative()
Is Negative?
public
isNegative() : bool
Return values
boolisOdd()
Is Odd?
public
isOdd() : bool
Return values
boolisPrime()
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
boolisValidEngine()
Test for engine validity
public
static isValidEngine() : bool
Return values
boolminMaxBits()
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
BigIntegerrandom()
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
EnginerandomPrime()
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
Engineroot()
Calculates the nth root of a biginteger.
public
root([int $n = 2 ]) : Engine
Parameters
- $n : int = 2
Return values
Enginescan1divide()
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
Return values
intserialize()
Serialize
public
serialize() : string
Will be called, automatically, when serialize() is called on a BigInteger object.
Return values
stringsetModExpEngine()
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
booltoBits()
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
stringtoBytes()
Converts a BigInteger to a byte string (eg. base-256).
public
toBytes([bool $twos_compliment = false ]) : string
Parameters
- $twos_compliment : bool = false
Return values
stringtoHex()
Converts a BigInteger to a hex string (eg. base-16).
public
toHex([bool $twos_compliment = false ]) : string
Parameters
- $twos_compliment : bool = false
Return values
stringtoString()
Converts a BigInteger to a base-10 number.
public
toString() : string
Return values
stringunserialize()
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
stringbaseSquare()
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
EnginebitwiseOrHelper()
Logical Or
protected
bitwiseOrHelper(Engine $x) : Engine
Parameters
- $x : Engine
Return values
EnginebitwiseXorHelper()
Logical Exclusive Or
protected
bitwiseXorHelper(Engine $x) : Engine
Parameters
- $x : Engine
Return values
EnginecompareHelper()
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
Return values
Engineinitialize()
Initialize a PHP BigInteger Engine instance
protected
initialize(int $base) : mixed
Parameters
- $base : int
Tags
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
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
EngineminHelper()
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
EnginemodInverse67108864()
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
intmodInverseHelper()
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|falsemultiplyHelper()
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
Tags
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
PHPpad()
Pads strings so that unpack may be used on them
protected
pad(string $str) : string
Parameters
- $str : string
Return values
stringpowHelper()
Performs exponentiation.
protected
powHelper(PHP $n) : PHP
Parameters
- $n : PHP
Return values
PHPpowModHelper()
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
Return values
PHPpowModInner()
Performs modular exponentiation.
protected
powModInner(PHP $e, PHP $n) : PHP
Parameters
Return values
PHPpowModOuter()
Performs some pre-processing for powMod
protected
powModOuter(Engine $e, Engine $n) : bool|Engine
Parameters
Return values
bool|EngineprepareReduce()
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
Return values
EnginerandomRangePrimeInner()
Performs some post-processing for randomRangePrime
protected
static randomRangePrimeInner(Engine $x, Engine $min, Engine $max) : bool|Engine
Parameters
Return values
bool|EnginerandomRangePrimeOuter()
Performs some pre-processing for randomRangePrime
protected
static randomRangePrimeOuter(Engine $min, Engine $max) : bool|Engine
Parameters
Return values
bool|Enginereduce()
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
EnginerootInner()
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
Enginershift()
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
Return values
EnginesetupIsPrime()
Sets the $t parameter for primality testing
protected
setupIsPrime() : int
Return values
intslidingWindow()
Performs modular exponentiation.
protected
static slidingWindow(Engine $x, Engine $e, Engine $n, string $class) : Engine
Parameters
Return values
Enginesquare()
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
Tags
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
booltestSmallPrimes()
Test the number against small primes.
protected
testSmallPrimes() : mixed
Tags
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
stringtrim()
Trim
protected
static trim(array<string|int, mixed> $value) : PHP
Removes leading zeros
Parameters
- $value : array<string|int, mixed>
Return values
PHPbitwise_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
stringkaratsuba()
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