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