Barrett.php — JetBackup – Backup, Restore & Migrate 3.1.23.3

backup / src / JetBackup / 3rdparty / phpseclib3 / Math / BigInteger / Engines / BCMath / Reductions / Barrett.php

backup / src / JetBackup / 3rdparty / phpseclib3 / Math / BigInteger / Engines / BCMath / Reductions Last commit date

.htaccess 1 year ago Barrett.php 1 year ago EvalBarrett.php 1 year ago index.html 1 year ago web.config 1 year ago

Barrett.php

180 lines

1	<?php
2
3	/**
4	* BCMath 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	declare(strict_types=1);
15
16	namespace phpseclib3\Math\BigInteger\Engines\BCMath\Reductions;
17
18	use phpseclib3\Math\BigInteger\Engines\BCMath\Base;
19
20	/**
21	* PHP Barrett Modular Exponentiation Engine
22	*
23	* @author Jim Wigginton <terrafrost@php.net>
24	*/
25	abstract class Barrett extends Base
26	{
27	/**
28	* Cache constants
29	*
30	* $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
31	*/
32	public const VARIABLE = 0;
33	/**
34	* $cache[self::DATA] contains the cached data.
35	*/
36	public const DATA = 1;
37
38	/**
39	* Barrett Modular Reduction
40	*
41	* See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
42	* {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly,
43	* so as not to require negative numbers (initially, this script didn't support negative numbers).
44	*
45	* Employs "folding", as described at
46	* {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from
47	* 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."
48	*
49	* Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
50	* usable on account of (1) its not using reasonable radix points as discussed in
51	* {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
52	* radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that
53	* (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
54	* comments for details.
55	*/
56	protected static function reduce(string $n, string $m): string
57	{
58	static $cache = [
59	self::VARIABLE => [],
60	self::DATA => [],
61	];
62
63	$m_length = strlen($m);
64
65	if (strlen($n) > 2 * $m_length) {
66	return bcmod($n, $m);
67	}
68
69	// if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
70	if ($m_length < 5) {
71	return self::regularBarrett($n, $m);
72	}
73	// n = 2 * m.length
74
75	if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
76	$key = count($cache[self::VARIABLE]);
77	$cache[self::VARIABLE][] = $m;
78
79	$lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1));
80	$u = bcdiv($lhs, $m, 0);
81	$m1 = bcsub($lhs, bcmul($u, $m));
82
83	$cache[self::DATA][] = [
84	'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
85	'm1' => $m1, // m.length
86	];
87	} else {
88	extract($cache[self::DATA][$key]);
89	}
90
91	$cutoff = $m_length + ($m_length >> 1);
92
93	$lsd = substr($n, -$cutoff);
94	$msd = substr($n, 0, -$cutoff);
95
96	$temp = bcmul($msd, $m1); // m.length + (m.length >> 1)
97	$n = bcadd($lsd, $temp); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers)
98	//if ($m_length & 1) {
99	// return self::regularBarrett($n, $m);
100	//}
101
102	// (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
103	$temp = substr($n, 0, -$m_length + 1);
104	// if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
105	// if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
106	$temp = bcmul($temp, $u);
107	// if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
108	// if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
109	$temp = substr($temp, 0, -($m_length >> 1) - 1);
110	// if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
111	// if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
112	$temp = bcmul($temp, $m);
113
114	// at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
115	// number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
116	// following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
117
118	$result = bcsub($n, $temp);
119
120	//if (bccomp($result, '0') < 0) {
121	if ($result[0] == '-') {
122	$temp = '1' . str_repeat('0', $m_length + 1);
123	$result = bcadd($result, $temp);
124	}
125
126	while (bccomp($result, $m) >= 0) {
127	$result = bcsub($result, $m);
128	}
129
130	return $result;
131	}
132
133	/**
134	* (Regular) Barrett Modular Reduction
135	*
136	* For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this
137	* is that this function does not fold the denominator into a smaller form.
138	*/
139	private static function regularBarrett(string $x, string $n): string
140	{
141	static $cache = [
142	self::VARIABLE => [],
143	self::DATA => [],
144	];
145
146	$n_length = strlen($n);
147
148	if (strlen($x) > 2 * $n_length) {
149	return bcmod($x, $n);
150	}
151
152	if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
153	$key = count($cache[self::VARIABLE]);
154	$cache[self::VARIABLE][] = $n;
155	$lhs = '1' . str_repeat('0', 2 * $n_length);
156	$cache[self::DATA][] = bcdiv($lhs, $n, 0);
157	}
158
159	$temp = substr($x, 0, -$n_length + 1);
160	$temp = bcmul($temp, $cache[self::DATA][$key]);
161	$temp = substr($temp, 0, -$n_length - 1);
162
163	$r1 = substr($x, -$n_length - 1);
164	$r2 = substr(bcmul($temp, $n), -$n_length - 1);
165	$result = bcsub($r1, $r2);
166
167	//if (bccomp($result, '0') < 0) {
168	if ($result[0] == '-') {
169	$q = '1' . str_repeat('0', $n_length + 1);
170	$result = bcadd($result, $q);
171	}
172
173	while (bccomp($result, $n) >= 0) {
174	$result = bcsub($result, $n);
175	}
176
177	return $result;
178	}
179	}
180