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.  * PHP 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\PHP\Reductions;
  17.  
  18. use phpseclib3\Math\BigInteger\Engines\PHP;
  19. use phpseclib3\Math\BigInteger\Engines\PHP\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 Barrett extends Base
  29. {
  30.     /**
  31.      * Barrett Modular Reduction
  32.      *
  33.      * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  34.      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
  35.      * so as not to require negative numbers (initially, this script didn't support negative numbers).
  36.      *
  37.      * Employs "folding", as described at
  38.      * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
  39.      * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
  40.      *
  41.      * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  42.      * usable on account of (1) its not using reasonable radix points as discussed in
  43.      * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  44.      * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
  45.      * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
  46.      * comments for details.
  47.      *
  48.      * @param array $n
  49.      * @param array $m
  50.      * @param class-string<PHP> $class
  51.      * @return array
  52.      */
  53.     protected static function reduce(array $n, array $m, $class)
  54.     {
  55.         static $cache = [
  56.             self::VARIABLE => [],
  57.             self::DATA => []
  58.         ];
  59.  
  60.         $m_length = count($m);
  61.  
  62.         // if (self::compareHelper($n, $static::square($m)) >= 0) {
  63.         if (count($n) > 2 * $m_length) {
  64.             $lhs = new $class();
  65.             $rhs = new $class();
  66.             $lhs->value = $n;
  67.             $rhs->value = $m;
  68.             list(, $temp) = $lhs->divide($rhs);
  69.             return $temp->value;
  70.         }
  71.  
  72.         // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  73.         if ($m_length < 5) {
  74.             return self::regularBarrett($n, $m, $class);
  75.         }
  76.         // n = 2 * m.length
  77.  
  78.         if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
  79.             $key = count($cache[self::VARIABLE]);
  80.             $cache[self::VARIABLE][] = $m;
  81.  
  82.             $lhs = new $class();
  83.             $lhs_value = &$lhs->value;
  84.             $lhs_value = self::array_repeat(0, $m_length + ($m_length >> 1));
  85.             $lhs_value[] = 1;
  86.             $rhs = new $class();
  87.             $rhs->value = $m;
  88.  
  89.             list($u, $m1) = $lhs->divide($rhs);
  90.             $u = $u->value;
  91.             $m1 = $m1->value;
  92.  
  93.             $cache[self::DATA][] = [
  94.                 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
  95.                 'm1' => $m1 // m.length
  96.             ];
  97.         } else {
  98.             extract($cache[self::DATA][$key]);
  99.         }
  100.  
  101.         $cutoff = $m_length + ($m_length >> 1);
  102.         $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
  103.         $msd = array_slice($n, $cutoff);    // m.length >> 1
  104.  
  105.         $lsd = self::trim($lsd);
  106.         $temp = $class::multiplyHelper($msd, false, $m1, false); // m.length + (m.length >> 1)
  107.         $n = $class::addHelper($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers)
  108.         //if ($m_length & 1) {
  109.         //    return self::regularBarrett($n[self::VALUE], $m, $class);
  110.         //}
  111.  
  112.         // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
  113.         $temp = array_slice($n[self::VALUE], $m_length - 1);
  114.         // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
  115.         // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
  116.         $temp = $class::multiplyHelper($temp, false, $u, false);
  117.         // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
  118.         // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
  119.         $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
  120.         // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
  121.         // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
  122.         $temp = $class::multiplyHelper($temp, false, $m, false);
  123.  
  124.         // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
  125.         // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
  126.         // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
  127.  
  128.         $result = $class::subtractHelper($n[self::VALUE], false, $temp[self::VALUE], false);
  129.  
  130.         while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
  131.             $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $m, false);
  132.         }
  133.  
  134.         return $result[self::VALUE];
  135.     }
  136.  
  137.     /**
  138.      * (Regular) Barrett Modular Reduction
  139.      *
  140.      * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
  141.      * is that this function does not fold the denominator into a smaller form.
  142.      *
  143.      * @param array $x
  144.      * @param array $n
  145.      * @param string $class
  146.      * @return array
  147.      */
  148.     private static function regularBarrett(array $x, array $n, $class)
  149.     {
  150.         static $cache = [
  151.             self::VARIABLE => [],
  152.             self::DATA => []
  153.         ];
  154.  
  155.         $n_length = count($n);
  156.  
  157.         if (count($x) > 2 * $n_length) {
  158.             $lhs = new $class();
  159.             $rhs = new $class();
  160.             $lhs->value = $x;
  161.             $rhs->value = $n;
  162.             list(, $temp) = $lhs->divide($rhs);
  163.             return $temp->value;
  164.         }
  165.  
  166.         if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
  167.             $key = count($cache[self::VARIABLE]);
  168.             $cache[self::VARIABLE][] = $n;
  169.             $lhs = new $class();
  170.             $lhs_value = &$lhs->value;
  171.             $lhs_value = self::array_repeat(0, 2 * $n_length);
  172.             $lhs_value[] = 1;
  173.             $rhs = new $class();
  174.             $rhs->value = $n;
  175.             list($temp, ) = $lhs->divide($rhs); // m.length
  176.             $cache[self::DATA][] = $temp->value;
  177.         }
  178.  
  179.         // 2 * m.length - (m.length - 1) = m.length + 1
  180.         $temp = array_slice($x, $n_length - 1);
  181.         // (m.length + 1) + m.length = 2 * m.length + 1
  182.         $temp = $class::multiplyHelper($temp, false, $cache[self::DATA][$key], false);
  183.         // (2 * m.length + 1) - (m.length - 1) = m.length + 2
  184.         $temp = array_slice($temp[self::VALUE], $n_length + 1);
  185.  
  186.         // m.length + 1
  187.         $result = array_slice($x, 0, $n_length + 1);
  188.         // m.length + 1
  189.         $temp = self::multiplyLower($temp, false, $n, false, $n_length + 1, $class);
  190.         // $temp == array_slice($class::regularMultiply($temp, false, $n, false)->value, 0, $n_length + 1)
  191.  
  192.         if (self::compareHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
  193.             $corrector_value = self::array_repeat(0, $n_length + 1);
  194.             $corrector_value[count($corrector_value)] = 1;
  195.             $result = $class::addHelper($result, false, $corrector_value, false);
  196.             $result = $result[self::VALUE];
  197.         }
  198.  
  199.         // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
  200.         $result = $class::subtractHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]);
  201.         while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
  202.             $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $n, false);
  203.         }
  204.  
  205.         return $result[self::VALUE];
  206.     }
  207.  
  208.     /**
  209.      * Performs long multiplication up to $stop digits
  210.      *
  211.      * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
  212.      *
  213.      * @see self::regularBarrett()
  214.      * @param array $x_value
  215.      * @param bool $x_negative
  216.      * @param array $y_value
  217.      * @param bool $y_negative
  218.      * @param int $stop
  219.      * @param string $class
  220.      * @return array
  221.      */
  222.     private static function multiplyLower(array $x_value, $x_negative, array $y_value, $y_negative, $stop, $class)
  223.     {
  224.         $x_length = count($x_value);
  225.         $y_length = count($y_value);
  226.  
  227.         if (!$x_length || !$y_length) { // a 0 is being multiplied
  228.             return [
  229.                 self::VALUE => [],
  230.                 self::SIGN => false
  231.             ];
  232.         }
  233.  
  234.         if ($x_length < $y_length) {
  235.             $temp = $x_value;
  236.             $x_value = $y_value;
  237.             $y_value = $temp;
  238.  
  239.             $x_length = count($x_value);
  240.             $y_length = count($y_value);
  241.         }
  242.  
  243.         $product_value = self::array_repeat(0, $x_length + $y_length);
  244.  
  245.         // the following for loop could be removed if the for loop following it
  246.         // (the one with nested for loops) initially set $i to 0, but
  247.         // doing so would also make the result in one set of unnecessary adds,
  248.         // since on the outermost loops first pass, $product->value[$k] is going
  249.         // to always be 0
  250.  
  251.         $carry = 0;
  252.  
  253.         for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
  254.             $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
  255.             $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  256.             $product_value[$j] = (int) ($temp - $class::BASE_FULL * $carry);
  257.         }
  258.  
  259.         if ($j < $stop) {
  260.             $product_value[$j] = $carry;
  261.         }
  262.  
  263.         // the above for loop is what the previous comment was talking about.  the
  264.         // following for loop is the "one with nested for loops"
  265.  
  266.         for ($i = 1; $i < $y_length; ++$i) {
  267.             $carry = 0;
  268.  
  269.             for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
  270.                 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  271.                 $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  272.                 $product_value[$k] = (int) ($temp - $class::BASE_FULL * $carry);
  273.             }
  274.  
  275.             if ($k < $stop) {
  276.                 $product_value[$k] = $carry;
  277.             }
  278.         }
  279.  
  280.         return [
  281.             self::VALUE => self::trim($product_value),
  282.             self::SIGN => $x_negative != $y_negative
  283.         ];
  284.     }
  285. }
  286.