BigInteger.php 126 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758
  1. <?php
  2. /**
  3. * Pure-PHP arbitrary precision integer arithmetic library.
  4. *
  5. * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
  6. * and an internal implementation, otherwise.
  7. *
  8. * PHP versions 4 and 5
  9. *
  10. * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
  11. * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
  12. *
  13. * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
  14. * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
  15. * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
  16. * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
  17. * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
  18. * which only supports integers. Although this fact will slow this library down, the fact that such a high
  19. * base is being used should more than compensate.
  20. *
  21. * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie.
  22. * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
  23. *
  24. * Useful resources are as follows:
  25. *
  26. * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
  27. * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
  28. * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
  29. *
  30. * Here's an example of how to use this library:
  31. * <code>
  32. * <?php
  33. * include 'Math/BigInteger.php';
  34. *
  35. * $a = new Math_BigInteger(2);
  36. * $b = new Math_BigInteger(3);
  37. *
  38. * $c = $a->add($b);
  39. *
  40. * echo $c->toString(); // outputs 5
  41. * ?>
  42. * </code>
  43. *
  44. * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy
  45. * of this software and associated documentation files (the "Software"), to deal
  46. * in the Software without restriction, including without limitation the rights
  47. * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  48. * copies of the Software, and to permit persons to whom the Software is
  49. * furnished to do so, subject to the following conditions:
  50. *
  51. * The above copyright notice and this permission notice shall be included in
  52. * all copies or substantial portions of the Software.
  53. *
  54. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  55. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  56. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  57. * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  58. * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  59. * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  60. * THE SOFTWARE.
  61. *
  62. * @category Math
  63. * @package Math_BigInteger
  64. * @author Jim Wigginton <terrafrost@php.net>
  65. * @copyright 2006 Jim Wigginton
  66. * @license http://www.opensource.org/licenses/mit-license.html MIT License
  67. * @link http://pear.php.net/package/Math_BigInteger
  68. */
  69. /**#@+
  70. * Reduction constants
  71. *
  72. * @access private
  73. * @see Math_BigInteger::_reduce()
  74. */
  75. /**
  76. * @see Math_BigInteger::_montgomery()
  77. * @see Math_BigInteger::_prepMontgomery()
  78. */
  79. define('MATH_BIGINTEGER_MONTGOMERY', 0);
  80. /**
  81. * @see Math_BigInteger::_barrett()
  82. */
  83. define('MATH_BIGINTEGER_BARRETT', 1);
  84. /**
  85. * @see Math_BigInteger::_mod2()
  86. */
  87. define('MATH_BIGINTEGER_POWEROF2', 2);
  88. /**
  89. * @see Math_BigInteger::_remainder()
  90. */
  91. define('MATH_BIGINTEGER_CLASSIC', 3);
  92. /**
  93. * @see Math_BigInteger::__clone()
  94. */
  95. define('MATH_BIGINTEGER_NONE', 4);
  96. /**#@-*/
  97. /**#@+
  98. * Array constants
  99. *
  100. * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
  101. * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
  102. *
  103. * @access private
  104. */
  105. /**
  106. * $result[MATH_BIGINTEGER_VALUE] contains the value.
  107. */
  108. define('MATH_BIGINTEGER_VALUE', 0);
  109. /**
  110. * $result[MATH_BIGINTEGER_SIGN] contains the sign.
  111. */
  112. define('MATH_BIGINTEGER_SIGN', 1);
  113. /**#@-*/
  114. /**#@+
  115. * @access private
  116. * @see Math_BigInteger::_montgomery()
  117. * @see Math_BigInteger::_barrett()
  118. */
  119. /**
  120. * Cache constants
  121. *
  122. * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
  123. */
  124. define('MATH_BIGINTEGER_VARIABLE', 0);
  125. /**
  126. * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
  127. */
  128. define('MATH_BIGINTEGER_DATA', 1);
  129. /**#@-*/
  130. /**#@+
  131. * Mode constants.
  132. *
  133. * @access private
  134. * @see Math_BigInteger::Math_BigInteger()
  135. */
  136. /**
  137. * To use the pure-PHP implementation
  138. */
  139. define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
  140. /**
  141. * To use the BCMath library
  142. *
  143. * (if enabled; otherwise, the internal implementation will be used)
  144. */
  145. define('MATH_BIGINTEGER_MODE_BCMATH', 2);
  146. /**
  147. * To use the GMP library
  148. *
  149. * (if present; otherwise, either the BCMath or the internal implementation will be used)
  150. */
  151. define('MATH_BIGINTEGER_MODE_GMP', 3);
  152. /**#@-*/
  153. /**
  154. * Karatsuba Cutoff
  155. *
  156. * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
  157. *
  158. * @access private
  159. */
  160. define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
  161. /**
  162. * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
  163. * numbers.
  164. *
  165. * @package Math_BigInteger
  166. * @author Jim Wigginton <terrafrost@php.net>
  167. * @access public
  168. */
  169. class Math_BigInteger
  170. {
  171. /**
  172. * Holds the BigInteger's value.
  173. *
  174. * @var Array
  175. * @access private
  176. */
  177. var $value;
  178. /**
  179. * Holds the BigInteger's magnitude.
  180. *
  181. * @var Boolean
  182. * @access private
  183. */
  184. var $is_negative = false;
  185. /**
  186. * Random number generator function
  187. *
  188. * @see setRandomGenerator()
  189. * @access private
  190. */
  191. var $generator = 'mt_rand';
  192. /**
  193. * Precision
  194. *
  195. * @see setPrecision()
  196. * @access private
  197. */
  198. var $precision = -1;
  199. /**
  200. * Precision Bitmask
  201. *
  202. * @see setPrecision()
  203. * @access private
  204. */
  205. var $bitmask = false;
  206. /**
  207. * Mode independent value used for serialization.
  208. *
  209. * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
  210. * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
  211. * however, $this->hex is only calculated when $this->__sleep() is called.
  212. *
  213. * @see __sleep()
  214. * @see __wakeup()
  215. * @var String
  216. * @access private
  217. */
  218. var $hex;
  219. /**
  220. * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
  221. *
  222. * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
  223. * two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
  224. *
  225. * Here's an example:
  226. * <code>
  227. * <?php
  228. * include 'Math/BigInteger.php';
  229. *
  230. * $a = new Math_BigInteger('0x32', 16); // 50 in base-16
  231. *
  232. * echo $a->toString(); // outputs 50
  233. * ?>
  234. * </code>
  235. *
  236. * @param optional $x base-10 number or base-$base number if $base set.
  237. * @param optional integer $base
  238. * @return Math_BigInteger
  239. * @access public
  240. */
  241. function Math_BigInteger($x = 0, $base = 10)
  242. {
  243. if ( !defined('MATH_BIGINTEGER_MODE') ) {
  244. switch (true) {
  245. case extension_loaded('gmp'):
  246. define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
  247. break;
  248. case extension_loaded('bcmath'):
  249. define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
  250. break;
  251. default:
  252. define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
  253. }
  254. }
  255. if (function_exists('openssl_public_encrypt') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
  256. // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
  257. ob_start();
  258. @phpinfo();
  259. $content = ob_get_contents();
  260. ob_end_clean();
  261. preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
  262. $versions = array();
  263. if (!empty($matches[1])) {
  264. for ($i = 0; $i < count($matches[1]); $i++) {
  265. $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
  266. // Remove letter part in OpenSSL version
  267. if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
  268. $versions[$matches[1][$i]] = $fullVersion;
  269. } else {
  270. $versions[$matches[1][$i]] = $m[0];
  271. }
  272. }
  273. }
  274. // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
  275. switch (true) {
  276. case !isset($versions['Header']):
  277. case !isset($versions['Library']):
  278. case $versions['Header'] == $versions['Library']:
  279. define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
  280. break;
  281. default:
  282. define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
  283. }
  284. }
  285. if (!defined('PHP_INT_SIZE')) {
  286. define('PHP_INT_SIZE', 4);
  287. }
  288. if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
  289. switch (PHP_INT_SIZE) {
  290. case 8: // use 64-bit integers if int size is 8 bytes
  291. define('MATH_BIGINTEGER_BASE', 31);
  292. define('MATH_BIGINTEGER_BASE_FULL', 0x80000000);
  293. define('MATH_BIGINTEGER_MAX_DIGIT', 0x7FFFFFFF);
  294. define('MATH_BIGINTEGER_MSB', 0x40000000);
  295. // 10**9 is the closest we can get to 2**31 without passing it
  296. define('MATH_BIGINTEGER_MAX10', 1000000000);
  297. define('MATH_BIGINTEGER_MAX10_LEN', 9);
  298. // the largest digit that may be used in addition / subtraction
  299. define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62));
  300. break;
  301. //case 4: // use 64-bit floats if int size is 4 bytes
  302. default:
  303. define('MATH_BIGINTEGER_BASE', 26);
  304. define('MATH_BIGINTEGER_BASE_FULL', 0x4000000);
  305. define('MATH_BIGINTEGER_MAX_DIGIT', 0x3FFFFFF);
  306. define('MATH_BIGINTEGER_MSB', 0x2000000);
  307. // 10**7 is the closest to 2**26 without passing it
  308. define('MATH_BIGINTEGER_MAX10', 10000000);
  309. define('MATH_BIGINTEGER_MAX10_LEN', 7);
  310. // the largest digit that may be used in addition / subtraction
  311. // we do pow(2, 52) instead of using 4503599627370496 directly because some
  312. // PHP installations will truncate 4503599627370496.
  313. define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52));
  314. }
  315. }
  316. switch ( MATH_BIGINTEGER_MODE ) {
  317. case MATH_BIGINTEGER_MODE_GMP:
  318. switch (true) {
  319. case is_resource($x) && get_resource_type($x) == 'GMP integer':
  320. // PHP 5.6 switched GMP from using resources to objects
  321. case is_object($x) && get_class($x) == 'GMP':
  322. $this->value = $x;
  323. return;
  324. }
  325. $this->value = gmp_init(0);
  326. break;
  327. case MATH_BIGINTEGER_MODE_BCMATH:
  328. $this->value = '0';
  329. break;
  330. default:
  331. $this->value = array();
  332. }
  333. // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
  334. // '0' is the only value like this per http://php.net/empty
  335. if (empty($x) && (abs($base) != 256 || $x !== '0')) {
  336. return;
  337. }
  338. switch ($base) {
  339. case -256:
  340. if (ord($x[0]) & 0x80) {
  341. $x = ~$x;
  342. $this->is_negative = true;
  343. }
  344. case 256:
  345. switch ( MATH_BIGINTEGER_MODE ) {
  346. case MATH_BIGINTEGER_MODE_GMP:
  347. $sign = $this->is_negative ? '-' : '';
  348. $this->value = gmp_init($sign . '0x' . bin2hex($x));
  349. break;
  350. case MATH_BIGINTEGER_MODE_BCMATH:
  351. // round $len to the nearest 4 (thanks, DavidMJ!)
  352. $len = (strlen($x) + 3) & 0xFFFFFFFC;
  353. $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
  354. for ($i = 0; $i < $len; $i+= 4) {
  355. $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
  356. $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
  357. }
  358. if ($this->is_negative) {
  359. $this->value = '-' . $this->value;
  360. }
  361. break;
  362. // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
  363. default:
  364. while (strlen($x)) {
  365. $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
  366. }
  367. }
  368. if ($this->is_negative) {
  369. if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
  370. $this->is_negative = false;
  371. }
  372. $temp = $this->add(new Math_BigInteger('-1'));
  373. $this->value = $temp->value;
  374. }
  375. break;
  376. case 16:
  377. case -16:
  378. if ($base > 0 && $x[0] == '-') {
  379. $this->is_negative = true;
  380. $x = substr($x, 1);
  381. }
  382. $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
  383. $is_negative = false;
  384. if ($base < 0 && hexdec($x[0]) >= 8) {
  385. $this->is_negative = $is_negative = true;
  386. $x = bin2hex(~pack('H*', $x));
  387. }
  388. switch ( MATH_BIGINTEGER_MODE ) {
  389. case MATH_BIGINTEGER_MODE_GMP:
  390. $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
  391. $this->value = gmp_init($temp);
  392. $this->is_negative = false;
  393. break;
  394. case MATH_BIGINTEGER_MODE_BCMATH:
  395. $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
  396. $temp = new Math_BigInteger(pack('H*', $x), 256);
  397. $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
  398. $this->is_negative = false;
  399. break;
  400. default:
  401. $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
  402. $temp = new Math_BigInteger(pack('H*', $x), 256);
  403. $this->value = $temp->value;
  404. }
  405. if ($is_negative) {
  406. $temp = $this->add(new Math_BigInteger('-1'));
  407. $this->value = $temp->value;
  408. }
  409. break;
  410. case 10:
  411. case -10:
  412. // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
  413. // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
  414. // [^-0-9].*: find any non-numeric characters and then any characters that follow that
  415. $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
  416. switch ( MATH_BIGINTEGER_MODE ) {
  417. case MATH_BIGINTEGER_MODE_GMP:
  418. $this->value = gmp_init($x);
  419. break;
  420. case MATH_BIGINTEGER_MODE_BCMATH:
  421. // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
  422. // results then doing it on '-1' does (modInverse does $x[0])
  423. $this->value = $x === '-' ? '0' : (string) $x;
  424. break;
  425. default:
  426. $temp = new Math_BigInteger();
  427. $multiplier = new Math_BigInteger();
  428. $multiplier->value = array(MATH_BIGINTEGER_MAX10);
  429. if ($x[0] == '-') {
  430. $this->is_negative = true;
  431. $x = substr($x, 1);
  432. }
  433. $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
  434. while (strlen($x)) {
  435. $temp = $temp->multiply($multiplier);
  436. $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
  437. $x = substr($x, MATH_BIGINTEGER_MAX10_LEN);
  438. }
  439. $this->value = $temp->value;
  440. }
  441. break;
  442. case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
  443. case -2:
  444. if ($base > 0 && $x[0] == '-') {
  445. $this->is_negative = true;
  446. $x = substr($x, 1);
  447. }
  448. $x = preg_replace('#^([01]*).*#', '$1', $x);
  449. $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
  450. $str = '0x';
  451. while (strlen($x)) {
  452. $part = substr($x, 0, 4);
  453. $str.= dechex(bindec($part));
  454. $x = substr($x, 4);
  455. }
  456. if ($this->is_negative) {
  457. $str = '-' . $str;
  458. }
  459. $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16
  460. $this->value = $temp->value;
  461. $this->is_negative = $temp->is_negative;
  462. break;
  463. default:
  464. // base not supported, so we'll let $this == 0
  465. }
  466. }
  467. /**
  468. * Converts a BigInteger to a byte string (eg. base-256).
  469. *
  470. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  471. * saved as two's compliment.
  472. *
  473. * Here's an example:
  474. * <code>
  475. * <?php
  476. * include 'Math/BigInteger.php';
  477. *
  478. * $a = new Math_BigInteger('65');
  479. *
  480. * echo $a->toBytes(); // outputs chr(65)
  481. * ?>
  482. * </code>
  483. *
  484. * @param Boolean $twos_compliment
  485. * @return String
  486. * @access public
  487. * @internal Converts a base-2**26 number to base-2**8
  488. */
  489. function toBytes($twos_compliment = false)
  490. {
  491. if ($twos_compliment) {
  492. $comparison = $this->compare(new Math_BigInteger());
  493. if ($comparison == 0) {
  494. return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
  495. }
  496. $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
  497. $bytes = $temp->toBytes();
  498. if (empty($bytes)) { // eg. if the number we're trying to convert is -1
  499. $bytes = chr(0);
  500. }
  501. if (ord($bytes[0]) & 0x80) {
  502. $bytes = chr(0) . $bytes;
  503. }
  504. return $comparison < 0 ? ~$bytes : $bytes;
  505. }
  506. switch ( MATH_BIGINTEGER_MODE ) {
  507. case MATH_BIGINTEGER_MODE_GMP:
  508. if (gmp_cmp($this->value, gmp_init(0)) == 0) {
  509. return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
  510. }
  511. $temp = gmp_strval(gmp_abs($this->value), 16);
  512. $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp;
  513. $temp = pack('H*', $temp);
  514. return $this->precision > 0 ?
  515. substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
  516. ltrim($temp, chr(0));
  517. case MATH_BIGINTEGER_MODE_BCMATH:
  518. if ($this->value === '0') {
  519. return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
  520. }
  521. $value = '';
  522. $current = $this->value;
  523. if ($current[0] == '-') {
  524. $current = substr($current, 1);
  525. }
  526. while (bccomp($current, '0', 0) > 0) {
  527. $temp = bcmod($current, '16777216');
  528. $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
  529. $current = bcdiv($current, '16777216', 0);
  530. }
  531. return $this->precision > 0 ?
  532. substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
  533. ltrim($value, chr(0));
  534. }
  535. if (!count($this->value)) {
  536. return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
  537. }
  538. $result = $this->_int2bytes($this->value[count($this->value) - 1]);
  539. $temp = $this->copy();
  540. for ($i = count($temp->value) - 2; $i >= 0; --$i) {
  541. $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
  542. $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
  543. }
  544. return $this->precision > 0 ?
  545. str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
  546. $result;
  547. }
  548. /**
  549. * Converts a BigInteger to a hex string (eg. base-16)).
  550. *
  551. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  552. * saved as two's compliment.
  553. *
  554. * Here's an example:
  555. * <code>
  556. * <?php
  557. * include 'Math/BigInteger.php';
  558. *
  559. * $a = new Math_BigInteger('65');
  560. *
  561. * echo $a->toHex(); // outputs '41'
  562. * ?>
  563. * </code>
  564. *
  565. * @param Boolean $twos_compliment
  566. * @return String
  567. * @access public
  568. * @internal Converts a base-2**26 number to base-2**8
  569. */
  570. function toHex($twos_compliment = false)
  571. {
  572. return bin2hex($this->toBytes($twos_compliment));
  573. }
  574. /**
  575. * Converts a BigInteger to a bit string (eg. base-2).
  576. *
  577. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  578. * saved as two's compliment.
  579. *
  580. * Here's an example:
  581. * <code>
  582. * <?php
  583. * include 'Math/BigInteger.php';
  584. *
  585. * $a = new Math_BigInteger('65');
  586. *
  587. * echo $a->toBits(); // outputs '1000001'
  588. * ?>
  589. * </code>
  590. *
  591. * @param Boolean $twos_compliment
  592. * @return String
  593. * @access public
  594. * @internal Converts a base-2**26 number to base-2**2
  595. */
  596. function toBits($twos_compliment = false)
  597. {
  598. $hex = $this->toHex($twos_compliment);
  599. $bits = '';
  600. for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
  601. $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
  602. }
  603. if ($start) { // hexdec('') == 0
  604. $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
  605. }
  606. $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
  607. if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision <= 0) {
  608. return '0' . $result;
  609. }
  610. return $result;
  611. }
  612. /**
  613. * Converts a BigInteger to a base-10 number.
  614. *
  615. * Here's an example:
  616. * <code>
  617. * <?php
  618. * include 'Math/BigInteger.php';
  619. *
  620. * $a = new Math_BigInteger('50');
  621. *
  622. * echo $a->toString(); // outputs 50
  623. * ?>
  624. * </code>
  625. *
  626. * @return String
  627. * @access public
  628. * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
  629. */
  630. function toString()
  631. {
  632. switch ( MATH_BIGINTEGER_MODE ) {
  633. case MATH_BIGINTEGER_MODE_GMP:
  634. return gmp_strval($this->value);
  635. case MATH_BIGINTEGER_MODE_BCMATH:
  636. if ($this->value === '0') {
  637. return '0';
  638. }
  639. return ltrim($this->value, '0');
  640. }
  641. if (!count($this->value)) {
  642. return '0';
  643. }
  644. $temp = $this->copy();
  645. $temp->is_negative = false;
  646. $divisor = new Math_BigInteger();
  647. $divisor->value = array(MATH_BIGINTEGER_MAX10);
  648. $result = '';
  649. while (count($temp->value)) {
  650. list($temp, $mod) = $temp->divide($divisor);
  651. $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result;
  652. }
  653. $result = ltrim($result, '0');
  654. if (empty($result)) {
  655. $result = '0';
  656. }
  657. if ($this->is_negative) {
  658. $result = '-' . $result;
  659. }
  660. return $result;
  661. }
  662. /**
  663. * Copy an object
  664. *
  665. * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee
  666. * that all objects are passed by value, when appropriate. More information can be found here:
  667. *
  668. * {@link http://php.net/language.oop5.basic#51624}
  669. *
  670. * @access public
  671. * @see __clone()
  672. * @return Math_BigInteger
  673. */
  674. function copy()
  675. {
  676. $temp = new Math_BigInteger();
  677. $temp->value = $this->value;
  678. $temp->is_negative = $this->is_negative;
  679. $temp->generator = $this->generator;
  680. $temp->precision = $this->precision;
  681. $temp->bitmask = $this->bitmask;
  682. return $temp;
  683. }
  684. /**
  685. * __toString() magic method
  686. *
  687. * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call
  688. * toString().
  689. *
  690. * @access public
  691. * @internal Implemented per a suggestion by Techie-Michael - thanks!
  692. */
  693. function __toString()
  694. {
  695. return $this->toString();
  696. }
  697. /**
  698. * __clone() magic method
  699. *
  700. * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
  701. * directly in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
  702. * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5,
  703. * call Math_BigInteger::copy(), instead.
  704. *
  705. * @access public
  706. * @see copy()
  707. * @return Math_BigInteger
  708. */
  709. function __clone()
  710. {
  711. return $this->copy();
  712. }
  713. /**
  714. * __sleep() magic method
  715. *
  716. * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
  717. *
  718. * @see __wakeup()
  719. * @access public
  720. */
  721. function __sleep()
  722. {
  723. $this->hex = $this->toHex(true);
  724. $vars = array('hex');
  725. if ($this->generator != 'mt_rand') {
  726. $vars[] = 'generator';
  727. }
  728. if ($this->precision > 0) {
  729. $vars[] = 'precision';
  730. }
  731. return $vars;
  732. }
  733. /**
  734. * __wakeup() magic method
  735. *
  736. * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
  737. *
  738. * @see __sleep()
  739. * @access public
  740. */
  741. function __wakeup()
  742. {
  743. $temp = new Math_BigInteger($this->hex, -16);
  744. $this->value = $temp->value;
  745. $this->is_negative = $temp->is_negative;
  746. $this->setRandomGenerator($this->generator);
  747. if ($this->precision > 0) {
  748. // recalculate $this->bitmask
  749. $this->setPrecision($this->precision);
  750. }
  751. }
  752. /**
  753. * Adds two BigIntegers.
  754. *
  755. * Here's an example:
  756. * <code>
  757. * <?php
  758. * include 'Math/BigInteger.php';
  759. *
  760. * $a = new Math_BigInteger('10');
  761. * $b = new Math_BigInteger('20');
  762. *
  763. * $c = $a->add($b);
  764. *
  765. * echo $c->toString(); // outputs 30
  766. * ?>
  767. * </code>
  768. *
  769. * @param Math_BigInteger $y
  770. * @return Math_BigInteger
  771. * @access public
  772. * @internal Performs base-2**52 addition
  773. */
  774. function add($y)
  775. {
  776. switch ( MATH_BIGINTEGER_MODE ) {
  777. case MATH_BIGINTEGER_MODE_GMP:
  778. $temp = new Math_BigInteger();
  779. $temp->value = gmp_add($this->value, $y->value);
  780. return $this->_normalize($temp);
  781. case MATH_BIGINTEGER_MODE_BCMATH:
  782. $temp = new Math_BigInteger();
  783. $temp->value = bcadd($this->value, $y->value, 0);
  784. return $this->_normalize($temp);
  785. }
  786. $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
  787. $result = new Math_BigInteger();
  788. $result->value = $temp[MATH_BIGINTEGER_VALUE];
  789. $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  790. return $this->_normalize($result);
  791. }
  792. /**
  793. * Performs addition.
  794. *
  795. * @param Array $x_value
  796. * @param Boolean $x_negative
  797. * @param Array $y_value
  798. * @param Boolean $y_negative
  799. * @return Array
  800. * @access private
  801. */
  802. function _add($x_value, $x_negative, $y_value, $y_negative)
  803. {
  804. $x_size = count($x_value);
  805. $y_size = count($y_value);
  806. if ($x_size == 0) {
  807. return array(
  808. MATH_BIGINTEGER_VALUE => $y_value,
  809. MATH_BIGINTEGER_SIGN => $y_negative
  810. );
  811. } else if ($y_size == 0) {
  812. return array(
  813. MATH_BIGINTEGER_VALUE => $x_value,
  814. MATH_BIGINTEGER_SIGN => $x_negative
  815. );
  816. }
  817. // subtract, if appropriate
  818. if ( $x_negative != $y_negative ) {
  819. if ( $x_value == $y_value ) {
  820. return array(
  821. MATH_BIGINTEGER_VALUE => array(),
  822. MATH_BIGINTEGER_SIGN => false
  823. );
  824. }
  825. $temp = $this->_subtract($x_value, false, $y_value, false);
  826. $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
  827. $x_negative : $y_negative;
  828. return $temp;
  829. }
  830. if ($x_size < $y_size) {
  831. $size = $x_size;
  832. $value = $y_value;
  833. } else {
  834. $size = $y_size;
  835. $value = $x_value;
  836. }
  837. $value[count($value)] = 0; // just in case the carry adds an extra digit
  838. $carry = 0;
  839. for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
  840. $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
  841. $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  842. $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
  843. $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
  844. $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
  845. $value[$j] = $temp;
  846. }
  847. if ($j == $size) { // ie. if $y_size is odd
  848. $sum = $x_value[$i] + $y_value[$i] + $carry;
  849. $carry = $sum >= MATH_BIGINTEGER_BASE_FULL;
  850. $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
  851. ++$i; // ie. let $i = $j since we've just done $value[$i]
  852. }
  853. if ($carry) {
  854. for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
  855. $value[$i] = 0;
  856. }
  857. ++$value[$i];
  858. }
  859. return array(
  860. MATH_BIGINTEGER_VALUE => $this->_trim($value),
  861. MATH_BIGINTEGER_SIGN => $x_negative
  862. );
  863. }
  864. /**
  865. * Subtracts two BigIntegers.
  866. *
  867. * Here's an example:
  868. * <code>
  869. * <?php
  870. * include 'Math/BigInteger.php';
  871. *
  872. * $a = new Math_BigInteger('10');
  873. * $b = new Math_BigInteger('20');
  874. *
  875. * $c = $a->subtract($b);
  876. *
  877. * echo $c->toString(); // outputs -10
  878. * ?>
  879. * </code>
  880. *
  881. * @param Math_BigInteger $y
  882. * @return Math_BigInteger
  883. * @access public
  884. * @internal Performs base-2**52 subtraction
  885. */
  886. function subtract($y)
  887. {
  888. switch ( MATH_BIGINTEGER_MODE ) {
  889. case MATH_BIGINTEGER_MODE_GMP:
  890. $temp = new Math_BigInteger();
  891. $temp->value = gmp_sub($this->value, $y->value);
  892. return $this->_normalize($temp);
  893. case MATH_BIGINTEGER_MODE_BCMATH:
  894. $temp = new Math_BigInteger();
  895. $temp->value = bcsub($this->value, $y->value, 0);
  896. return $this->_normalize($temp);
  897. }
  898. $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
  899. $result = new Math_BigInteger();
  900. $result->value = $temp[MATH_BIGINTEGER_VALUE];
  901. $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  902. return $this->_normalize($result);
  903. }
  904. /**
  905. * Performs subtraction.
  906. *
  907. * @param Array $x_value
  908. * @param Boolean $x_negative
  909. * @param Array $y_value
  910. * @param Boolean $y_negative
  911. * @return Array
  912. * @access private
  913. */
  914. function _subtract($x_value, $x_negative, $y_value, $y_negative)
  915. {
  916. $x_size = count($x_value);
  917. $y_size = count($y_value);
  918. if ($x_size == 0) {
  919. return array(
  920. MATH_BIGINTEGER_VALUE => $y_value,
  921. MATH_BIGINTEGER_SIGN => !$y_negative
  922. );
  923. } else if ($y_size == 0) {
  924. return array(
  925. MATH_BIGINTEGER_VALUE => $x_value,
  926. MATH_BIGINTEGER_SIGN => $x_negative
  927. );
  928. }
  929. // add, if appropriate (ie. -$x - +$y or +$x - -$y)
  930. if ( $x_negative != $y_negative ) {
  931. $temp = $this->_add($x_value, false, $y_value, false);
  932. $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
  933. return $temp;
  934. }
  935. $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
  936. if ( !$diff ) {
  937. return array(
  938. MATH_BIGINTEGER_VALUE => array(),
  939. MATH_BIGINTEGER_SIGN => false
  940. );
  941. }
  942. // switch $x and $y around, if appropriate.
  943. if ( (!$x_negative && $diff < 0) || ($x_negative && $diff > 0) ) {
  944. $temp = $x_value;
  945. $x_value = $y_value;
  946. $y_value = $temp;
  947. $x_negative = !$x_negative;
  948. $x_size = count($x_value);
  949. $y_size = count($y_value);
  950. }
  951. // at this point, $x_value should be at least as big as - if not bigger than - $y_value
  952. $carry = 0;
  953. for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
  954. $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
  955. $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
  956. $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
  957. $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
  958. $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
  959. $x_value[$j] = $temp;
  960. }
  961. if ($j == $y_size) { // ie. if $y_size is odd
  962. $sum = $x_value[$i] - $y_value[$i] - $carry;
  963. $carry = $sum < 0;
  964. $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
  965. ++$i;
  966. }
  967. if ($carry) {
  968. for (; !$x_value[$i]; ++$i) {
  969. $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
  970. }
  971. --$x_value[$i];
  972. }
  973. return array(
  974. MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
  975. MATH_BIGINTEGER_SIGN => $x_negative
  976. );
  977. }
  978. /**
  979. * Multiplies two BigIntegers
  980. *
  981. * Here's an example:
  982. * <code>
  983. * <?php
  984. * include 'Math/BigInteger.php';
  985. *
  986. * $a = new Math_BigInteger('10');
  987. * $b = new Math_BigInteger('20');
  988. *
  989. * $c = $a->multiply($b);
  990. *
  991. * echo $c->toString(); // outputs 200
  992. * ?>
  993. * </code>
  994. *
  995. * @param Math_BigInteger $x
  996. * @return Math_BigInteger
  997. * @access public
  998. */
  999. function multiply($x)
  1000. {
  1001. switch ( MATH_BIGINTEGER_MODE ) {
  1002. case MATH_BIGINTEGER_MODE_GMP:
  1003. $temp = new Math_BigInteger();
  1004. $temp->value = gmp_mul($this->value, $x->value);
  1005. return $this->_normalize($temp);
  1006. case MATH_BIGINTEGER_MODE_BCMATH:
  1007. $temp = new Math_BigInteger();
  1008. $temp->value = bcmul($this->value, $x->value, 0);
  1009. return $this->_normalize($temp);
  1010. }
  1011. $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
  1012. $product = new Math_BigInteger();
  1013. $product->value = $temp[MATH_BIGINTEGER_VALUE];
  1014. $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  1015. return $this->_normalize($product);
  1016. }
  1017. /**
  1018. * Performs multiplication.
  1019. *
  1020. * @param Array $x_value
  1021. * @param Boolean $x_negative
  1022. * @param Array $y_value
  1023. * @param Boolean $y_negative
  1024. * @return Array
  1025. * @access private
  1026. */
  1027. function _multiply($x_value, $x_negative, $y_value, $y_negative)
  1028. {
  1029. //if ( $x_value == $y_value ) {
  1030. // return array(
  1031. // MATH_BIGINTEGER_VALUE => $this->_square($x_value),
  1032. // MATH_BIGINTEGER_SIGN => $x_sign != $y_value
  1033. // );
  1034. //}
  1035. $x_length = count($x_value);
  1036. $y_length = count($y_value);
  1037. if ( !$x_length || !$y_length ) { // a 0 is being multiplied
  1038. return array(
  1039. MATH_BIGINTEGER_VALUE => array(),
  1040. MATH_BIGINTEGER_SIGN => false
  1041. );
  1042. }
  1043. return array(
  1044. MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
  1045. $this->_trim($this->_regularMultiply($x_value, $y_value)) :
  1046. $this->_trim($this->_karatsuba($x_value, $y_value)),
  1047. MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
  1048. );
  1049. }
  1050. /**
  1051. * Performs long multiplication on two BigIntegers
  1052. *
  1053. * Modeled after 'multiply' in MutableBigInteger.java.
  1054. *
  1055. * @param Array $x_value
  1056. * @param Array $y_value
  1057. * @return Array
  1058. * @access private
  1059. */
  1060. function _regularMultiply($x_value, $y_value)
  1061. {
  1062. $x_length = count($x_value);
  1063. $y_length = count($y_value);
  1064. if ( !$x_length || !$y_length ) { // a 0 is being multiplied
  1065. return array();
  1066. }
  1067. if ( $x_length < $y_length ) {
  1068. $temp = $x_value;
  1069. $x_value = $y_value;
  1070. $y_value = $temp;
  1071. $x_length = count($x_value);
  1072. $y_length = count($y_value);
  1073. }
  1074. $product_value = $this->_array_repeat(0, $x_length + $y_length);
  1075. // the following for loop could be removed if the for loop following it
  1076. // (the one with nested for loops) initially set $i to 0, but
  1077. // doing so would also make the result in one set of unnecessary adds,
  1078. // since on the outermost loops first pass, $product->value[$k] is going
  1079. // to always be 0
  1080. $carry = 0;
  1081. for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
  1082. $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
  1083. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1084. $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1085. }
  1086. $product_value[$j] = $carry;
  1087. // the above for loop is what the previous comment was talking about. the
  1088. // following for loop is the "one with nested for loops"
  1089. for ($i = 1; $i < $y_length; ++$i) {
  1090. $carry = 0;
  1091. for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
  1092. $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  1093. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1094. $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1095. }
  1096. $product_value[$k] = $carry;
  1097. }
  1098. return $product_value;
  1099. }
  1100. /**
  1101. * Performs Karatsuba multiplication on two BigIntegers
  1102. *
  1103. * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1104. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
  1105. *
  1106. * @param Array $x_value
  1107. * @param Array $y_value
  1108. * @return Array
  1109. * @access private
  1110. */
  1111. function _karatsuba($x_value, $y_value)
  1112. {
  1113. $m = min(count($x_value) >> 1, count($y_value) >> 1);
  1114. if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  1115. return $this->_regularMultiply($x_value, $y_value);
  1116. }
  1117. $x1 = array_slice($x_value, $m);
  1118. $x0 = array_slice($x_value, 0, $m);
  1119. $y1 = array_slice($y_value, $m);
  1120. $y0 = array_slice($y_value, 0, $m);
  1121. $z2 = $this->_karatsuba($x1, $y1);
  1122. $z0 = $this->_karatsuba($x0, $y0);
  1123. $z1 = $this->_add($x1, false, $x0, false);
  1124. $temp = $this->_add($y1, false, $y0, false);
  1125. $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
  1126. $temp = $this->_add($z2, false, $z0, false);
  1127. $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
  1128. $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  1129. $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
  1130. $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1131. $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
  1132. return $xy[MATH_BIGINTEGER_VALUE];
  1133. }
  1134. /**
  1135. * Performs squaring
  1136. *
  1137. * @param Array $x
  1138. * @return Array
  1139. * @access private
  1140. */
  1141. function _square($x = false)
  1142. {
  1143. return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
  1144. $this->_trim($this->_baseSquare($x)) :
  1145. $this->_trim($this->_karatsubaSquare($x));
  1146. }
  1147. /**
  1148. * Performs traditional squaring on two BigIntegers
  1149. *
  1150. * Squaring can be done faster than multiplying a number by itself can be. See
  1151. * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
  1152. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
  1153. *
  1154. * @param Array $value
  1155. * @return Array
  1156. * @access private
  1157. */
  1158. function _baseSquare($value)
  1159. {
  1160. if ( empty($value) ) {
  1161. return array();
  1162. }
  1163. $square_value = $this->_array_repeat(0, 2 * count($value));
  1164. for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
  1165. $i2 = $i << 1;
  1166. $temp = $square_value[$i2] + $value[$i] * $value[$i];
  1167. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1168. $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1169. // note how we start from $i+1 instead of 0 as we do in multiplication.
  1170. for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
  1171. $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
  1172. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1173. $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1174. }
  1175. // the following line can yield values larger 2**15. at this point, PHP should switch
  1176. // over to floats.
  1177. $square_value[$i + $max_index + 1] = $carry;
  1178. }
  1179. return $square_value;
  1180. }
  1181. /**
  1182. * Performs Karatsuba "squaring" on two BigIntegers
  1183. *
  1184. * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1185. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
  1186. *
  1187. * @param Array $value
  1188. * @return Array
  1189. * @access private
  1190. */
  1191. function _karatsubaSquare($value)
  1192. {
  1193. $m = count($value) >> 1;
  1194. if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  1195. return $this->_baseSquare($value);
  1196. }
  1197. $x1 = array_slice($value, $m);
  1198. $x0 = array_slice($value, 0, $m);
  1199. $z2 = $this->_karatsubaSquare($x1);
  1200. $z0 = $this->_karatsubaSquare($x0);
  1201. $z1 = $this->_add($x1, false, $x0, false);
  1202. $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
  1203. $temp = $this->_add($z2, false, $z0, false);
  1204. $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
  1205. $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  1206. $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
  1207. $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1208. $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
  1209. return $xx[MATH_BIGINTEGER_VALUE];
  1210. }
  1211. /**
  1212. * Divides two BigIntegers.
  1213. *
  1214. * Returns an array whose first element contains the quotient and whose second element contains the
  1215. * "common residue". If the remainder would be positive, the "common residue" and the remainder are the
  1216. * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
  1217. * and the divisor (basically, the "common residue" is the first positive modulo).
  1218. *
  1219. * Here's an example:
  1220. * <code>
  1221. * <?php
  1222. * include 'Math/BigInteger.php';
  1223. *
  1224. * $a = new Math_BigInteger('10');
  1225. * $b = new Math_BigInteger('20');
  1226. *
  1227. * list($quotient, $remainder) = $a->divide($b);
  1228. *
  1229. * echo $quotient->toString(); // outputs 0
  1230. * echo "\r\n";
  1231. * echo $remainder->toString(); // outputs 10
  1232. * ?>
  1233. * </code>
  1234. *
  1235. * @param Math_BigInteger $y
  1236. * @return Array
  1237. * @access public
  1238. * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
  1239. */
  1240. function divide($y)
  1241. {
  1242. switch ( MATH_BIGINTEGER_MODE ) {
  1243. case MATH_BIGINTEGER_MODE_GMP:
  1244. $quotient = new Math_BigInteger();
  1245. $remainder = new Math_BigInteger();
  1246. list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
  1247. if (gmp_sign($remainder->value) < 0) {
  1248. $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
  1249. }
  1250. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1251. case MATH_BIGINTEGER_MODE_BCMATH:
  1252. $quotient = new Math_BigInteger();
  1253. $remainder = new Math_BigInteger();
  1254. $quotient->value = bcdiv($this->value, $y->value, 0);
  1255. $remainder->value = bcmod($this->value, $y->value);
  1256. if ($remainder->value[0] == '-') {
  1257. $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
  1258. }
  1259. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1260. }
  1261. if (count($y->value) == 1) {
  1262. list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
  1263. $quotient = new Math_BigInteger();
  1264. $remainder = new Math_BigInteger();
  1265. $quotient->value = $q;
  1266. $remainder->value = array($r);
  1267. $quotient->is_negative = $this->is_negative != $y->is_negative;
  1268. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1269. }
  1270. static $zero;
  1271. if ( !isset($zero) ) {
  1272. $zero = new Math_BigInteger();
  1273. }
  1274. $x = $this->copy();
  1275. $y = $y->copy();
  1276. $x_sign = $x->is_negative;
  1277. $y_sign = $y->is_negative;
  1278. $x->is_negative = $y->is_negative = false;
  1279. $diff = $x->compare($y);
  1280. if ( !$diff ) {
  1281. $temp = new Math_BigInteger();
  1282. $temp->value = array(1);
  1283. $temp->is_negative = $x_sign != $y_sign;
  1284. return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
  1285. }
  1286. if ( $diff < 0 ) {
  1287. // if $x is negative, "add" $y.
  1288. if ( $x_sign ) {
  1289. $x = $y->subtract($x);
  1290. }
  1291. return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
  1292. }
  1293. // normalize $x and $y as described in HAC 14.23 / 14.24
  1294. $msb = $y->value[count($y->value) - 1];
  1295. for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) {
  1296. $msb <<= 1;
  1297. }
  1298. $x->_lshift($shift);
  1299. $y->_lshift($shift);
  1300. $y_value = &$y->value;
  1301. $x_max = count($x->value) - 1;
  1302. $y_max = count($y->value) - 1;
  1303. $quotient = new Math_BigInteger();
  1304. $quotient_value = &$quotient->value;
  1305. $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
  1306. static $temp, $lhs, $rhs;
  1307. if (!isset($temp)) {
  1308. $temp = new Math_BigInteger();
  1309. $lhs = new Math_BigInteger();
  1310. $rhs = new Math_BigInteger();
  1311. }
  1312. $temp_value = &$temp->value;
  1313. $rhs_value = &$rhs->value;
  1314. // $temp = $y << ($x_max - $y_max-1) in base 2**26
  1315. $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
  1316. while ( $x->compare($temp) >= 0 ) {
  1317. // calculate the "common residue"
  1318. ++$quotient_value[$x_max - $y_max];
  1319. $x = $x->subtract($temp);
  1320. $x_max = count($x->value) - 1;
  1321. }
  1322. for ($i = $x_max; $i >= $y_max + 1; --$i) {
  1323. $x_value = &$x->value;
  1324. $x_window = array(
  1325. isset($x_value[$i]) ? $x_value[$i] : 0,
  1326. isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
  1327. isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
  1328. );
  1329. $y_window = array(
  1330. $y_value[$y_max],
  1331. ( $y_max > 0 ) ? $y_value[$y_max - 1] : 0
  1332. );
  1333. $q_index = $i - $y_max - 1;
  1334. if ($x_window[0] == $y_window[0]) {
  1335. $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
  1336. } else {
  1337. $quotient_value[$q_index] = $this->_safe_divide(
  1338. $x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1],
  1339. $y_window[0]
  1340. );
  1341. }
  1342. $temp_value = array($y_window[1], $y_window[0]);
  1343. $lhs->value = array($quotient_value[$q_index]);
  1344. $lhs = $lhs->multiply($temp);
  1345. $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
  1346. while ( $lhs->compare($rhs) > 0 ) {
  1347. --$quotient_value[$q_index];
  1348. $lhs->value = array($quotient_value[$q_index]);
  1349. $lhs = $lhs->multiply($temp);
  1350. }
  1351. $adjust = $this->_array_repeat(0, $q_index);
  1352. $temp_value = array($quotient_value[$q_index]);
  1353. $temp = $temp->multiply($y);
  1354. $temp_value = &$temp->value;
  1355. $temp_value = array_merge($adjust, $temp_value);
  1356. $x = $x->subtract($temp);
  1357. if ($x->compare($zero) < 0) {
  1358. $temp_value = array_merge($adjust, $y_value);
  1359. $x = $x->add($temp);
  1360. --$quotient_value[$q_index];
  1361. }
  1362. $x_max = count($x_value) - 1;
  1363. }
  1364. // unnormalize the remainder
  1365. $x->_rshift($shift);
  1366. $quotient->is_negative = $x_sign != $y_sign;
  1367. // calculate the "common residue", if appropriate
  1368. if ( $x_sign ) {
  1369. $y->_rshift($shift);
  1370. $x = $y->subtract($x);
  1371. }
  1372. return array($this->_normalize($quotient), $this->_normalize($x));
  1373. }
  1374. /**
  1375. * Divides a BigInteger by a regular integer
  1376. *
  1377. * abc / x = a00 / x + b0 / x + c / x
  1378. *
  1379. * @param Array $dividend
  1380. * @param Array $divisor
  1381. * @return Array
  1382. * @access private
  1383. */
  1384. function _divide_digit($dividend, $divisor)
  1385. {
  1386. $carry = 0;
  1387. $result = array();
  1388. for ($i = count($dividend) - 1; $i >= 0; --$i) {
  1389. $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i];
  1390. $result[$i] = $this->_safe_divide($temp, $divisor);
  1391. $carry = (int) ($temp - $divisor * $result[$i]);
  1392. }
  1393. return array($result, $carry);
  1394. }
  1395. /**
  1396. * Performs modular exponentiation.
  1397. *
  1398. * Here's an example:
  1399. * <code>
  1400. * <?php
  1401. * include 'Math/BigInteger.php';
  1402. *
  1403. * $a = new Math_BigInteger('10');
  1404. * $b = new Math_BigInteger('20');
  1405. * $c = new Math_BigInteger('30');
  1406. *
  1407. * $c = $a->modPow($b, $c);
  1408. *
  1409. * echo $c->toString(); // outputs 10
  1410. * ?>
  1411. * </code>
  1412. *
  1413. * @param Math_BigInteger $e
  1414. * @param Math_BigInteger $n
  1415. * @return Math_BigInteger
  1416. * @access public
  1417. * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
  1418. * and although the approach involving repeated squaring does vastly better, it, too, is impractical
  1419. * for our purposes. The reason being that division - by far the most complicated and time-consuming
  1420. * of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
  1421. *
  1422. * Modular reductions resolve this issue. Although an individual modular reduction takes more time
  1423. * then an individual division, when performed in succession (with the same modulo), they're a lot faster.
  1424. *
  1425. * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction,
  1426. * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the
  1427. * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
  1428. * the product of two odd numbers is odd), but what about when RSA isn't used?
  1429. *
  1430. * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a
  1431. * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the
  1432. * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however,
  1433. * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
  1434. * the other, a power of two - and recombine them, later. This is the method that this modPow function uses.
  1435. * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
  1436. */
  1437. function modPow($e, $n)
  1438. {
  1439. $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
  1440. if ($e->compare(new Math_BigInteger()) < 0) {
  1441. $e = $e->abs();
  1442. $temp = $this->modInverse($n);
  1443. if ($temp === false) {
  1444. return false;
  1445. }
  1446. return $this->_normalize($temp->modPow($e, $n));
  1447. }
  1448. if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) {
  1449. $temp = new Math_BigInteger();
  1450. $temp->value = gmp_powm($this->value, $e->value, $n->value);
  1451. return $this->_normalize($temp);
  1452. }
  1453. if ($this->compare(new Math_BigInteger()) < 0 || $this->compare($n) > 0) {
  1454. list(, $temp) = $this->divide($n);
  1455. return $temp->modPow($e, $n);
  1456. }
  1457. if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
  1458. $components = array(
  1459. 'modulus' => $n->toBytes(true),
  1460. 'publicExponent' => $e->toBytes(true)
  1461. );
  1462. $components = array(
  1463. 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
  1464. 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
  1465. );
  1466. $RSAPublicKey = pack('Ca*a*a*',
  1467. 48, $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
  1468. $components['modulus'], $components['publicExponent']
  1469. );
  1470. $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
  1471. $RSAPublicKey = chr(0) . $RSAPublicKey;
  1472. $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
  1473. $encapsulated = pack('Ca*a*',
  1474. 48, $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), $rsaOID . $RSAPublicKey
  1475. );
  1476. $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
  1477. chunk_split(base64_encode($encapsulated)) .
  1478. '-----END PUBLIC KEY-----';
  1479. $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
  1480. if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
  1481. return new Math_BigInteger($result, 256);
  1482. }
  1483. }
  1484. if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
  1485. $temp = new Math_BigInteger();
  1486. $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
  1487. return $this->_normalize($temp);
  1488. }
  1489. if ( empty($e->value) ) {
  1490. $temp = new Math_BigInteger();
  1491. $temp->value = array(1);
  1492. return $this->_normalize($temp);
  1493. }
  1494. if ( $e->value == array(1) ) {
  1495. list(, $temp) = $this->divide($n);
  1496. return $this->_normalize($temp);
  1497. }
  1498. if ( $e->value == array(2) ) {
  1499. $temp = new Math_BigInteger();
  1500. $temp->value = $this->_square($this->value);
  1501. list(, $temp) = $temp->divide($n);
  1502. return $this->_normalize($temp);
  1503. }
  1504. return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
  1505. // the following code, although not callable, can be run independently of the above code
  1506. // although the above code performed better in my benchmarks the following could might
  1507. // perform better under different circumstances. in lieu of deleting it it's just been
  1508. // made uncallable
  1509. // is the modulo odd?
  1510. if ( $n->value[0] & 1 ) {
  1511. return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
  1512. }
  1513. // if it's not, it's even
  1514. // find the lowest set bit (eg. the max pow of 2 that divides $n)
  1515. for ($i = 0; $i < count($n->value); ++$i) {
  1516. if ( $n->value[$i] ) {
  1517. $temp = decbin($n->value[$i]);
  1518. $j = strlen($temp) - strrpos($temp, '1') - 1;
  1519. $j+= 26 * $i;
  1520. break;
  1521. }
  1522. }
  1523. // at this point, 2^$j * $n/(2^$j) == $n
  1524. $mod1 = $n->copy();
  1525. $mod1->_rshift($j);
  1526. $mod2 = new Math_BigInteger();
  1527. $mod2->value = array(1);
  1528. $mod2->_lshift($j);
  1529. $part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
  1530. $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
  1531. $y1 = $mod2->modInverse($mod1);
  1532. $y2 = $mod1->modInverse($mod2);
  1533. $result = $part1->multiply($mod2);
  1534. $result = $result->multiply($y1);
  1535. $temp = $part2->multiply($mod1);
  1536. $temp = $temp->multiply($y2);
  1537. $result = $result->add($temp);
  1538. list(, $result) = $result->divide($n);
  1539. return $this->_normalize($result);
  1540. }
  1541. /**
  1542. * Performs modular exponentiation.
  1543. *
  1544. * Alias for Math_BigInteger::modPow()
  1545. *
  1546. * @param Math_BigInteger $e
  1547. * @param Math_BigInteger $n
  1548. * @return Math_BigInteger
  1549. * @access public
  1550. */
  1551. function powMod($e, $n)
  1552. {
  1553. return $this->modPow($e, $n);
  1554. }
  1555. /**
  1556. * Sliding Window k-ary Modular Exponentiation
  1557. *
  1558. * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
  1559. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims,
  1560. * however, this function performs a modular reduction after every multiplication and squaring operation.
  1561. * As such, this function has the same preconditions that the reductions being used do.
  1562. *
  1563. * @param Math_BigInteger $e
  1564. * @param Math_BigInteger $n
  1565. * @param Integer $mode
  1566. * @return Math_BigInteger
  1567. * @access private
  1568. */
  1569. function _slidingWindow($e, $n, $mode)
  1570. {
  1571. static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
  1572. //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
  1573. $e_value = $e->value;
  1574. $e_length = count($e_value) - 1;
  1575. $e_bits = decbin($e_value[$e_length]);
  1576. for ($i = $e_length - 1; $i >= 0; --$i) {
  1577. $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT);
  1578. }
  1579. $e_length = strlen($e_bits);
  1580. // calculate the appropriate window size.
  1581. // $window_size == 3 if $window_ranges is between 25 and 81, for example.
  1582. for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i);
  1583. $n_value = $n->value;
  1584. // precompute $this^0 through $this^$window_size
  1585. $powers = array();
  1586. $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
  1587. $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
  1588. // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
  1589. // in a 1. ie. it's supposed to be odd.
  1590. $temp = 1 << ($window_size - 1);
  1591. for ($i = 1; $i < $temp; ++$i) {
  1592. $i2 = $i << 1;
  1593. $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
  1594. }
  1595. $result = array(1);
  1596. $result = $this->_prepareReduce($result, $n_value, $mode);
  1597. for ($i = 0; $i < $e_length; ) {
  1598. if ( !$e_bits[$i] ) {
  1599. $result = $this->_squareReduce($result, $n_value, $mode);
  1600. ++$i;
  1601. } else {
  1602. for ($j = $window_size - 1; $j > 0; --$j) {
  1603. if ( !empty($e_bits[$i + $j]) ) {
  1604. break;
  1605. }
  1606. }
  1607. for ($k = 0; $k <= $j; ++$k) {// eg. the length of substr($e_bits, $i, $j+1)
  1608. $result = $this->_squareReduce($result, $n_value, $mode);
  1609. }
  1610. $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
  1611. $i+=$j + 1;
  1612. }
  1613. }
  1614. $temp = new Math_BigInteger();
  1615. $temp->value = $this->_reduce($result, $n_value, $mode);
  1616. return $temp;
  1617. }
  1618. /**
  1619. * Modular reduction
  1620. *
  1621. * For most $modes this will return the remainder.
  1622. *
  1623. * @see _slidingWindow()
  1624. * @access private
  1625. * @param Array $x
  1626. * @param Array $n
  1627. * @param Integer $mode
  1628. * @return Array
  1629. */
  1630. function _reduce($x, $n, $mode)
  1631. {
  1632. switch ($mode) {
  1633. case MATH_BIGINTEGER_MONTGOMERY:
  1634. return $this->_montgomery($x, $n);
  1635. case MATH_BIGINTEGER_BARRETT:
  1636. return $this->_barrett($x, $n);
  1637. case MATH_BIGINTEGER_POWEROF2:
  1638. $lhs = new Math_BigInteger();
  1639. $lhs->value = $x;
  1640. $rhs = new Math_BigInteger();
  1641. $rhs->value = $n;
  1642. return $x->_mod2($n);
  1643. case MATH_BIGINTEGER_CLASSIC:
  1644. $lhs = new Math_BigInteger();
  1645. $lhs->value = $x;
  1646. $rhs = new Math_BigInteger();
  1647. $rhs->value = $n;
  1648. list(, $temp) = $lhs->divide($rhs);
  1649. return $temp->value;
  1650. case MATH_BIGINTEGER_NONE:
  1651. return $x;
  1652. default:
  1653. // an invalid $mode was provided
  1654. }
  1655. }
  1656. /**
  1657. * Modular reduction preperation
  1658. *
  1659. * @see _slidingWindow()
  1660. * @access private
  1661. * @param Array $x
  1662. * @param Array $n
  1663. * @param Integer $mode
  1664. * @return Array
  1665. */
  1666. function _prepareReduce($x, $n, $mode)
  1667. {
  1668. if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  1669. return $this->_prepMontgomery($x, $n);
  1670. }
  1671. return $this->_reduce($x, $n, $mode);
  1672. }
  1673. /**
  1674. * Modular multiply
  1675. *
  1676. * @see _slidingWindow()
  1677. * @access private
  1678. * @param Array $x
  1679. * @param Array $y
  1680. * @param Array $n
  1681. * @param Integer $mode
  1682. * @return Array
  1683. */
  1684. function _multiplyReduce($x, $y, $n, $mode)
  1685. {
  1686. if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  1687. return $this->_montgomeryMultiply($x, $y, $n);
  1688. }
  1689. $temp = $this->_multiply($x, false, $y, false);
  1690. return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode);
  1691. }
  1692. /**
  1693. * Modular square
  1694. *
  1695. * @see _slidingWindow()
  1696. * @access private
  1697. * @param Array $x
  1698. * @param Array $n
  1699. * @param Integer $mode
  1700. * @return Array
  1701. */
  1702. function _squareReduce($x, $n, $mode)
  1703. {
  1704. if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
  1705. return $this->_montgomeryMultiply($x, $x, $n);
  1706. }
  1707. return $this->_reduce($this->_square($x), $n, $mode);
  1708. }
  1709. /**
  1710. * Modulos for Powers of Two
  1711. *
  1712. * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1),
  1713. * we'll just use this function as a wrapper for doing that.
  1714. *
  1715. * @see _slidingWindow()
  1716. * @access private
  1717. * @param Math_BigInteger
  1718. * @return Math_BigInteger
  1719. */
  1720. function _mod2($n)
  1721. {
  1722. $temp = new Math_BigInteger();
  1723. $temp->value = array(1);
  1724. return $this->bitwise_and($n->subtract($temp));
  1725. }
  1726. /**
  1727. * Barrett Modular Reduction
  1728. *
  1729. * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
  1730. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly,
  1731. * so as not to require negative numbers (initially, this script didn't support negative numbers).
  1732. *
  1733. * Employs "folding", as described at
  1734. * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from
  1735. * 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."
  1736. *
  1737. * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
  1738. * usable on account of (1) its not using reasonable radix points as discussed in
  1739. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
  1740. * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that
  1741. * (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
  1742. * comments for details.
  1743. *
  1744. * @see _slidingWindow()
  1745. * @access private
  1746. * @param Array $n
  1747. * @param Array $m
  1748. * @return Array
  1749. */
  1750. function _barrett($n, $m)
  1751. {
  1752. static $cache = array(
  1753. MATH_BIGINTEGER_VARIABLE => array(),
  1754. MATH_BIGINTEGER_DATA => array()
  1755. );
  1756. $m_length = count($m);
  1757. // if ($this->_compare($n, $this->_square($m)) >= 0) {
  1758. if (count($n) > 2 * $m_length) {
  1759. $lhs = new Math_BigInteger();
  1760. $rhs = new Math_BigInteger();
  1761. $lhs->value = $n;
  1762. $rhs->value = $m;
  1763. list(, $temp) = $lhs->divide($rhs);
  1764. return $temp->value;
  1765. }
  1766. // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
  1767. if ($m_length < 5) {
  1768. return $this->_regularBarrett($n, $m);
  1769. }
  1770. // n = 2 * m.length
  1771. if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
  1772. $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
  1773. $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
  1774. $lhs = new Math_BigInteger();
  1775. $lhs_value = &$lhs->value;
  1776. $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
  1777. $lhs_value[] = 1;
  1778. $rhs = new Math_BigInteger();
  1779. $rhs->value = $m;
  1780. list($u, $m1) = $lhs->divide($rhs);
  1781. $u = $u->value;
  1782. $m1 = $m1->value;
  1783. $cache[MATH_BIGINTEGER_DATA][] = array(
  1784. 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
  1785. 'm1'=> $m1 // m.length
  1786. );
  1787. } else {
  1788. extract($cache[MATH_BIGINTEGER_DATA][$key]);
  1789. }
  1790. $cutoff = $m_length + ($m_length >> 1);
  1791. $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
  1792. $msd = array_slice($n, $cutoff); // m.length >> 1
  1793. $lsd = $this->_trim($lsd);
  1794. $temp = $this->_multiply($msd, false, $m1, false);
  1795. $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false); // m.length + (m.length >> 1) + 1
  1796. if ($m_length & 1) {
  1797. return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
  1798. }
  1799. // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
  1800. $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1);
  1801. // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
  1802. // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
  1803. $temp = $this->_multiply($temp, false, $u, false);
  1804. // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
  1805. // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
  1806. $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
  1807. // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
  1808. // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
  1809. $temp = $this->_multiply($temp, false, $m, false);
  1810. // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
  1811. // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
  1812. // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
  1813. $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
  1814. while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) {
  1815. $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false);
  1816. }
  1817. return $result[MATH_BIGINTEGER_VALUE];
  1818. }
  1819. /**
  1820. * (Regular) Barrett Modular Reduction
  1821. *
  1822. * For numbers with more than four digits Math_BigInteger::_barrett() is faster. The difference between that and this
  1823. * is that this function does not fold the denominator into a smaller form.
  1824. *
  1825. * @see _slidingWindow()
  1826. * @access private
  1827. * @param Array $x
  1828. * @param Array $n
  1829. * @return Array
  1830. */
  1831. function _regularBarrett($x, $n)
  1832. {
  1833. static $cache = array(
  1834. MATH_BIGINTEGER_VARIABLE => array(),
  1835. MATH_BIGINTEGER_DATA => array()
  1836. );
  1837. $n_length = count($n);
  1838. if (count($x) > 2 * $n_length) {
  1839. $lhs = new Math_BigInteger();
  1840. $rhs = new Math_BigInteger();
  1841. $lhs->value = $x;
  1842. $rhs->value = $n;
  1843. list(, $temp) = $lhs->divide($rhs);
  1844. return $temp->value;
  1845. }
  1846. if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
  1847. $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
  1848. $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
  1849. $lhs = new Math_BigInteger();
  1850. $lhs_value = &$lhs->value;
  1851. $lhs_value = $this->_array_repeat(0, 2 * $n_length);
  1852. $lhs_value[] = 1;
  1853. $rhs = new Math_BigInteger();
  1854. $rhs->value = $n;
  1855. list($temp, ) = $lhs->divide($rhs); // m.length
  1856. $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
  1857. }
  1858. // 2 * m.length - (m.length - 1) = m.length + 1
  1859. $temp = array_slice($x, $n_length - 1);
  1860. // (m.length + 1) + m.length = 2 * m.length + 1
  1861. $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false);
  1862. // (2 * m.length + 1) - (m.length - 1) = m.length + 2
  1863. $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1);
  1864. // m.length + 1
  1865. $result = array_slice($x, 0, $n_length + 1);
  1866. // m.length + 1
  1867. $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
  1868. // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
  1869. if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
  1870. $corrector_value = $this->_array_repeat(0, $n_length + 1);
  1871. $corrector_value[count($corrector_value)] = 1;
  1872. $result = $this->_add($result, false, $corrector_value, false);
  1873. $result = $result[MATH_BIGINTEGER_VALUE];
  1874. }
  1875. // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
  1876. $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
  1877. while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) {
  1878. $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false);
  1879. }
  1880. return $result[MATH_BIGINTEGER_VALUE];
  1881. }
  1882. /**
  1883. * Performs long multiplication up to $stop digits
  1884. *
  1885. * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
  1886. *
  1887. * @see _regularBarrett()
  1888. * @param Array $x_value
  1889. * @param Boolean $x_negative
  1890. * @param Array $y_value
  1891. * @param Boolean $y_negative
  1892. * @param Integer $stop
  1893. * @return Array
  1894. * @access private
  1895. */
  1896. function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
  1897. {
  1898. $x_length = count($x_value);
  1899. $y_length = count($y_value);
  1900. if ( !$x_length || !$y_length ) { // a 0 is being multiplied
  1901. return array(
  1902. MATH_BIGINTEGER_VALUE => array(),
  1903. MATH_BIGINTEGER_SIGN => false
  1904. );
  1905. }
  1906. if ( $x_length < $y_length ) {
  1907. $temp = $x_value;
  1908. $x_value = $y_value;
  1909. $y_value = $temp;
  1910. $x_length = count($x_value);
  1911. $y_length = count($y_value);
  1912. }
  1913. $product_value = $this->_array_repeat(0, $x_length + $y_length);
  1914. // the following for loop could be removed if the for loop following it
  1915. // (the one with nested for loops) initially set $i to 0, but
  1916. // doing so would also make the result in one set of unnecessary adds,
  1917. // since on the outermost loops first pass, $product->value[$k] is going
  1918. // to always be 0
  1919. $carry = 0;
  1920. for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
  1921. $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
  1922. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1923. $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1924. }
  1925. if ($j < $stop) {
  1926. $product_value[$j] = $carry;
  1927. }
  1928. // the above for loop is what the previous comment was talking about. the
  1929. // following for loop is the "one with nested for loops"
  1930. for ($i = 1; $i < $y_length; ++$i) {
  1931. $carry = 0;
  1932. for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
  1933. $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  1934. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  1935. $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
  1936. }
  1937. if ($k < $stop) {
  1938. $product_value[$k] = $carry;
  1939. }
  1940. }
  1941. return array(
  1942. MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
  1943. MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
  1944. );
  1945. }
  1946. /**
  1947. * Montgomery Modular Reduction
  1948. *
  1949. * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
  1950. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
  1951. * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function
  1952. * to work correctly.
  1953. *
  1954. * @see _prepMontgomery()
  1955. * @see _slidingWindow()
  1956. * @access private
  1957. * @param Array $x
  1958. * @param Array $n
  1959. * @return Array
  1960. */
  1961. function _montgomery($x, $n)
  1962. {
  1963. static $cache = array(
  1964. MATH_BIGINTEGER_VARIABLE => array(),
  1965. MATH_BIGINTEGER_DATA => array()
  1966. );
  1967. if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
  1968. $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
  1969. $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
  1970. $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
  1971. }
  1972. $k = count($n);
  1973. $result = array(MATH_BIGINTEGER_VALUE => $x);
  1974. for ($i = 0; $i < $k; ++$i) {
  1975. $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
  1976. $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  1977. $temp = $this->_regularMultiply(array($temp), $n);
  1978. $temp = array_merge($this->_array_repeat(0, $i), $temp);
  1979. $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false);
  1980. }
  1981. $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
  1982. if ($this->_compare($result, false, $n, false) >= 0) {
  1983. $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false);
  1984. }
  1985. return $result[MATH_BIGINTEGER_VALUE];
  1986. }
  1987. /**
  1988. * Montgomery Multiply
  1989. *
  1990. * Interleaves the montgomery reduction and long multiplication algorithms together as described in
  1991. * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
  1992. *
  1993. * @see _prepMontgomery()
  1994. * @see _montgomery()
  1995. * @access private
  1996. * @param Array $x
  1997. * @param Array $y
  1998. * @param Array $m
  1999. * @return Array
  2000. */
  2001. function _montgomeryMultiply($x, $y, $m)
  2002. {
  2003. $temp = $this->_multiply($x, false, $y, false);
  2004. return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
  2005. // the following code, although not callable, can be run independently of the above code
  2006. // although the above code performed better in my benchmarks the following could might
  2007. // perform better under different circumstances. in lieu of deleting it it's just been
  2008. // made uncallable
  2009. static $cache = array(
  2010. MATH_BIGINTEGER_VARIABLE => array(),
  2011. MATH_BIGINTEGER_DATA => array()
  2012. );
  2013. if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
  2014. $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
  2015. $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
  2016. $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
  2017. }
  2018. $n = max(count($x), count($y), count($m));
  2019. $x = array_pad($x, $n, 0);
  2020. $y = array_pad($y, $n, 0);
  2021. $m = array_pad($m, $n, 0);
  2022. $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1));
  2023. for ($i = 0; $i < $n; ++$i) {
  2024. $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
  2025. $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  2026. $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key];
  2027. $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  2028. $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
  2029. $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
  2030. $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
  2031. }
  2032. if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) {
  2033. $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false);
  2034. }
  2035. return $a[MATH_BIGINTEGER_VALUE];
  2036. }
  2037. /**
  2038. * Prepare a number for use in Montgomery Modular Reductions
  2039. *
  2040. * @see _montgomery()
  2041. * @see _slidingWindow()
  2042. * @access private
  2043. * @param Array $x
  2044. * @param Array $n
  2045. * @return Array
  2046. */
  2047. function _prepMontgomery($x, $n)
  2048. {
  2049. $lhs = new Math_BigInteger();
  2050. $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
  2051. $rhs = new Math_BigInteger();
  2052. $rhs->value = $n;
  2053. list(, $temp) = $lhs->divide($rhs);
  2054. return $temp->value;
  2055. }
  2056. /**
  2057. * Modular Inverse of a number mod 2**26 (eg. 67108864)
  2058. *
  2059. * Based off of the bnpInvDigit function implemented and justified in the following URL:
  2060. *
  2061. * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
  2062. *
  2063. * The following URL provides more info:
  2064. *
  2065. * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
  2066. *
  2067. * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For
  2068. * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
  2069. * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
  2070. * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that
  2071. * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the
  2072. * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to
  2073. * 40 bits, which only 64-bit floating points will support.
  2074. *
  2075. * Thanks to Pedro Gimeno Fortea for input!
  2076. *
  2077. * @see _montgomery()
  2078. * @access private
  2079. * @param Array $x
  2080. * @return Integer
  2081. */
  2082. function _modInverse67108864($x) // 2**26 == 67,108,864
  2083. {
  2084. $x = -$x[0];
  2085. $result = $x & 0x3; // x**-1 mod 2**2
  2086. $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
  2087. $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
  2088. $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
  2089. $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL); // x**-1 mod 2**26
  2090. return $result & MATH_BIGINTEGER_MAX_DIGIT;
  2091. }
  2092. /**
  2093. * Calculates modular inverses.
  2094. *
  2095. * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
  2096. *
  2097. * Here's an example:
  2098. * <code>
  2099. * <?php
  2100. * include 'Math/BigInteger.php';
  2101. *
  2102. * $a = new Math_BigInteger(30);
  2103. * $b = new Math_BigInteger(17);
  2104. *
  2105. * $c = $a->modInverse($b);
  2106. * echo $c->toString(); // outputs 4
  2107. *
  2108. * echo "\r\n";
  2109. *
  2110. * $d = $a->multiply($c);
  2111. * list(, $d) = $d->divide($b);
  2112. * echo $d; // outputs 1 (as per the definition of modular inverse)
  2113. * ?>
  2114. * </code>
  2115. *
  2116. * @param Math_BigInteger $n
  2117. * @return mixed false, if no modular inverse exists, Math_BigInteger, otherwise.
  2118. * @access public
  2119. * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
  2120. */
  2121. function modInverse($n)
  2122. {
  2123. switch ( MATH_BIGINTEGER_MODE ) {
  2124. case MATH_BIGINTEGER_MODE_GMP:
  2125. $temp = new Math_BigInteger();
  2126. $temp->value = gmp_invert($this->value, $n->value);
  2127. return ( $temp->value === false ) ? false : $this->_normalize($temp);
  2128. }
  2129. static $zero, $one;
  2130. if (!isset($zero)) {
  2131. $zero = new Math_BigInteger();
  2132. $one = new Math_BigInteger(1);
  2133. }
  2134. // $x mod -$n == $x mod $n.
  2135. $n = $n->abs();
  2136. if ($this->compare($zero) < 0) {
  2137. $temp = $this->abs();
  2138. $temp = $temp->modInverse($n);
  2139. return $this->_normalize($n->subtract($temp));
  2140. }
  2141. extract($this->extendedGCD($n));
  2142. if (!$gcd->equals($one)) {
  2143. return false;
  2144. }
  2145. $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
  2146. return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
  2147. }
  2148. /**
  2149. * Calculates the greatest common divisor and Bezout's identity.
  2150. *
  2151. * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that
  2152. * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which
  2153. * combination is returned is dependant upon which mode is in use. See
  2154. * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
  2155. *
  2156. * Here's an example:
  2157. * <code>
  2158. * <?php
  2159. * include 'Math/BigInteger.php';
  2160. *
  2161. * $a = new Math_BigInteger(693);
  2162. * $b = new Math_BigInteger(609);
  2163. *
  2164. * extract($a->extendedGCD($b));
  2165. *
  2166. * echo $gcd->toString() . "\r\n"; // outputs 21
  2167. * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
  2168. * ?>
  2169. * </code>
  2170. *
  2171. * @param Math_BigInteger $n
  2172. * @return Math_BigInteger
  2173. * @access public
  2174. * @internal Calculates the GCD using the binary xGCD algorithim described in
  2175. * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes,
  2176. * the more traditional algorithim requires "relatively costly multiple-precision divisions".
  2177. */
  2178. function extendedGCD($n)
  2179. {
  2180. switch ( MATH_BIGINTEGER_MODE ) {
  2181. case MATH_BIGINTEGER_MODE_GMP:
  2182. extract(gmp_gcdext($this->value, $n->value));
  2183. return array(
  2184. 'gcd' => $this->_normalize(new Math_BigInteger($g)),
  2185. 'x' => $this->_normalize(new Math_BigInteger($s)),
  2186. 'y' => $this->_normalize(new Math_BigInteger($t))
  2187. );
  2188. case MATH_BIGINTEGER_MODE_BCMATH:
  2189. // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
  2190. // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
  2191. // the basic extended euclidean algorithim is what we're using.
  2192. $u = $this->value;
  2193. $v = $n->value;
  2194. $a = '1';
  2195. $b = '0';
  2196. $c = '0';
  2197. $d = '1';
  2198. while (bccomp($v, '0', 0) != 0) {
  2199. $q = bcdiv($u, $v, 0);
  2200. $temp = $u;
  2201. $u = $v;
  2202. $v = bcsub($temp, bcmul($v, $q, 0), 0);
  2203. $temp = $a;
  2204. $a = $c;
  2205. $c = bcsub($temp, bcmul($a, $q, 0), 0);
  2206. $temp = $b;
  2207. $b = $d;
  2208. $d = bcsub($temp, bcmul($b, $q, 0), 0);
  2209. }
  2210. return array(
  2211. 'gcd' => $this->_normalize(new Math_BigInteger($u)),
  2212. 'x' => $this->_normalize(new Math_BigInteger($a)),
  2213. 'y' => $this->_normalize(new Math_BigInteger($b))
  2214. );
  2215. }
  2216. $y = $n->copy();
  2217. $x = $this->copy();
  2218. $g = new Math_BigInteger();
  2219. $g->value = array(1);
  2220. while ( !(($x->value[0] & 1)|| ($y->value[0] & 1)) ) {
  2221. $x->_rshift(1);
  2222. $y->_rshift(1);
  2223. $g->_lshift(1);
  2224. }
  2225. $u = $x->copy();
  2226. $v = $y->copy();
  2227. $a = new Math_BigInteger();
  2228. $b = new Math_BigInteger();
  2229. $c = new Math_BigInteger();
  2230. $d = new Math_BigInteger();
  2231. $a->value = $d->value = $g->value = array(1);
  2232. $b->value = $c->value = array();
  2233. while ( !empty($u->value) ) {
  2234. while ( !($u->value[0] & 1) ) {
  2235. $u->_rshift(1);
  2236. if ( (!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1)) ) {
  2237. $a = $a->add($y);
  2238. $b = $b->subtract($x);
  2239. }
  2240. $a->_rshift(1);
  2241. $b->_rshift(1);
  2242. }
  2243. while ( !($v->value[0] & 1) ) {
  2244. $v->_rshift(1);
  2245. if ( (!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1)) ) {
  2246. $c = $c->add($y);
  2247. $d = $d->subtract($x);
  2248. }
  2249. $c->_rshift(1);
  2250. $d->_rshift(1);
  2251. }
  2252. if ($u->compare($v) >= 0) {
  2253. $u = $u->subtract($v);
  2254. $a = $a->subtract($c);
  2255. $b = $b->subtract($d);
  2256. } else {
  2257. $v = $v->subtract($u);
  2258. $c = $c->subtract($a);
  2259. $d = $d->subtract($b);
  2260. }
  2261. }
  2262. return array(
  2263. 'gcd' => $this->_normalize($g->multiply($v)),
  2264. 'x' => $this->_normalize($c),
  2265. 'y' => $this->_normalize($d)
  2266. );
  2267. }
  2268. /**
  2269. * Calculates the greatest common divisor
  2270. *
  2271. * Say you have 693 and 609. The GCD is 21.
  2272. *
  2273. * Here's an example:
  2274. * <code>
  2275. * <?php
  2276. * include 'Math/BigInteger.php';
  2277. *
  2278. * $a = new Math_BigInteger(693);
  2279. * $b = new Math_BigInteger(609);
  2280. *
  2281. * $gcd = a->extendedGCD($b);
  2282. *
  2283. * echo $gcd->toString() . "\r\n"; // outputs 21
  2284. * ?>
  2285. * </code>
  2286. *
  2287. * @param Math_BigInteger $n
  2288. * @return Math_BigInteger
  2289. * @access public
  2290. */
  2291. function gcd($n)
  2292. {
  2293. extract($this->extendedGCD($n));
  2294. return $gcd;
  2295. }
  2296. /**
  2297. * Absolute value.
  2298. *
  2299. * @return Math_BigInteger
  2300. * @access public
  2301. */
  2302. function abs()
  2303. {
  2304. $temp = new Math_BigInteger();
  2305. switch ( MATH_BIGINTEGER_MODE ) {
  2306. case MATH_BIGINTEGER_MODE_GMP:
  2307. $temp->value = gmp_abs($this->value);
  2308. break;
  2309. case MATH_BIGINTEGER_MODE_BCMATH:
  2310. $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
  2311. break;
  2312. default:
  2313. $temp->value = $this->value;
  2314. }
  2315. return $temp;
  2316. }
  2317. /**
  2318. * Compares two numbers.
  2319. *
  2320. * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is
  2321. * demonstrated thusly:
  2322. *
  2323. * $x > $y: $x->compare($y) > 0
  2324. * $x < $y: $x->compare($y) < 0
  2325. * $x == $y: $x->compare($y) == 0
  2326. *
  2327. * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
  2328. *
  2329. * @param Math_BigInteger $y
  2330. * @return Integer < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
  2331. * @access public
  2332. * @see equals()
  2333. * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
  2334. */
  2335. function compare($y)
  2336. {
  2337. switch ( MATH_BIGINTEGER_MODE ) {
  2338. case MATH_BIGINTEGER_MODE_GMP:
  2339. return gmp_cmp($this->value, $y->value);
  2340. case MATH_BIGINTEGER_MODE_BCMATH:
  2341. return bccomp($this->value, $y->value, 0);
  2342. }
  2343. return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
  2344. }
  2345. /**
  2346. * Compares two numbers.
  2347. *
  2348. * @param Array $x_value
  2349. * @param Boolean $x_negative
  2350. * @param Array $y_value
  2351. * @param Boolean $y_negative
  2352. * @return Integer
  2353. * @see compare()
  2354. * @access private
  2355. */
  2356. function _compare($x_value, $x_negative, $y_value, $y_negative)
  2357. {
  2358. if ( $x_negative != $y_negative ) {
  2359. return ( !$x_negative && $y_negative ) ? 1 : -1;
  2360. }
  2361. $result = $x_negative ? -1 : 1;
  2362. if ( count($x_value) != count($y_value) ) {
  2363. return ( count($x_value) > count($y_value) ) ? $result : -$result;
  2364. }
  2365. $size = max(count($x_value), count($y_value));
  2366. $x_value = array_pad($x_value, $size, 0);
  2367. $y_value = array_pad($y_value, $size, 0);
  2368. for ($i = count($x_value) - 1; $i >= 0; --$i) {
  2369. if ($x_value[$i] != $y_value[$i]) {
  2370. return ( $x_value[$i] > $y_value[$i] ) ? $result : -$result;
  2371. }
  2372. }
  2373. return 0;
  2374. }
  2375. /**
  2376. * Tests the equality of two numbers.
  2377. *
  2378. * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
  2379. *
  2380. * @param Math_BigInteger $x
  2381. * @return Boolean
  2382. * @access public
  2383. * @see compare()
  2384. */
  2385. function equals($x)
  2386. {
  2387. switch ( MATH_BIGINTEGER_MODE ) {
  2388. case MATH_BIGINTEGER_MODE_GMP:
  2389. return gmp_cmp($this->value, $x->value) == 0;
  2390. default:
  2391. return $this->value === $x->value && $this->is_negative == $x->is_negative;
  2392. }
  2393. }
  2394. /**
  2395. * Set Precision
  2396. *
  2397. * Some bitwise operations give different results depending on the precision being used. Examples include left
  2398. * shift, not, and rotates.
  2399. *
  2400. * @param Integer $bits
  2401. * @access public
  2402. */
  2403. function setPrecision($bits)
  2404. {
  2405. $this->precision = $bits;
  2406. if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ) {
  2407. $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
  2408. } else {
  2409. $this->bitmask = new Math_BigInteger(bcpow('2', $bits, 0));
  2410. }
  2411. $temp = $this->_normalize($this);
  2412. $this->value = $temp->value;
  2413. }
  2414. /**
  2415. * Logical And
  2416. *
  2417. * @param Math_BigInteger $x
  2418. * @access public
  2419. * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2420. * @return Math_BigInteger
  2421. */
  2422. function bitwise_and($x)
  2423. {
  2424. switch ( MATH_BIGINTEGER_MODE ) {
  2425. case MATH_BIGINTEGER_MODE_GMP:
  2426. $temp = new Math_BigInteger();
  2427. $temp->value = gmp_and($this->value, $x->value);
  2428. return $this->_normalize($temp);
  2429. case MATH_BIGINTEGER_MODE_BCMATH:
  2430. $left = $this->toBytes();
  2431. $right = $x->toBytes();
  2432. $length = max(strlen($left), strlen($right));
  2433. $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
  2434. $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
  2435. return $this->_normalize(new Math_BigInteger($left & $right, 256));
  2436. }
  2437. $result = $this->copy();
  2438. $length = min(count($x->value), count($this->value));
  2439. $result->value = array_slice($result->value, 0, $length);
  2440. for ($i = 0; $i < $length; ++$i) {
  2441. $result->value[$i]&= $x->value[$i];
  2442. }
  2443. return $this->_normalize($result);
  2444. }
  2445. /**
  2446. * Logical Or
  2447. *
  2448. * @param Math_BigInteger $x
  2449. * @access public
  2450. * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2451. * @return Math_BigInteger
  2452. */
  2453. function bitwise_or($x)
  2454. {
  2455. switch ( MATH_BIGINTEGER_MODE ) {
  2456. case MATH_BIGINTEGER_MODE_GMP:
  2457. $temp = new Math_BigInteger();
  2458. $temp->value = gmp_or($this->value, $x->value);
  2459. return $this->_normalize($temp);
  2460. case MATH_BIGINTEGER_MODE_BCMATH:
  2461. $left = $this->toBytes();
  2462. $right = $x->toBytes();
  2463. $length = max(strlen($left), strlen($right));
  2464. $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
  2465. $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
  2466. return $this->_normalize(new Math_BigInteger($left | $right, 256));
  2467. }
  2468. $length = max(count($this->value), count($x->value));
  2469. $result = $this->copy();
  2470. $result->value = array_pad($result->value, $length, 0);
  2471. $x->value = array_pad($x->value, $length, 0);
  2472. for ($i = 0; $i < $length; ++$i) {
  2473. $result->value[$i]|= $x->value[$i];
  2474. }
  2475. return $this->_normalize($result);
  2476. }
  2477. /**
  2478. * Logical Exclusive-Or
  2479. *
  2480. * @param Math_BigInteger $x
  2481. * @access public
  2482. * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2483. * @return Math_BigInteger
  2484. */
  2485. function bitwise_xor($x)
  2486. {
  2487. switch ( MATH_BIGINTEGER_MODE ) {
  2488. case MATH_BIGINTEGER_MODE_GMP:
  2489. $temp = new Math_BigInteger();
  2490. $temp->value = gmp_xor($this->value, $x->value);
  2491. return $this->_normalize($temp);
  2492. case MATH_BIGINTEGER_MODE_BCMATH:
  2493. $left = $this->toBytes();
  2494. $right = $x->toBytes();
  2495. $length = max(strlen($left), strlen($right));
  2496. $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
  2497. $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
  2498. return $this->_normalize(new Math_BigInteger($left ^ $right, 256));
  2499. }
  2500. $length = max(count($this->value), count($x->value));
  2501. $result = $this->copy();
  2502. $result->value = array_pad($result->value, $length, 0);
  2503. $x->value = array_pad($x->value, $length, 0);
  2504. for ($i = 0; $i < $length; ++$i) {
  2505. $result->value[$i]^= $x->value[$i];
  2506. }
  2507. return $this->_normalize($result);
  2508. }
  2509. /**
  2510. * Logical Not
  2511. *
  2512. * @access public
  2513. * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
  2514. * @return Math_BigInteger
  2515. */
  2516. function bitwise_not()
  2517. {
  2518. // calculuate "not" without regard to $this->precision
  2519. // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
  2520. $temp = $this->toBytes();
  2521. $pre_msb = decbin(ord($temp[0]));
  2522. $temp = ~$temp;
  2523. $msb = decbin(ord($temp[0]));
  2524. if (strlen($msb) == 8) {
  2525. $msb = substr($msb, strpos($msb, '0'));
  2526. }
  2527. $temp[0] = chr(bindec($msb));
  2528. // see if we need to add extra leading 1's
  2529. $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
  2530. $new_bits = $this->precision - $current_bits;
  2531. if ($new_bits <= 0) {
  2532. return $this->_normalize(new Math_BigInteger($temp, 256));
  2533. }
  2534. // generate as many leading 1's as we need to.
  2535. $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
  2536. $this->_base256_lshift($leading_ones, $current_bits);
  2537. $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
  2538. return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256));
  2539. }
  2540. /**
  2541. * Logical Right Shift
  2542. *
  2543. * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
  2544. *
  2545. * @param Integer $shift
  2546. * @return Math_BigInteger
  2547. * @access public
  2548. * @internal The only version that yields any speed increases is the internal version.
  2549. */
  2550. function bitwise_rightShift($shift)
  2551. {
  2552. $temp = new Math_BigInteger();
  2553. switch ( MATH_BIGINTEGER_MODE ) {
  2554. case MATH_BIGINTEGER_MODE_GMP:
  2555. static $two;
  2556. if (!isset($two)) {
  2557. $two = gmp_init('2');
  2558. }
  2559. $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
  2560. break;
  2561. case MATH_BIGINTEGER_MODE_BCMATH:
  2562. $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
  2563. break;
  2564. default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
  2565. // and I don't want to do that...
  2566. $temp->value = $this->value;
  2567. $temp->_rshift($shift);
  2568. }
  2569. return $this->_normalize($temp);
  2570. }
  2571. /**
  2572. * Logical Left Shift
  2573. *
  2574. * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
  2575. *
  2576. * @param Integer $shift
  2577. * @return Math_BigInteger
  2578. * @access public
  2579. * @internal The only version that yields any speed increases is the internal version.
  2580. */
  2581. function bitwise_leftShift($shift)
  2582. {
  2583. $temp = new Math_BigInteger();
  2584. switch ( MATH_BIGINTEGER_MODE ) {
  2585. case MATH_BIGINTEGER_MODE_GMP:
  2586. static $two;
  2587. if (!isset($two)) {
  2588. $two = gmp_init('2');
  2589. }
  2590. $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
  2591. break;
  2592. case MATH_BIGINTEGER_MODE_BCMATH:
  2593. $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
  2594. break;
  2595. default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
  2596. // and I don't want to do that...
  2597. $temp->value = $this->value;
  2598. $temp->_lshift($shift);
  2599. }
  2600. return $this->_normalize($temp);
  2601. }
  2602. /**
  2603. * Logical Left Rotate
  2604. *
  2605. * Instead of the top x bits being dropped they're appended to the shifted bit string.
  2606. *
  2607. * @param Integer $shift
  2608. * @return Math_BigInteger
  2609. * @access public
  2610. */
  2611. function bitwise_leftRotate($shift)
  2612. {
  2613. $bits = $this->toBytes();
  2614. if ($this->precision > 0) {
  2615. $precision = $this->precision;
  2616. if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
  2617. $mask = $this->bitmask->subtract(new Math_BigInteger(1));
  2618. $mask = $mask->toBytes();
  2619. } else {
  2620. $mask = $this->bitmask->toBytes();
  2621. }
  2622. } else {
  2623. $temp = ord($bits[0]);
  2624. for ($i = 0; $temp >> $i; ++$i);
  2625. $precision = 8 * strlen($bits) - 8 + $i;
  2626. $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
  2627. }
  2628. if ($shift < 0) {
  2629. $shift+= $precision;
  2630. }
  2631. $shift%= $precision;
  2632. if (!$shift) {
  2633. return $this->copy();
  2634. }
  2635. $left = $this->bitwise_leftShift($shift);
  2636. $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
  2637. $right = $this->bitwise_rightShift($precision - $shift);
  2638. $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
  2639. return $this->_normalize($result);
  2640. }
  2641. /**
  2642. * Logical Right Rotate
  2643. *
  2644. * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
  2645. *
  2646. * @param Integer $shift
  2647. * @return Math_BigInteger
  2648. * @access public
  2649. */
  2650. function bitwise_rightRotate($shift)
  2651. {
  2652. return $this->bitwise_leftRotate(-$shift);
  2653. }
  2654. /**
  2655. * Set random number generator function
  2656. *
  2657. * This function is deprecated.
  2658. *
  2659. * @param String $generator
  2660. * @access public
  2661. */
  2662. function setRandomGenerator($generator)
  2663. {
  2664. }
  2665. /**
  2666. * Generates a random BigInteger
  2667. *
  2668. * Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.
  2669. *
  2670. * @param Integer $length
  2671. * @return Math_BigInteger
  2672. * @access private
  2673. */
  2674. function _random_number_helper($size)
  2675. {
  2676. if (function_exists('crypt_random_string')) {
  2677. $random = crypt_random_string($size);
  2678. } else {
  2679. $random = '';
  2680. if ($size & 1) {
  2681. $random.= chr(mt_rand(0, 255));
  2682. }
  2683. $blocks = $size >> 1;
  2684. for ($i = 0; $i < $blocks; ++$i) {
  2685. // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
  2686. $random.= pack('n', mt_rand(0, 0xFFFF));
  2687. }
  2688. }
  2689. return new Math_BigInteger($random, 256);
  2690. }
  2691. /**
  2692. * Generate a random number
  2693. *
  2694. * Returns a random number between $min and $max where $min and $max
  2695. * can be defined using one of the two methods:
  2696. *
  2697. * $min->random($max)
  2698. * $max->random($min)
  2699. *
  2700. * @param Math_BigInteger $arg1
  2701. * @param optional Math_BigInteger $arg2
  2702. * @return Math_BigInteger
  2703. * @access public
  2704. * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a Math_BigInteger object.
  2705. * That method is still supported for BC purposes.
  2706. */
  2707. function random($arg1, $arg2 = false)
  2708. {
  2709. if ($arg1 === false) {
  2710. return false;
  2711. }
  2712. if ($arg2 === false) {
  2713. $max = $arg1;
  2714. $min = $this;
  2715. } else {
  2716. $min = $arg1;
  2717. $max = $arg2;
  2718. }
  2719. $compare = $max->compare($min);
  2720. if (!$compare) {
  2721. return $this->_normalize($min);
  2722. } else if ($compare < 0) {
  2723. // if $min is bigger then $max, swap $min and $max
  2724. $temp = $max;
  2725. $max = $min;
  2726. $min = $temp;
  2727. }
  2728. static $one;
  2729. if (!isset($one)) {
  2730. $one = new Math_BigInteger(1);
  2731. }
  2732. $max = $max->subtract($min->subtract($one));
  2733. $size = strlen(ltrim($max->toBytes(), chr(0)));
  2734. /*
  2735. doing $random % $max doesn't work because some numbers will be more likely to occur than others.
  2736. eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
  2737. would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
  2738. not all numbers would be equally likely. some would be more likely than others.
  2739. creating a whole new random number until you find one that is within the range doesn't work
  2740. because, for sufficiently small ranges, the likelihood that you'd get a number within that range
  2741. would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
  2742. would be pretty high that $random would be greater than $max.
  2743. phpseclib works around this using the technique described here:
  2744. http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
  2745. */
  2746. $random_max = new Math_BigInteger(chr(1) . str_repeat("\0", $size), 256);
  2747. $random = $this->_random_number_helper($size);
  2748. list($max_multiple) = $random_max->divide($max);
  2749. $max_multiple = $max_multiple->multiply($max);
  2750. while ($random->compare($max_multiple) >= 0) {
  2751. $random = $random->subtract($max_multiple);
  2752. $random_max = $random_max->subtract($max_multiple);
  2753. $random = $random->bitwise_leftShift(8);
  2754. $random = $random->add($this->_random_number_helper(1));
  2755. $random_max = $random_max->bitwise_leftShift(8);
  2756. list($max_multiple) = $random_max->divide($max);
  2757. $max_multiple = $max_multiple->multiply($max);
  2758. }
  2759. list(, $random) = $random->divide($max);
  2760. return $this->_normalize($random->add($min));
  2761. }
  2762. /**
  2763. * Generate a random prime number.
  2764. *
  2765. * If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed,
  2766. * give up and return false.
  2767. *
  2768. * @param Math_BigInteger $arg1
  2769. * @param optional Math_BigInteger $arg2
  2770. * @param optional Integer $timeout
  2771. * @return Mixed
  2772. * @access public
  2773. * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
  2774. */
  2775. function randomPrime($arg1, $arg2 = false, $timeout = false)
  2776. {
  2777. if ($arg1 === false) {
  2778. return false;
  2779. }
  2780. if ($arg2 === false) {
  2781. $max = $arg1;
  2782. $min = $this;
  2783. } else {
  2784. $min = $arg1;
  2785. $max = $arg2;
  2786. }
  2787. $compare = $max->compare($min);
  2788. if (!$compare) {
  2789. return $min->isPrime() ? $min : false;
  2790. } else if ($compare < 0) {
  2791. // if $min is bigger then $max, swap $min and $max
  2792. $temp = $max;
  2793. $max = $min;
  2794. $min = $temp;
  2795. }
  2796. static $one, $two;
  2797. if (!isset($one)) {
  2798. $one = new Math_BigInteger(1);
  2799. $two = new Math_BigInteger(2);
  2800. }
  2801. $start = time();
  2802. $x = $this->random($min, $max);
  2803. // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
  2804. if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && function_exists('gmp_nextprime') ) {
  2805. $p = new Math_BigInteger();
  2806. $p->value = gmp_nextprime($x->value);
  2807. if ($p->compare($max) <= 0) {
  2808. return $p;
  2809. }
  2810. if (!$min->equals($x)) {
  2811. $x = $x->subtract($one);
  2812. }
  2813. return $x->randomPrime($min, $x);
  2814. }
  2815. if ($x->equals($two)) {
  2816. return $x;
  2817. }
  2818. $x->_make_odd();
  2819. if ($x->compare($max) > 0) {
  2820. // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
  2821. if ($min->equals($max)) {
  2822. return false;
  2823. }
  2824. $x = $min->copy();
  2825. $x->_make_odd();
  2826. }
  2827. $initial_x = $x->copy();
  2828. while (true) {
  2829. if ($timeout !== false && time() - $start > $timeout) {
  2830. return false;
  2831. }
  2832. if ($x->isPrime()) {
  2833. return $x;
  2834. }
  2835. $x = $x->add($two);
  2836. if ($x->compare($max) > 0) {
  2837. $x = $min->copy();
  2838. if ($x->equals($two)) {
  2839. return $x;
  2840. }
  2841. $x->_make_odd();
  2842. }
  2843. if ($x->equals($initial_x)) {
  2844. return false;
  2845. }
  2846. }
  2847. }
  2848. /**
  2849. * Make the current number odd
  2850. *
  2851. * If the current number is odd it'll be unchanged. If it's even, one will be added to it.
  2852. *
  2853. * @see randomPrime()
  2854. * @access private
  2855. */
  2856. function _make_odd()
  2857. {
  2858. switch ( MATH_BIGINTEGER_MODE ) {
  2859. case MATH_BIGINTEGER_MODE_GMP:
  2860. gmp_setbit($this->value, 0);
  2861. break;
  2862. case MATH_BIGINTEGER_MODE_BCMATH:
  2863. if ($this->value[strlen($this->value) - 1] % 2 == 0) {
  2864. $this->value = bcadd($this->value, '1');
  2865. }
  2866. break;
  2867. default:
  2868. $this->value[0] |= 1;
  2869. }
  2870. }
  2871. /**
  2872. * Checks a numer to see if it's prime
  2873. *
  2874. * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the
  2875. * $t parameter is distributability. Math_BigInteger::randomPrime() can be distributed across multiple pageloads
  2876. * on a website instead of just one.
  2877. *
  2878. * @param optional Math_BigInteger $t
  2879. * @return Boolean
  2880. * @access public
  2881. * @internal Uses the
  2882. * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See
  2883. * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
  2884. */
  2885. function isPrime($t = false)
  2886. {
  2887. $length = strlen($this->toBytes());
  2888. if (!$t) {
  2889. // see HAC 4.49 "Note (controlling the error probability)"
  2890. // @codingStandardsIgnoreStart
  2891. if ($length >= 163) { $t = 2; } // floor(1300 / 8)
  2892. else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
  2893. else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
  2894. else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
  2895. else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
  2896. else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
  2897. else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
  2898. else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
  2899. else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
  2900. else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
  2901. else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
  2902. else { $t = 27; }
  2903. // @codingStandardsIgnoreEnd
  2904. }
  2905. // ie. gmp_testbit($this, 0)
  2906. // ie. isEven() or !isOdd()
  2907. switch ( MATH_BIGINTEGER_MODE ) {
  2908. case MATH_BIGINTEGER_MODE_GMP:
  2909. return gmp_prob_prime($this->value, $t) != 0;
  2910. case MATH_BIGINTEGER_MODE_BCMATH:
  2911. if ($this->value === '2') {
  2912. return true;
  2913. }
  2914. if ($this->value[strlen($this->value) - 1] % 2 == 0) {
  2915. return false;
  2916. }
  2917. break;
  2918. default:
  2919. if ($this->value == array(2)) {
  2920. return true;
  2921. }
  2922. if (~$this->value[0] & 1) {
  2923. return false;
  2924. }
  2925. }
  2926. static $primes, $zero, $one, $two;
  2927. if (!isset($primes)) {
  2928. $primes = array(
  2929. 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
  2930. 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
  2931. 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
  2932. 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
  2933. 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
  2934. 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
  2935. 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
  2936. 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
  2937. 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
  2938. 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
  2939. 953, 967, 971, 977, 983, 991, 997
  2940. );
  2941. if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
  2942. for ($i = 0; $i < count($primes); ++$i) {
  2943. $primes[$i] = new Math_BigInteger($primes[$i]);
  2944. }
  2945. }
  2946. $zero = new Math_BigInteger();
  2947. $one = new Math_BigInteger(1);
  2948. $two = new Math_BigInteger(2);
  2949. }
  2950. if ($this->equals($one)) {
  2951. return false;
  2952. }
  2953. // see HAC 4.4.1 "Random search for probable primes"
  2954. if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
  2955. foreach ($primes as $prime) {
  2956. list(, $r) = $this->divide($prime);
  2957. if ($r->equals($zero)) {
  2958. return $this->equals($prime);
  2959. }
  2960. }
  2961. } else {
  2962. $value = $this->value;
  2963. foreach ($primes as $prime) {
  2964. list(, $r) = $this->_divide_digit($value, $prime);
  2965. if (!$r) {
  2966. return count($value) == 1 && $value[0] == $prime;
  2967. }
  2968. }
  2969. }
  2970. $n = $this->copy();
  2971. $n_1 = $n->subtract($one);
  2972. $n_2 = $n->subtract($two);
  2973. $r = $n_1->copy();
  2974. $r_value = $r->value;
  2975. // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
  2976. if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
  2977. $s = 0;
  2978. // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
  2979. while ($r->value[strlen($r->value) - 1] % 2 == 0) {
  2980. $r->value = bcdiv($r->value, '2', 0);
  2981. ++$s;
  2982. }
  2983. } else {
  2984. for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
  2985. $temp = ~$r_value[$i] & 0xFFFFFF;
  2986. for ($j = 1; ($temp >> $j) & 1; ++$j);
  2987. if ($j != 25) {
  2988. break;
  2989. }
  2990. }
  2991. $s = 26 * $i + $j - 1;
  2992. $r->_rshift($s);
  2993. }
  2994. for ($i = 0; $i < $t; ++$i) {
  2995. $a = $this->random($two, $n_2);
  2996. $y = $a->modPow($r, $n);
  2997. if (!$y->equals($one) && !$y->equals($n_1)) {
  2998. for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
  2999. $y = $y->modPow($two, $n);
  3000. if ($y->equals($one)) {
  3001. return false;
  3002. }
  3003. }
  3004. if (!$y->equals($n_1)) {
  3005. return false;
  3006. }
  3007. }
  3008. }
  3009. return true;
  3010. }
  3011. /**
  3012. * Logical Left Shift
  3013. *
  3014. * Shifts BigInteger's by $shift bits.
  3015. *
  3016. * @param Integer $shift
  3017. * @access private
  3018. */
  3019. function _lshift($shift)
  3020. {
  3021. if ( $shift == 0 ) {
  3022. return;
  3023. }
  3024. $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
  3025. $shift %= MATH_BIGINTEGER_BASE;
  3026. $shift = 1 << $shift;
  3027. $carry = 0;
  3028. for ($i = 0; $i < count($this->value); ++$i) {
  3029. $temp = $this->value[$i] * $shift + $carry;
  3030. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
  3031. $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL);
  3032. }
  3033. if ( $carry ) {
  3034. $this->value[count($this->value)] = $carry;
  3035. }
  3036. while ($num_digits--) {
  3037. array_unshift($this->value, 0);
  3038. }
  3039. }
  3040. /**
  3041. * Logical Right Shift
  3042. *
  3043. * Shifts BigInteger's by $shift bits.
  3044. *
  3045. * @param Integer $shift
  3046. * @access private
  3047. */
  3048. function _rshift($shift)
  3049. {
  3050. if ($shift == 0) {
  3051. return;
  3052. }
  3053. $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
  3054. $shift %= MATH_BIGINTEGER_BASE;
  3055. $carry_shift = MATH_BIGINTEGER_BASE - $shift;
  3056. $carry_mask = (1 << $shift) - 1;
  3057. if ( $num_digits ) {
  3058. $this->value = array_slice($this->value, $num_digits);
  3059. }
  3060. $carry = 0;
  3061. for ($i = count($this->value) - 1; $i >= 0; --$i) {
  3062. $temp = $this->value[$i] >> $shift | $carry;
  3063. $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
  3064. $this->value[$i] = $temp;
  3065. }
  3066. $this->value = $this->_trim($this->value);
  3067. }
  3068. /**
  3069. * Normalize
  3070. *
  3071. * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
  3072. *
  3073. * @param Math_BigInteger
  3074. * @return Math_BigInteger
  3075. * @see _trim()
  3076. * @access private
  3077. */
  3078. function _normalize($result)
  3079. {
  3080. $result->precision = $this->precision;
  3081. $result->bitmask = $this->bitmask;
  3082. switch ( MATH_BIGINTEGER_MODE ) {
  3083. case MATH_BIGINTEGER_MODE_GMP:
  3084. if (!empty($result->bitmask->value)) {
  3085. $result->value = gmp_and($result->value, $result->bitmask->value);
  3086. }
  3087. return $result;
  3088. case MATH_BIGINTEGER_MODE_BCMATH:
  3089. if (!empty($result->bitmask->value)) {
  3090. $result->value = bcmod($result->value, $result->bitmask->value);
  3091. }
  3092. return $result;
  3093. }
  3094. $value = &$result->value;
  3095. if ( !count($value) ) {
  3096. return $result;
  3097. }
  3098. $value = $this->_trim($value);
  3099. if (!empty($result->bitmask->value)) {
  3100. $length = min(count($value), count($this->bitmask->value));
  3101. $value = array_slice($value, 0, $length);
  3102. for ($i = 0; $i < $length; ++$i) {
  3103. $value[$i] = $value[$i] & $this->bitmask->value[$i];
  3104. }
  3105. }
  3106. return $result;
  3107. }
  3108. /**
  3109. * Trim
  3110. *
  3111. * Removes leading zeros
  3112. *
  3113. * @param Array $value
  3114. * @return Math_BigInteger
  3115. * @access private
  3116. */
  3117. function _trim($value)
  3118. {
  3119. for ($i = count($value) - 1; $i >= 0; --$i) {
  3120. if ( $value[$i] ) {
  3121. break;
  3122. }
  3123. unset($value[$i]);
  3124. }
  3125. return $value;
  3126. }
  3127. /**
  3128. * Array Repeat
  3129. *
  3130. * @param $input Array
  3131. * @param $multiplier mixed
  3132. * @return Array
  3133. * @access private
  3134. */
  3135. function _array_repeat($input, $multiplier)
  3136. {
  3137. return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
  3138. }
  3139. /**
  3140. * Logical Left Shift
  3141. *
  3142. * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
  3143. *
  3144. * @param $x String
  3145. * @param $shift Integer
  3146. * @return String
  3147. * @access private
  3148. */
  3149. function _base256_lshift(&$x, $shift)
  3150. {
  3151. if ($shift == 0) {
  3152. return;
  3153. }
  3154. $num_bytes = $shift >> 3; // eg. floor($shift/8)
  3155. $shift &= 7; // eg. $shift % 8
  3156. $carry = 0;
  3157. for ($i = strlen($x) - 1; $i >= 0; --$i) {
  3158. $temp = ord($x[$i]) << $shift | $carry;
  3159. $x[$i] = chr($temp);
  3160. $carry = $temp >> 8;
  3161. }
  3162. $carry = ($carry != 0) ? chr($carry) : '';
  3163. $x = $carry . $x . str_repeat(chr(0), $num_bytes);
  3164. }
  3165. /**
  3166. * Logical Right Shift
  3167. *
  3168. * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
  3169. *
  3170. * @param $x String
  3171. * @param $shift Integer
  3172. * @return String
  3173. * @access private
  3174. */
  3175. function _base256_rshift(&$x, $shift)
  3176. {
  3177. if ($shift == 0) {
  3178. $x = ltrim($x, chr(0));
  3179. return '';
  3180. }
  3181. $num_bytes = $shift >> 3; // eg. floor($shift/8)
  3182. $shift &= 7; // eg. $shift % 8
  3183. $remainder = '';
  3184. if ($num_bytes) {
  3185. $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
  3186. $remainder = substr($x, $start);
  3187. $x = substr($x, 0, -$num_bytes);
  3188. }
  3189. $carry = 0;
  3190. $carry_shift = 8 - $shift;
  3191. for ($i = 0; $i < strlen($x); ++$i) {
  3192. $temp = (ord($x[$i]) >> $shift) | $carry;
  3193. $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
  3194. $x[$i] = chr($temp);
  3195. }
  3196. $x = ltrim($x, chr(0));
  3197. $remainder = chr($carry >> $carry_shift) . $remainder;
  3198. return ltrim($remainder, chr(0));
  3199. }
  3200. // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
  3201. // at 32-bits, while java's longs are 64-bits.
  3202. /**
  3203. * Converts 32-bit integers to bytes.
  3204. *
  3205. * @param Integer $x
  3206. * @return String
  3207. * @access private
  3208. */
  3209. function _int2bytes($x)
  3210. {
  3211. return ltrim(pack('N', $x), chr(0));
  3212. }
  3213. /**
  3214. * Converts bytes to 32-bit integers
  3215. *
  3216. * @param String $x
  3217. * @return Integer
  3218. * @access private
  3219. */
  3220. function _bytes2int($x)
  3221. {
  3222. $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
  3223. return $temp['int'];
  3224. }
  3225. /**
  3226. * DER-encode an integer
  3227. *
  3228. * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
  3229. *
  3230. * @see modPow()
  3231. * @access private
  3232. * @param Integer $length
  3233. * @return String
  3234. */
  3235. function _encodeASN1Length($length)
  3236. {
  3237. if ($length <= 0x7F) {
  3238. return chr($length);
  3239. }
  3240. $temp = ltrim(pack('N', $length), chr(0));
  3241. return pack('Ca*', 0x80 | strlen($temp), $temp);
  3242. }
  3243. /**
  3244. * Single digit division
  3245. *
  3246. * Even if int64 is being used the division operator will return a float64 value
  3247. * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
  3248. * have the precision of int64 this is a problem so, when int64 is being used,
  3249. * we'll guarantee that the dividend is divisible by first subtracting the remainder.
  3250. *
  3251. * @access private
  3252. * @param Integer $x
  3253. * @param Integer $y
  3254. * @return Integer
  3255. */
  3256. function _safe_divide($x, $y)
  3257. {
  3258. if (MATH_BIGINTEGER_BASE === 26) {
  3259. return (int) ($x / $y);
  3260. }
  3261. // MATH_BIGINTEGER_BASE === 31
  3262. return ($x - ($x % $y)) / $y;
  3263. }
  3264. }