Subversion Repositories oidplus

Rev

Rev 846 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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.  
  16. namespace phpseclib3\Math\BigInteger\Engines\BCMath\Reductions;
  17.  
  18. use phpseclib3\Math\BigInteger\Engines\BCMath;
  19. use 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.  */
  28. abstract 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.