backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
/
Reductions
/
MontgomeryMult.php
backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
/
Reductions
Last commit date
.htaccess
1 year ago
Barrett.php
1 year ago
Classic.php
1 year ago
EvalBarrett.php
1 year ago
Montgomery.php
1 year ago
MontgomeryMult.php
1 year ago
PowerOfTwo.php
1 year ago
index.html
1 year ago
web.config
1 year ago
MontgomeryMult.php
75 lines
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * PHP Montgomery Modular Exponentiation Engine with interleaved multiplication |
| 5 | * |
| 6 | * PHP version 5 and 7 |
| 7 | * |
| 8 | * @author Jim Wigginton <terrafrost@php.net> |
| 9 | * @copyright 2017 Jim Wigginton |
| 10 | * @license http://www.opensource.org/licenses/mit-license.html MIT License |
| 11 | * @link http://pear.php.net/package/Math_BigInteger |
| 12 | */ |
| 13 | |
| 14 | declare(strict_types=1); |
| 15 | |
| 16 | namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions; |
| 17 | |
| 18 | use phpseclib3\Math\BigInteger\Engines\PHP; |
| 19 | |
| 20 | /** |
| 21 | * PHP Montgomery Modular Exponentiation Engine with interleaved multiplication |
| 22 | * |
| 23 | * @author Jim Wigginton <terrafrost@php.net> |
| 24 | */ |
| 25 | abstract class MontgomeryMult extends Montgomery |
| 26 | { |
| 27 | /** |
| 28 | * Montgomery Multiply |
| 29 | * |
| 30 | * Interleaves the montgomery reduction and long multiplication algorithms together as described in |
| 31 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} |
| 32 | * |
| 33 | * @param class-string<PHP> $class |
| 34 | * @see self::_prepMontgomery() |
| 35 | * @see self::_montgomery() |
| 36 | */ |
| 37 | public static function multiplyReduce(array $x, array $y, array $m, string $class): array |
| 38 | { |
| 39 | // the following code, although not callable, can be run independently of the above code |
| 40 | // although the above code performed better in my benchmarks the following could might |
| 41 | // perform better under different circumstances. in lieu of deleting it it's just been |
| 42 | // made uncallable |
| 43 | |
| 44 | static $cache = [ |
| 45 | self::VARIABLE => [], |
| 46 | self::DATA => [], |
| 47 | ]; |
| 48 | |
| 49 | if (($key = array_search($m, $cache[self::VARIABLE])) === false) { |
| 50 | $key = count($cache[self::VARIABLE]); |
| 51 | $cache[self::VARIABLE][] = $m; |
| 52 | $cache[self::DATA][] = self::modInverse67108864($m, $class); |
| 53 | } |
| 54 | |
| 55 | $n = max(count($x), count($y), count($m)); |
| 56 | $x = array_pad($x, $n, 0); |
| 57 | $y = array_pad($y, $n, 0); |
| 58 | $m = array_pad($m, $n, 0); |
| 59 | $a = [self::VALUE => self::array_repeat(0, $n + 1)]; |
| 60 | for ($i = 0; $i < $n; ++$i) { |
| 61 | $temp = $a[self::VALUE][0] + $x[$i] * $y[0]; |
| 62 | $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); |
| 63 | $temp = $temp * $cache[self::DATA][$key]; |
| 64 | $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); |
| 65 | $temp = $class::addHelper($class::regularMultiply([$x[$i]], $y), false, $class::regularMultiply([$temp], $m), false); |
| 66 | $a = $class::addHelper($a[self::VALUE], false, $temp[self::VALUE], false); |
| 67 | $a[self::VALUE] = array_slice($a[self::VALUE], 1); |
| 68 | } |
| 69 | if (self::compareHelper($a[self::VALUE], false, $m, false) >= 0) { |
| 70 | $a = $class::subtractHelper($a[self::VALUE], false, $m, false); |
| 71 | } |
| 72 | return $a[self::VALUE]; |
| 73 | } |
| 74 | } |
| 75 |