[Summary view] [Print] [Text view]

   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 <[email protected]>
  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 <[email protected]>
  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  }