backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
/
Montgomery.php
backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
Last commit date
Reductions
1 year ago
.htaccess
1 year ago
Base.php
1 year ago
DefaultEngine.php
1 year ago
Montgomery.php
1 year ago
OpenSSL.php
1 year ago
index.html
1 year ago
web.config
1 year ago
Montgomery.php
87 lines
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * PHP Montgomery Modular Exponentiation Engine |
| 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; |
| 17 | |
| 18 | use phpseclib3\Math\BigInteger\Engines\Engine; |
| 19 | use phpseclib3\Math\BigInteger\Engines\PHP; |
| 20 | use phpseclib3\Math\BigInteger\Engines\PHP\Reductions\PowerOfTwo; |
| 21 | |
| 22 | /** |
| 23 | * PHP Montgomery Modular Exponentiation Engine |
| 24 | * |
| 25 | * @author Jim Wigginton <terrafrost@php.net> |
| 26 | */ |
| 27 | abstract class Montgomery extends Base |
| 28 | { |
| 29 | /** |
| 30 | * Test for engine validity |
| 31 | */ |
| 32 | public static function isValidEngine(): bool |
| 33 | { |
| 34 | return static::class != __CLASS__; |
| 35 | } |
| 36 | |
| 37 | /** |
| 38 | * Performs modular exponentiation. |
| 39 | * |
| 40 | * @template T of Engine |
| 41 | * @param class-string<T> $class |
| 42 | * @return T |
| 43 | */ |
| 44 | protected static function slidingWindow(Engine $x, Engine $e, Engine $n, string $class) |
| 45 | { |
| 46 | // is the modulo odd? |
| 47 | if ($n->value[0] & 1) { |
| 48 | return parent::slidingWindow($x, $e, $n, $class); |
| 49 | } |
| 50 | // if it's not, it's even |
| 51 | |
| 52 | // find the lowest set bit (eg. the max pow of 2 that divides $n) |
| 53 | for ($i = 0; $i < count($n->value); ++$i) { |
| 54 | if ($n->value[$i]) { |
| 55 | $temp = decbin($n->value[$i]); |
| 56 | $j = strlen($temp) - strrpos($temp, '1') - 1; |
| 57 | $j += $class::BASE * $i; |
| 58 | break; |
| 59 | } |
| 60 | } |
| 61 | // at this point, 2^$j * $n/(2^$j) == $n |
| 62 | |
| 63 | $mod1 = clone $n; |
| 64 | $mod1->rshift($j); |
| 65 | $mod2 = new $class(); |
| 66 | $mod2->value = [1]; |
| 67 | $mod2->lshift($j); |
| 68 | |
| 69 | $part1 = $mod1->value != [1] ? parent::slidingWindow($x, $e, $mod1, $class) : new $class(); |
| 70 | $part2 = PowerOfTwo::slidingWindow($x, $e, $mod2, $class); |
| 71 | |
| 72 | $y1 = $mod2->modInverse($mod1); |
| 73 | $y2 = $mod1->modInverse($mod2); |
| 74 | |
| 75 | $result = $part1->multiply($mod2); |
| 76 | $result = $result->multiply($y1); |
| 77 | |
| 78 | $temp = $part2->multiply($mod1); |
| 79 | $temp = $temp->multiply($y2); |
| 80 | |
| 81 | $result = $result->add($temp); |
| 82 | [, $result] = $result->divide($n); |
| 83 | |
| 84 | return $result; |
| 85 | } |
| 86 | } |
| 87 |