1<?php 2 3/** 4 * BCMath Dynamic Barrett Modular Exponentiation Engine 5 * 6 * PHP version 5 and 7 7 * 8 * @category Math 9 * @package BigInteger 10 * @author Jim Wigginton <terrafrost@php.net> 11 * @copyright 2017 Jim Wigginton 12 * @license http://www.opensource.org/licenses/mit-license.html MIT License 13 * @link http://pear.php.net/package/Math_BigInteger 14 */ 15 16namespace phpseclib3\Math\BigInteger\Engines\BCMath\Reductions; 17 18use phpseclib3\Math\BigInteger\Engines\BCMath; 19use phpseclib3\Math\BigInteger\Engines\BCMath\Base; 20 21/** 22 * PHP Barrett Modular Exponentiation Engine 23 * 24 * @package PHP 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @access public 27 */ 28abstract class EvalBarrett extends Base 29{ 30 /** 31 * Custom Reduction Function 32 * 33 * @see self::generateCustomReduction 34 */ 35 private static $custom_reduction; 36 37 /** 38 * Barrett Modular Reduction 39 * 40 * This calls a dynamically generated loop unrolled function that's specific to a given modulo. 41 * Array lookups are avoided as are if statements testing for how many bits the host OS supports, etc. 42 * 43 * @param string $n 44 * @param string $m 45 * @return string 46 */ 47 protected static function reduce($n, $m) 48 { 49 $inline = self::$custom_reduction; 50 return $inline($n); 51 } 52 53 /** 54 * Generate Custom Reduction 55 * 56 * @param BCMath $m 57 * @param string $class 58 * @return callable|void 59 */ 60 protected static function generateCustomReduction(BCMath $m, $class) 61 { 62 $m_length = strlen($m); 63 64 if ($m_length < 5) { 65 $code = 'return bcmod($x, $n);'; 66 eval('$func = function ($n) { ' . $code . '};'); 67 self::$custom_reduction = $func; 68 return; 69 } 70 71 $lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1)); 72 $u = bcdiv($lhs, $m, 0); 73 $m1 = bcsub($lhs, bcmul($u, $m)); 74 75 $cutoff = $m_length + ($m_length >> 1); 76 77 $m = "'$m'"; 78 $u = "'$u'"; 79 $m1 = "'$m1'"; 80 81 $code = ' 82 $lsd = substr($n, -' . $cutoff . '); 83 $msd = substr($n, 0, -' . $cutoff . '); 84 85 $temp = bcmul($msd, ' . $m1 . '); 86 $n = bcadd($lsd, $temp); 87 88 $temp = substr($n, 0, ' . (-$m_length + 1) . '); 89 $temp = bcmul($temp, ' . $u . '); 90 $temp = substr($temp, 0, ' . (-($m_length >> 1) - 1) . '); 91 $temp = bcmul($temp, ' . $m . '); 92 93 $result = bcsub($n, $temp); 94 95 if ($result[0] == \'-\') { 96 $temp = \'1' . str_repeat('0', $m_length + 1) . '\'; 97 $result = bcadd($result, $temp); 98 } 99 100 while (bccomp($result, ' . $m . ') >= 0) { 101 $result = bcsub($result, ' . $m . '); 102 } 103 104 return $result;'; 105 106 eval('$func = function ($n) { ' . $code . '};'); 107 108 self::$custom_reduction = $func; 109 110 return $func; 111 } 112} 113