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