[ Index ]

PHP Cross Reference of DokuWiki

title

Body

[close]

/vendor/phpseclib/phpseclib/phpseclib/Math/BigInteger/Engines/PHP/ -> Base.php (summary)

PHP Modular Exponentiation Engine PHP version 5 and 7

Author: Jim Wigginton
Copyright: 2017 Jim Wigginton
License: http://www.opensource.org/licenses/mit-license.html MIT License
Link: http://pear.php.net/package/Math_BigInteger
File Size: 143 lines (5 kb)
Included or required:0 times
Referenced: 0 times
Includes or requires: 0 files

Defines 5 functions

  isValidEngine()
  powModHelper()
  prepareReduce()
  multiplyReduce()
  squareReduce()

Functions
Functions that are not part of a class:

isValidEngine()   X-Ref
Test for engine validity

return: bool

powModHelper(PHP $x, PHP $e, PHP $n, $class)   X-Ref
Performs modular exponentiation.

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.
{@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.

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

prepareReduce(array $x, array $n, $class)   X-Ref
Modular reduction preparation

param: array $x
param: array $n
param: string $class
return: array
see: self::slidingWindow()

multiplyReduce(array $x, array $y, array $n, $class)   X-Ref
Modular multiply

param: array $x
param: array $y
param: array $n
param: string $class
return: array
see: self::slidingWindow()

squareReduce(array $x, array $n, $class)   X-Ref
Modular square

param: array $x
param: array $n
param: string $class
return: array
see: self::slidingWindow()