bigint.php 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369
  1. <?php
  2. /**********************************************************\
  3. | |
  4. | The implementation of PHPRPC Protocol 3.0 |
  5. | |
  6. | bigint.php |
  7. | |
  8. | Release 3.0.1 |
  9. | Copyright by Team-PHPRPC |
  10. | |
  11. | WebSite: http://www.phprpc.org/ |
  12. | http://www.phprpc.net/ |
  13. | http://www.phprpc.com/ |
  14. | http://sourceforge.net/projects/php-rpc/ |
  15. | |
  16. | Authors: Ma Bingyao <andot@ujn.edu.cn> |
  17. | |
  18. | This file may be distributed and/or modified under the |
  19. | terms of the GNU General Public License (GPL) version |
  20. | 2.0 as published by the Free Software Foundation and |
  21. | appearing in the included file LICENSE. |
  22. | |
  23. \**********************************************************/
  24. /* Big integer expansion library.
  25. *
  26. * Copyright: Ma Bingyao <andot@ujn.edu.cn>
  27. * mgccl <mgcclx@gmail.com>
  28. * Version: 3.0.1
  29. * LastModified: Apr 12, 2010
  30. * This library is free. You can redistribute it and/or modify it under GPL.
  31. */
  32. if (extension_loaded('gmp')) {
  33. function bigint_dec2num($dec) {
  34. return gmp_init($dec);
  35. }
  36. function bigint_num2dec($num) {
  37. return gmp_strval($num);
  38. }
  39. function bigint_str2num($str) {
  40. return gmp_init("0x".bin2hex($str));
  41. }
  42. function bigint_num2str($num) {
  43. $str = gmp_strval($num, 16);
  44. $len = strlen($str);
  45. if ($len % 2 == 1) {
  46. $str = '0'.$str;
  47. }
  48. return pack("H*", $str);
  49. }
  50. function bigint_random($n, $s) {
  51. $result = gmp_init(0);
  52. for ($i = 0; $i < $n; $i++) {
  53. if (mt_rand(0, 1)) {
  54. gmp_setbit($result, $i);
  55. }
  56. }
  57. if ($s) {
  58. gmp_setbit($result, $n - 1);
  59. }
  60. return $result;
  61. }
  62. function bigint_powmod($x, $y, $m) {
  63. return gmp_powm($x, $y, $m);
  64. }
  65. }
  66. else if (extension_loaded('big_int')) {
  67. function bigint_dec2num($dec) {
  68. return bi_from_str($dec);
  69. }
  70. function bigint_num2dec($num) {
  71. return bi_to_str($num);
  72. }
  73. function bigint_str2num($str) {
  74. return bi_from_str(bin2hex($str), 16);
  75. }
  76. function bigint_num2str($num) {
  77. $str = bi_to_str($num, 16);
  78. $len = strlen($str);
  79. if ($len % 2 == 1) {
  80. $str = '0'.$str;
  81. }
  82. return pack("H*", $str);
  83. }
  84. function bigint_random($n, $s) {
  85. $result = bi_rand($n);
  86. if ($s) {
  87. $result = bi_set_bit($result, $n - 1);
  88. }
  89. return $result;
  90. }
  91. function bigint_powmod($x, $y, $m) {
  92. return bi_powmod($x, $y, $m);
  93. }
  94. }
  95. else if (extension_loaded('bcmath')) {
  96. function bigint_dec2num($dec) {
  97. return $dec;
  98. }
  99. function bigint_num2dec($num) {
  100. return $num;
  101. }
  102. function bigint_str2num($str) {
  103. bcscale(0);
  104. $len = strlen($str);
  105. $result = '0';
  106. $m = '1';
  107. for ($i = 0; $i < $len; $i++) {
  108. $result = bcadd(bcmul($m, ord($str{$len - $i - 1})), $result);
  109. $m = bcmul($m, '256');
  110. }
  111. return $result;
  112. }
  113. function bigint_num2str($num) {
  114. bcscale(0);
  115. $str = "";
  116. while (bccomp($num, '0') == 1) {
  117. $str = chr(bcmod($num, '256')) . $str;
  118. $num = bcdiv($num, '256');
  119. }
  120. return $str;
  121. }
  122. // author of bcmath bigint_random: mgccl <mgcclx@gmail.com>
  123. function bigint_pow($b, $e) {
  124. if ($b == 2) {
  125. $a[96] = '79228162514264337593543950336';
  126. $a[128] = '340282366920938463463374607431768211456';
  127. $a[160] = '1461501637330902918203684832716283019655932542976';
  128. $a[192] = '6277101735386680763835789423207666416102355444464034512896';
  129. $a[256] = '115792089237316195423570985008687907853269984665640564039457584007913129639936';
  130. $a[512] = '13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096';
  131. $a[768] = '1552518092300708935148979488462502555256886017116696611139052038026050952686376886330878408828646477950487730697131073206171580044114814391444287275041181139204454976020849905550265285631598444825262999193716468750892846853816057856';
  132. $a[1024] = '179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216';
  133. $a[1356] = '1572802244866018108182967249994981337399178505432223228293716677435703277129801955281491139254988030713172834803458459525011536776047399098682525970017006610187370020027540826048617586909475175880278263391147764612823746132583281588112028234096933800670620569966257212339315820309710495898777306979706509398705741430192541287726011814541176060679505247297118998085067003005943214893171428950699778511718055936';
  134. $a[2048] = '32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656';
  135. $a[3072] = '5809605995369958062859502533304574370686975176362895236661486152287203730997110225737336044533118407251326157754980517443990529594540047121662885672187032401032111639706440498844049850989051627200244765807041812394729680540024104827976584369381522292361208779044769892743225751738076979568811309579125511333093243519553784816306381580161860200247492568448150242515304449577187604136428738580990172551573934146255830366405915000869643732053218566832545291107903722831634138599586406690325959725187447169059540805012310209639011750748760017095360734234945757416272994856013308616958529958304677637019181594088528345061285863898271763457294883546638879554311615446446330199254382340016292057090751175533888161918987295591531536698701292267685465517437915790823154844634780260102891718032495396075041899485513811126977307478969074857043710716150121315922024556759241239013152919710956468406379442914941614357107914462567329693696';
  136. $a[4096] = '1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190336';
  137. $a[8192] = '1090748135619415929462984244733782862448264161996232692431832786189721331849119295216264234525201987223957291796157025273109870820177184063610979765077554799078906298842192989538609825228048205159696851613591638196771886542609324560121290553901886301017900252535799917200010079600026535836800905297805880952350501630195475653911005312364560014847426035293551245843928918752768696279344088055617515694349945406677825140814900616105920256438504578013326493565836047242407382442812245131517757519164899226365743722432277368075027627883045206501792761700945699168497257879683851737049996900961120515655050115561271491492515342105748966629547032786321505730828430221664970324396138635251626409516168005427623435996308921691446181187406395310665404885739434832877428167407495370993511868756359970390117021823616749458620969857006263612082706715408157066575137281027022310927564910276759160520878304632411049364568754920967322982459184763427383790272448438018526977764941072715611580434690827459339991961414242741410599117426060556483763756314527611362658628383368621157993638020878537675545336789915694234433955666315070087213535470255670312004130725495834508357439653828936077080978550578912967907352780054935621561090795845172954115972927479877527738560008204118558930004777748727761853813510493840581861598652211605960308356405941821189714037868726219481498727603653616298856174822413033485438785324024751419417183012281078209729303537372804574372095228703622776363945290869806258422355148507571039619387449629866808188769662815778153079393179093143648340761738581819563002994422790754955061288818308430079648693232179158765918035565216157115402992120276155607873107937477466841528362987708699450152031231862594203085693838944657061346236704234026821102958954951197087076546186622796294536451620756509351018906023773821539532776208676978589731966330308893304665169436185078350641568336944530051437491311298834367265238595404904273455928723949525227184617404367854754610474377019768025576605881038077270707717942221977090385438585844095492116099852538903974655703943973086090930596963360767529964938414598185705963754561497355827813623833288906309004288017321424808663962671333528009232758350873059614118723781422101460198615747386855096896089189180441339558524822867541113212638793675567650340362970031930023397828465318547238244232028015189689660418822976000815437610652254270163595650875433851147123214227266605403581781469090806576468950587661997186505665475715792896';
  138. return (isset($a[$e]) ? $a[$e] : bcpow(2, $e));
  139. }
  140. return bcpow($b, $e);
  141. }
  142. function bigint_random($n, $s) {
  143. bcscale(0);
  144. $t = bigint_pow(2, $n);
  145. if ($s == 1) {
  146. $m = bcdiv($t, 2);
  147. $t = bcsub($m, 1);
  148. }
  149. else {
  150. $m = 0;
  151. $t = bcsub($t, 1);
  152. }
  153. $l = strlen($t);
  154. $n = (int) ($l / 9) + 1;
  155. $r = '';
  156. while($n) {
  157. $r .= substr('000000000' . mt_rand(0, 999999999), -9);
  158. --$n;
  159. }
  160. $r = substr($r, 0, $l);
  161. while (bccomp($r, $t) == 1) $r = substr($r, 1, $l) . mt_rand(0, 9);
  162. return bcadd($r, $m);
  163. }
  164. if (!function_exists('bcpowmod')) {
  165. function bcpowmod($x, $y, $modulus, $scale = 0) {
  166. $t = '1';
  167. while (bccomp($y, '0')) {
  168. if (bccomp(bcmod($y, '2'), '0')) {
  169. $t = bcmod(bcmul($t, $x), $modulus);
  170. $y = bcsub($y, '1');
  171. }
  172. $x = bcmod(bcmul($x, $x), $modulus);
  173. $y = bcdiv($y, '2');
  174. }
  175. return $t;
  176. }
  177. }
  178. function bigint_powmod($x, $y, $m) {
  179. return bcpowmod($x, $y, $m);
  180. }
  181. }
  182. else {
  183. function bigint_mul($a, $b) {
  184. $n = count($a);
  185. $m = count($b);
  186. $nm = $n + $m;
  187. $c = array_fill(0, $nm, 0);
  188. for ($i = 0; $i < $n; $i++) {
  189. for ($j = 0; $j < $m; $j++) {
  190. $c[$i + $j] += $a[$i] * $b[$j];
  191. $c[$i + $j + 1] += ($c[$i + $j] >> 15) & 0x7fff;
  192. $c[$i + $j] &= 0x7fff;
  193. }
  194. }
  195. return $c;
  196. }
  197. function bigint_div($a, $b, $is_mod = 0) {
  198. $n = count($a);
  199. $m = count($b);
  200. $c = array();
  201. $d = floor(0x8000 / ($b[$m - 1] + 1));
  202. $a = bigint_mul($a, array($d));
  203. $b = bigint_mul($b, array($d));
  204. for ($j = $n - $m; $j >= 0; $j--) {
  205. $tmp = $a[$j + $m] * 0x8000 + $a[$j + $m - 1];
  206. $rr = $tmp % $b[$m - 1];
  207. $qq = round(($tmp - $rr) / $b[$m - 1]);
  208. if (($qq == 0x8000) || (($m > 1) && ($qq * $b[$m - 2] > 0x8000 * $rr + $a[$j + $m - 2]))) {
  209. $qq--;
  210. $rr += $b[$m - 1];
  211. if (($rr < 0x8000) && ($qq * $b[$m - 2] > 0x8000 * $rr + $a[$j + $m - 2])) $qq--;
  212. }
  213. for ($i = 0; $i < $m; $i++) {
  214. $tmp = $i + $j;
  215. $a[$tmp] -= $b[$i] * $qq;
  216. $a[$tmp + 1] += floor($a[$tmp] / 0x8000);
  217. $a[$tmp] &= 0x7fff;
  218. }
  219. $c[$j] = $qq;
  220. if ($a[$tmp + 1] < 0) {
  221. $c[$j]--;
  222. for ($i = 0; $i < $m; $i++) {
  223. $tmp = $i + $j;
  224. $a[$tmp] += $b[$i];
  225. if ($a[$tmp] > 0x7fff) {
  226. $a[$tmp + 1]++;
  227. $a[$tmp] &= 0x7fff;
  228. }
  229. }
  230. }
  231. }
  232. if (!$is_mod) return $c;
  233. $b = array();
  234. for ($i = 0; $i < $m; $i++) $b[$i] = $a[$i];
  235. return bigint_div($b, array($d));
  236. }
  237. function bigint_zerofill($str, $num) {
  238. return str_pad($str, $num, '0', STR_PAD_LEFT);
  239. }
  240. function bigint_dec2num($dec) {
  241. $n = strlen($dec);
  242. $a = array(0);
  243. $n += 4 - ($n % 4);
  244. $dec = bigint_zerofill($dec, $n);
  245. $n >>= 2;
  246. for ($i = 0; $i < $n; $i++) {
  247. $a = bigint_mul($a, array(10000));
  248. $a[0] += (int)substr($dec, 4 * $i, 4);
  249. $m = count($a);
  250. $j = 0;
  251. $a[$m] = 0;
  252. while ($j < $m && $a[$j] > 0x7fff) {
  253. $a[$j++] &= 0x7fff;
  254. $a[$j]++;
  255. }
  256. while ((count($a) > 1) && (!$a[count($a) - 1])) array_pop($a);
  257. }
  258. return $a;
  259. }
  260. function bigint_num2dec($num) {
  261. $n = count($num) << 1;
  262. $b = array();
  263. for ($i = 0; $i < $n; $i++) {
  264. $tmp = bigint_div($num, array(10000), 1);
  265. $b[$i] = bigint_zerofill($tmp[0], 4);
  266. $num = bigint_div($num, array(10000));
  267. }
  268. while ((count($b) > 1) && !(int)$b[count($b) - 1]) array_pop($b);
  269. $n = count($b) - 1;
  270. $b[$n] = (int)$b[$n];
  271. $b = join('', array_reverse($b));
  272. return $b;
  273. }
  274. function bigint_str2num($str) {
  275. $n = strlen($str);
  276. $n += 15 - ($n % 15);
  277. $str = str_pad($str, $n, chr(0), STR_PAD_LEFT);
  278. $j = 0;
  279. $result = array();
  280. for ($i = 0; $i < $n; $i++) {
  281. $result[$j++] = (ord($str{$i++}) << 7) | (ord($str{$i}) >> 1);
  282. $result[$j++] = ((ord($str{$i++}) & 0x01) << 14) | (ord($str{$i++}) << 6) | (ord($str{$i}) >> 2);
  283. $result[$j++] = ((ord($str{$i++}) & 0x03) << 13) | (ord($str{$i++}) << 5) | (ord($str{$i}) >> 3);
  284. $result[$j++] = ((ord($str{$i++}) & 0x07) << 12) | (ord($str{$i++}) << 4) | (ord($str{$i}) >> 4);
  285. $result[$j++] = ((ord($str{$i++}) & 0x0f) << 11) | (ord($str{$i++}) << 3) | (ord($str{$i}) >> 5);
  286. $result[$j++] = ((ord($str{$i++}) & 0x1f) << 10) | (ord($str{$i++}) << 2) | (ord($str{$i}) >> 6);
  287. $result[$j++] = ((ord($str{$i++}) & 0x3f) << 9) | (ord($str{$i++}) << 1) | (ord($str{$i}) >> 7);
  288. $result[$j++] = ((ord($str{$i++}) & 0x7f) << 8) | ord($str{$i});
  289. }
  290. $result = array_reverse($result);
  291. $i = count($result) - 1;
  292. while ($result[$i] == 0) {
  293. array_pop($result);
  294. $i--;
  295. }
  296. return $result;
  297. }
  298. function bigint_num2str($num) {
  299. ksort($num, SORT_NUMERIC);
  300. $n = count($num);
  301. $n += 8 - ($n % 8);
  302. $num = array_reverse(array_pad($num, $n, 0));
  303. $s = '';
  304. for ($i = 0; $i < $n; $i++) {
  305. $s .= chr($num[$i] >> 7);
  306. $s .= chr((($num[$i++] & 0x7f) << 1) | ($num[$i] >> 14));
  307. $s .= chr(($num[$i] >> 6) & 0xff);
  308. $s .= chr((($num[$i++] & 0x3f) << 2) | ($num[$i] >> 13));
  309. $s .= chr(($num[$i] >> 5) & 0xff);
  310. $s .= chr((($num[$i++] & 0x1f) << 3) | ($num[$i] >> 12));
  311. $s .= chr(($num[$i] >> 4) & 0xff);
  312. $s .= chr((($num[$i++] & 0x0f) << 4) | ($num[$i] >> 11));
  313. $s .= chr(($num[$i] >> 3) & 0xff);
  314. $s .= chr((($num[$i++] & 0x07) << 5) | ($num[$i] >> 10));
  315. $s .= chr(($num[$i] >> 2) & 0xff);
  316. $s .= chr((($num[$i++] & 0x03) << 6) | ($num[$i] >> 9));
  317. $s .= chr(($num[$i] >> 1) & 0xff);
  318. $s .= chr((($num[$i++] & 0x01) << 7) | ($num[$i] >> 8));
  319. $s .= chr($num[$i] & 0xff);
  320. }
  321. return ltrim($s, chr(0));
  322. }
  323. function bigint_random($n, $s) {
  324. $lowBitMasks = array(0x0000, 0x0001, 0x0003, 0x0007,
  325. 0x000f, 0x001f, 0x003f, 0x007f,
  326. 0x00ff, 0x01ff, 0x03ff, 0x07ff,
  327. 0x0fff, 0x1fff, 0x3fff);
  328. $r = $n % 15;
  329. $q = floor($n / 15);
  330. $result = array();
  331. for ($i = 0; $i < $q; $i++) {
  332. $result[$i] = mt_rand(0, 0x7fff);
  333. }
  334. if ($r != 0) {
  335. $result[$q] = mt_rand(0, $lowBitMasks[$r]);
  336. if ($s) {
  337. $result[$q] |= 1 << ($r - 1);
  338. }
  339. }
  340. else if ($s) {
  341. $result[$q - 1] |= 0x4000;
  342. }
  343. return $result;
  344. }
  345. function bigint_powmod($x, $y, $m) {
  346. $n = count($y);
  347. $p = array(1);
  348. for ($i = 0; $i < $n - 1; $i++) {
  349. $tmp = $y[$i];
  350. for ($j = 0; $j < 0xf; $j++) {
  351. if ($tmp & 1) $p = bigint_div(bigint_mul($p, $x), $m, 1);
  352. $tmp >>= 1;
  353. $x = bigint_div(bigint_mul($x, $x), $m, 1);
  354. }
  355. }
  356. $tmp = $y[$i];
  357. while ($tmp) {
  358. if ($tmp & 1) $p = bigint_div(bigint_mul($p, $x), $m, 1);
  359. $tmp >>= 1;
  360. $x = bigint_div(bigint_mul($x, $x), $m, 1);
  361. }
  362. return $p;
  363. }
  364. }
  365. ?>