examples/factoring.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Shor's factoring algorithm\n",
    "This notebook exemplifies using [Quaspy](https://github.com/ekera/quaspy) to simulate Shor's general factoring algorithm [[Shor94]](https://doi.org/10.1109/SFCS.1994.365700), modified as in [[E24]](https://doi.org/10.1145/3655026), and with the classical post-processing in [[E21b]](https://doi.org/10.1007/s11128-021-03069-1) and [[E24]](https://doi.org/10.1145/3655026).\n",
    "\n",
    "To start off, let us pick $n$ prime factors $p_i$ uniformly at random from the set of all $l$-bit prime factors, and $n$ exponents $e_i$ uniformly at random from $[1, e_{\\max}] \\cap \\mathbb Z$, for $i \\in [1, n] \\cap \\mathbb Z$, and take the product to form\n",
    "\n",
    "$$N = \\prod_{i=1}^n p_i^{e_i}.$$\n",
    "\n",
    "To this end, we use the [<code>sample_l_bit_prime(l)</code>](../docs/math/primes/sample_l_bit_prime.md) and [<code>sample_integer(B)</code>](../docs/math/random/sample_integer.md) convenience functions provided by [Quaspy](https://github.com/ekera/quaspy)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip3 install -q quaspy # Make sure that quaspy is installed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled p1 = 143653370906962213832221125972548186993793147225256479101915841314636455570619793778626523047081772987291883621498124341980839900153849834901562866869712349175174132611303508678354099155334357961279919040223656876640707689000311229807373332776462112895002715119420109503534890125841668435156145503897816255463\n",
      "Sampled p2 = 106153134784350358413063271386813501001164923544918597765901791886784397928018190335997299057888395430750831604751690469446090993345500125851704250449550116482655100367052555882649562794487519355617787511150151335198376269039380945828047567351164548239630158998133279153268206457289372717862632786392510114069\n",
      "Sampled p3 = 148857569733497845863220175361223191316606910471581532450259055474768711371113107629205426044478994257558574595136991165136600511913029464646782231738570373037496688123539999718304459199896700908516381223386700474890146402393425991759002285418115786781334562664999448804559301844510515759781443207221888220733\n",
      "Sampled p4 = 127464129907058416852419862544206483858533127614682008274342461070998109271419538757945769429936138086254619957140745465270203917586825925647569295659605419357676733795147574470348046548264642162544402366259752825380320428341980294083966523305795128852682450340727440893984049238933040572610068173238150780573\n",
      "Sampled p5 = 130500593269878861635497728165486780483045060812770902879685935625342239165548326756881593323235329972983975146745738971624607372491212039011871250072685837925537036408239013280821351637274112077162351031677017624841652747772835987749784749997453168800269127690306410203195465163642584594761429738362705879243\n",
      "Sampled p6 = 177533731264587152889112801442700692959945228382752809275658894322845353310784720857215112219935806595928410810449047881109078925761191610481091255082896634138470637785770750427073834998264948783499289515464398777150229911251276698680004792613669184715267553954460485390289098187481557844662344332446058112049\n",
      "Sampled p7 = 153002907362889260188667429205566457072628243080067924318126480508262058127483362077728830631609578558105072787402714266565572578343146969539183854639748152640858511084059086685537187537186511162892257678879586392818722835192911749106742990532526075107597854289990819041480653963928157238876664948836595442181\n",
      "Sampled p8 = 119195687971922021372621191918058656854608926398271465007706405405764738065574471569348699030790937620461898813512366013331472104865637642884426948120456066512227210065116929693142650859173542010450981698211698894742228497478450587004379236830271423868055749443652299272623654486186450881748620911153631093189\n",
      "Sampled p9 = 149804245573510945324970721367576067743105197900625084885333725155216226080363724205737276405911779750500118703557654733975314587200486261827663016404491919671703847335369937542584717321974925756113573249968302322191948935246573646832762563293279359138145576961804490231305998228345387305189451715728757600763\n",
      "Sampled p10 = 140749726575732377709605185342331185547632858177534582982016751215130071154534867461948801759250518252372697406764832912764182010835897141581780663294530852798633759891819858555377278388898769298561742603774296359482921908337674123565202383263229945266402028912487961446359719317891278662032975830976681512637\n",
      "\n",
      "Computed N = 2577702731674256727908989108867287762496455253394808216505304982114166879928648868859608787482159820250835021875020322646170792011468311118875092081819825629115449833849073280910644993089112634324776406603839976127522437802582120184119424212952074175727745248404034628808880875832043815805464866013356072887266643484367382868748776650155797258609684515466437448867637803940104737380235460845103439723295121620180645328985270056085386333593255728755520165918386153783903681417774339223007187169465674633626774010977971920773936265860065699908144511231787928321137949698346601772397761065646499608838139662800520313469366273553292200882897150832928023348413419330416712169142418855591951833953695459030196544789795204067128497410873834468750275895878812319886566539413556201606040724779322498317284835380525231301540489762030165953347318192480143990407657256822017231603244187555481040555487706151035581949449147149460318876799398664846002510558978569020013336262667312569401769671613782689673490858555069322936649049721854107600758400698856422298883143232714351865551699750694189905337825389734188954060902962388222439241192765492176699323840307390124297164207262296087362013211351494700810815931905452790499176066873539126227166008920303814680945465448566512683486222302310602082940775281401475294849234122480810639865085912473171684753686385166461780923987274566300459535005551755909676273426285183111330780195080443689114271421029844763739041384320039697075853780290995155374780657054986758950045560360311354164056928321492540812108743938027425529298412985469723764821975723588174467388572538215417536804442763808629600137471743993543085729399490098487951514939745054076273237927045295187277464884457210532550594786452596478555814282155137487703680522438450614149988524309996192605976518294950048103886062922491671675021539799619492868989323285958423614244463505223657791035444762452312106531242380031139771836927922762803487228004810306629371481648031436051417703187485021968557145044897990134115075713476586796023689199949977323210124415669370428238113478889824710546377044359669593106102596797781045074986579242062983934437266765888215548144974535574890079330237920283572562846044648661606416097954093587683337804901661868705537420616368687985715151480353483671819098249768967863646192528082005862626026085998927209004285703558578922275797787382967956262792588675296770353520709126641808906960082920130493327747930036422420689821708486613921534310086775043395617195792667404405306215116066780462996509953166780869317824026971152651544093208458857557580198418384358711788556521088463194168771548306788254995587632760566890292987254102189937949740873780733769515212286025671970708637607625937421056501172000688939682471442290314275249657262779468858900468978101116663905808044737197249170975375544459626688367682873852277937194473249432670509469246122507146265033193025038115925044419541555569925154310299874287899277288066932571645723886848239650324516236794933349896840272125888795433618220947155153962865782710691878546375008105574172817578958219719083702525902829844162423919\n"
     ]
    }
   ],
   "source": [
    "from quaspy.math.primes import sample_l_bit_prime;\n",
    "from quaspy.math.random import sample_integer;\n",
    "\n",
    "from math import prod;\n",
    "\n",
    "n = 10;\n",
    "l = 1024;\n",
    "e_max = 1;\n",
    "\n",
    "factors = [];\n",
    "primes = set();\n",
    "\n",
    "while len(factors) < n:\n",
    "  pi = sample_l_bit_prime(l);\n",
    "  ei = sample_integer(e_max) + 1;\n",
    "\n",
    "  if pi not in primes:\n",
    "    primes.add(pi);\n",
    "    factors.append([pi, ei]);\n",
    "\n",
    "    print(\"Sampled p\" + str(len(factors)) + \" =\", pi);\n",
    "\n",
    "N = prod([pi ** ei for [pi, ei] in factors]);\n",
    "\n",
    "print(\"\\nComputed N =\", N);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Simulating order finding in $\\mathbb Z_N^*$ exactly to sample $r$\n",
    "[Quaspy](https://github.com/ekera/quaspy) provides a function [<code>sample_r_given_N(N, factors)</code>](../docs/factoring/sampling/sample_r_given_N.md) for exactly sampling an element $g$ uniformly at random from $\\mathbb Z_N^*$ and returning its order without explicitly computing and returning $g$. This function requires that the factorization of $N$ is known, as is the case here given that we selected the factors of $N$.\n",
    "\n",
    "Below, we use this function to simulate the initial classical pre-processing step of Shor's algorithm where an element $g$ is selected uniformly at random from $\\mathbb Z_N^*$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled r = 363328042643605888539115171004196443395278889632690559996824944777545992284574303996138757621590086314636141370527481870914096970173200133627434771692717854403236826190609170391804093614411512957332449375739343117825723898014221683903525020431944319918741342775111232812257914407092514201301463886719278970660495249679080362141698773884401817703450110019532819103625137943022931157521302640436553623181676450143860561597855429632465470800413724240659491640669869050434344653883388513422914698655297312164057173650328882712983445279965886013233887837929645561964601939184548201381923025361901164375400559912170875681745610167480039059425795644024812838861988306443453178701325842794737348579011549541638242825028081360917419174142987402512841346460718294992360614579455226717013782034401992432164352498301528481366394347182553223217455233184165456843789931572214672482059804759630186854188750807441498156739919637529326164010457936226702139878243136814870563841076069812250252265957372766518360718301715393334966645747171034896995732705663884787225034642033459140328643681075388757287772805450241373125002357427726778344627000475862366809697923887900180983291682053350676500882580074609136412269830053123284539787450458501385875103269539842912760536212616073555797878646064730963263504938306698053246560876300812949172063153807002286262435805514368433935922202642037547595773425094882661982431121568953804797261465273504215532076875589993382576069359212733120937922028177514832403612953922682761272544798674075035024080046765724023142367296465752144649462095681968335339115235923644803364171322248730043983239362292974171517059268359721927564851630618275165035865649216727305293799095485913951302913041996126105344820537063690948300627644565217756017593634849618561650511147697751535043254208303001347419273520648956179567392648244610081313679019197317926830544324916630343452851150285354058205724220068026013582172134484781124771223371767580279937436028531744563606186390536907178646062603624654491065560331735410440429250230234617863031112296799934317349045124458717745155479761842833101897093232298617037981761571053225567289915799966706786969608294469113213945768855395980473539902515560937121848970073017301564277783955492285917677297578516153863553314036099525393686516608702052389574420713911882548387018205293832407865830328367421174901452242457332924746205817162042612533173379427753245637371773031407525420809937150927479282147121241922908445813509913580151351460212352179842238490906545839057806159276010781558264610874655683476143357253417639900926598622319622957502186857428241926994032682172072400912252427827374350858813828832530571276105561586546374285783015758527366731500830459538566193657835672261422915912816992370704695680227461606655120608145806456261041018628037262551278199656501435889739590885313194660416940460631480871676717099173851577723289886414333486164495399269814059622244785602895451160315724887122295550687123438862859218726666543113279083510675701871647384421285862852453914861466792279562217447785312615332706550242027157441459912085680\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.sampling import sample_r_given_N;\n",
    "\n",
    "r = sample_r_given_N(N, factors);\n",
    "\n",
    "print(\"Sampled r =\", r);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1. Solving $r$ for the complete factorization of $N$\n",
    "We may then use the [<code>solve_r_for_factors(r, N, ..)</code>](../docs/factoring/general/postprocessing/ekera/solve_r_for_factors.md) function provided by [Quaspy](https://github.com/ekera/quaspy) to solve $r$ for the factors of $N$ by using the post-processing from [[E21p]](https://doi.org/10.1007/s11128-021-03069-1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for the prime factors yielded: {148857569733497845863220175361223191316606910471581532450259055474768711371113107629205426044478994257558574595136991165136600511913029464646782231738570373037496688123539999718304459199896700908516381223386700474890146402393425991759002285418115786781334562664999448804559301844510515759781443207221888220733, 127464129907058416852419862544206483858533127614682008274342461070998109271419538757945769429936138086254619957140745465270203917586825925647569295659605419357676733795147574470348046548264642162544402366259752825380320428341980294083966523305795128852682450340727440893984049238933040572610068173238150780573, 119195687971922021372621191918058656854608926398271465007706405405764738065574471569348699030790937620461898813512366013331472104865637642884426948120456066512227210065116929693142650859173542010450981698211698894742228497478450587004379236830271423868055749443652299272623654486186450881748620911153631093189, 143653370906962213832221125972548186993793147225256479101915841314636455570619793778626523047081772987291883621498124341980839900153849834901562866869712349175174132611303508678354099155334357961279919040223656876640707689000311229807373332776462112895002715119420109503534890125841668435156145503897816255463, 130500593269878861635497728165486780483045060812770902879685935625342239165548326756881593323235329972983975146745738971624607372491212039011871250072685837925537036408239013280821351637274112077162351031677017624841652747772835987749784749997453168800269127690306410203195465163642584594761429738362705879243, 177533731264587152889112801442700692959945228382752809275658894322845353310784720857215112219935806595928410810449047881109078925761191610481091255082896634138470637785770750427073834998264948783499289515464398777150229911251276698680004792613669184715267553954460485390289098187481557844662344332446058112049, 149804245573510945324970721367576067743105197900625084885333725155216226080363724205737276405911779750500118703557654733975314587200486261827663016404491919671703847335369937542584717321974925756113573249968302322191948935246573646832762563293279359138145576961804490231305998228345387305189451715728757600763, 153002907362889260188667429205566457072628243080067924318126480508262058127483362077728830631609578558105072787402714266565572578343146969539183854639748152640858511084059086685537187537186511162892257678879586392818722835192911749106742990532526075107597854289990819041480653963928157238876664948836595442181, 140749726575732377709605185342331185547632858177534582982016751215130071154534867461948801759250518252372697406764832912764182010835897141581780663294530852798633759891819858555377278388898769298561742603774296359482921908337674123565202383263229945266402028912487961446359719317891278662032975830976681512637, 106153134784350358413063271386813501001164923544918597765901791886784397928018190335997299057888395430750831604751690469446090993345500125851704250449550116482655100367052555882649562794487519355617787511150151335198376269039380945828047567351164548239630158998133279153268206457289372717862632786392510114069}\n",
      "\n",
      "[ OK ] All prime factors of N were successfully recovered.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.general.postprocessing.ekera import solve_r_for_factors;\n",
    "\n",
    "result = solve_r_for_factors(r, N);\n",
    "\n",
    "print(\"Solving for the prime factors yielded:\", result);\n",
    "\n",
    "if result == primes:\n",
    "  print(\"\\n[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"\\n[FAIL] The integer N was not completely factored.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Simulating the quantum part of Shor's order-finding algorithm to sample $j$\n",
    "[Quaspy](https://github.com/ekera/quaspy) provides a function [<code>sample_j_given_r(r, m, l, ..)</code>](../docs/orderfinding/general/sampling/sample_j_given_r.md) for simulating Shor's order-finding algorithm exactly (up to arbitrary precision) for a given order $r$. Below, we use the this function to simulate running the algorithm for $r$ with a control register of $m + \\ell$ bits.\n",
    "\n",
    "This yields a frequency $j$ sampled from the probability distribution induced by the algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled j = 3160961445531119556362965420807833999374700957411031200654687182663060613987651314002548228811683536204147728357433187924295281432472716493529402843679653944565220812485775295582002246658927980399253682030559880936352054705396152287121557783407831473607066207309361269342837503696532313813567368585544848559799782320876707169188235802012880524125291020684633958487706675423410577525010193321335248901923680443408569560799181428950356287236228100503890224348902188372469588796219591759727423169531719057054488434577846835534589724771404308631841363932050310009334388818715265425680635884397804639910183364673395056533208249520337629366630810025452712521657407719536331091392074550134630036934315964909197074055189716487369659992949580968776794281638832520378407419702241017071365035433641184599352858191450725206313268840460483164441343965191634324392890813851191134857396882245284056572408750987118629143356360968421508005723512832199885804157707585876079878643391798311547478508913719995252730182898246842271594171398268267884765953908225627940727487877652626860161007913777229212209278128802036360558902178068861631704759460766587194075699188801882742668756936999332428874600854648749290515599149244595041217152778032157129664974303308282345924677352688951875422193417563088256739382071556824158836905192204526966438005102781678491817727745900888822500505099696288793228904854186060196194873033536809846408379196022420556564976590818015590135909315590583503188407534764905706327587633788800801268972441977984141689284714995687363122666557146967812544044548739539083754629019395228888918187015851615980924156942132295262098040019369442422316393684617272848606026100968047743730782106270211183475056953367237074252004316966723193124235926622486678538647799742780113299038322280470135285511675735691215239839969573314474160564733330182203467248629576340457029235583760783241373463139180212314597285858146323191857299553586640610446282779999821023502680774964465057786128572595775457484758552219734230993391711229456799894919439948006368895997572179600841455574787053211272700507351051551539229774336033669349248439357373422933443577266402974570058061960814947388256161578070225442668333817074809937553220864373421969281458243239229779796622552857540404311338257891900251519209004184367848198203153225958828399962334754517743383687998668269040303487285258126995357337689630032640473467351252830596907536054183005041752234796184269734785657496586906156249233440509517759203961666087424320690345737438841069809076848710709490643706509123508510417553045484870698122886247683940739280967544073454201151863677627452523614281276278663096974662755263574249254268959803325561100363847290456687969815852678643873047365153339449059101664096227841347736804542753467555279517503495661702484651014189102745923623314668686761709725220906611754579268510869373916481130653398132589946278289580343154172264325126974162779953997516029755394617929261782545000840782724162372905795141645547586614311543985300843917554876009736106625810559886854925888646138191657162771833048784750411897648093866306207242288439371828291441971759662778147146875458010994694606209013379068059816480276028097902123307330036031159224299649158064091913938045702698374582149969565698871813015197197894242259815544326980309349423009427375214324824588670137326160939335808197745302212656358491723492754625145407152412644621686477703471486400611409966750618343614320529241456417177729645530416288514037184502889293634388337929332719923124979827739238285747758640853370416836289314550269652982335468326372835797110512608380904745923537316426226487812964251923163276039380058103667500057091281382050076184567421994548440820002066189756252902409141659685532452522208209042339012515090357316006218504331659814986695128259416955628278592434239616175065766073417253887975356572350471572801605813809469400053015642872283806927819439201491551090914031741027164288606097519896019518171737312444342521462801629727644806831769953070234548173678185578377391436008225208117930012875751127025919489142568318094008809796586648732525397831612637263967522247840550871260705399746544349587238859758572282750084736410360328413272504304260267665381636315996301220969225972485278018156118429183649569662871400467999988734127988300473275732001528917251671743304976652056402167979768730299218714369218496293558735230667887562558425411263006149806395604565644891359350583803381493141880294892051268473897577851357971332973524894467964732534064136555494748229318961954193981520429259152454566021648587119121960273921829888317868159253052001001066192746532295438122174221901865957842955899287143409681126791320385128381549502205829240150214522493914457345892270140953118717798789443275158989515196151488903600669233538093535604078028275180425514372614694392337634259860416558444048430332199569169405428989716019514606193249807366310729438040684851094175661063965931766850304125990887244641323808193574219779248841679129653623951149167729284576201381762563452515306881118901159632714943171922019531625833041979708973384759791825056678203045290730264594757760444803081811460655588978721525883347576356388589824833243003939800387243605219079343404109187673440473858298609206986838620209447583363710982962149196524374527663235504668372509644106945951060492010766370334989118958682824781726423378822358949297255396737165190138190591269749815965449294692774968782740065605601900033658765476200155266882595921173752026098936701052964669069181067256511553097241600596339701891513959582956839459564218132656596459132585772696726549383882706453854570020348016460732157695242337664975099628451605618048189795331756000934296862134036486181042375933467684707624207646840480996555721221639741424832006000168259998630011088684287362731105473263412467985961179389756891133973178383709637031695269741170172038198705291353759405189454151581621574617425453505827428972335792192846324768562287660411055559533323935682805442279246542051931626616083992754229457486630623306621050010349275807245402978124438265013587449720347681739081847313697770308949024863877563781284553532143307264849002393484560118437835531928635655860199466417861189992599702604963461131\n"
     ]
    }
   ],
   "source": [
    "from quaspy.orderfinding.general.sampling import sample_j_given_r;\n",
    "\n",
    "m = N.bit_length() - 1;\n",
    "l = m; # Ensures that r^2 < 2^(m + l) as r < 2^m;\n",
    "\n",
    "j = sample_j_given_r(r, m, l);\n",
    "\n",
    "print(\"Sampled j =\", j);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1. Solving $j$ for the complete factorization of $N$\n",
    "We now proceed to solve $j$ for the factors of $N$.\n",
    "\n",
    "To this end, we first use the [SimulatedCyclicGroupElement](../docs/math/groups/SimulatedCyclicGroupElement.md) class provided by [Quaspy](https://github.com/ekera/quaspy) to define a group element $g$ of order $r$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from quaspy.math.groups import SimulatedCyclicGroupElement;\n",
    "\n",
    "g = SimulatedCyclicGroupElement(r);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may then e.g. use the [<code>solve_j_for_factors(j, m, l, g, N, ..)</code>](../docs/factoring/general/postprocessing/ekera/solve_j_for_factors.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy) to first solve $j$ for a positive integer multiple of $r$ using the lattice-based post-processing from [[E24]](https://doi.org/10.1145/3655026), and to then solve $r$ for the prime factors of $N$ using the post-processing in [[E21p]](https://doi.org/10.1007/s11128-021-03069-1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for the prime factors yielded: {148857569733497845863220175361223191316606910471581532450259055474768711371113107629205426044478994257558574595136991165136600511913029464646782231738570373037496688123539999718304459199896700908516381223386700474890146402393425991759002285418115786781334562664999448804559301844510515759781443207221888220733, 127464129907058416852419862544206483858533127614682008274342461070998109271419538757945769429936138086254619957140745465270203917586825925647569295659605419357676733795147574470348046548264642162544402366259752825380320428341980294083966523305795128852682450340727440893984049238933040572610068173238150780573, 119195687971922021372621191918058656854608926398271465007706405405764738065574471569348699030790937620461898813512366013331472104865637642884426948120456066512227210065116929693142650859173542010450981698211698894742228497478450587004379236830271423868055749443652299272623654486186450881748620911153631093189, 143653370906962213832221125972548186993793147225256479101915841314636455570619793778626523047081772987291883621498124341980839900153849834901562866869712349175174132611303508678354099155334357961279919040223656876640707689000311229807373332776462112895002715119420109503534890125841668435156145503897816255463, 130500593269878861635497728165486780483045060812770902879685935625342239165548326756881593323235329972983975146745738971624607372491212039011871250072685837925537036408239013280821351637274112077162351031677017624841652747772835987749784749997453168800269127690306410203195465163642584594761429738362705879243, 177533731264587152889112801442700692959945228382752809275658894322845353310784720857215112219935806595928410810449047881109078925761191610481091255082896634138470637785770750427073834998264948783499289515464398777150229911251276698680004792613669184715267553954460485390289098187481557844662344332446058112049, 149804245573510945324970721367576067743105197900625084885333725155216226080363724205737276405911779750500118703557654733975314587200486261827663016404491919671703847335369937542584717321974925756113573249968302322191948935246573646832762563293279359138145576961804490231305998228345387305189451715728757600763, 153002907362889260188667429205566457072628243080067924318126480508262058127483362077728830631609578558105072787402714266565572578343146969539183854639748152640858511084059086685537187537186511162892257678879586392818722835192911749106742990532526075107597854289990819041480653963928157238876664948836595442181, 140749726575732377709605185342331185547632858177534582982016751215130071154534867461948801759250518252372697406764832912764182010835897141581780663294530852798633759891819858555377278388898769298561742603774296359482921908337674123565202383263229945266402028912487961446359719317891278662032975830976681512637, 106153134784350358413063271386813501001164923544918597765901791886784397928018190335997299057888395430750831604751690469446090993345500125851704250449550116482655100367052555882649562794487519355617787511150151335198376269039380945828047567351164548239630158998133279153268206457289372717862632786392510114069}\n",
      "\n",
      "[ OK ] All prime factors of N were successfully recovered.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.general.postprocessing.ekera import solve_j_for_factors;\n",
    "\n",
    "result = solve_j_for_factors(j, m, l, g, N);\n",
    "\n",
    "print(\"Solving for the prime factors yielded:\", result);\n",
    "\n",
    "if result == primes:\n",
    "  print(\"\\n[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"\\n[FAIL] Failed to completely factor the integer N.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may also solve in two steps, by first calling [<code>solve_j_for_r(j, m, l, g, ..)</code>](../docs/orderfinding/general/postprocessing/ekera/solve_j_for_r.md) to first solve $j$ for a positive integer multiple of $r$ using the lattice-based post-processing from [[E24]](https://doi.org/10.1145/3655026), and by then calling [<code>solve_r_for_factors(r, N, ..)</code>](../docs/factoring/general/postprocessing/ekera/solve_r_for_factors.md) to solve $r$ for the prime factors of $N$ using the post-processing in [[E21p]](https://doi.org/10.1007/s11128-021-03069-1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving j for a multiple r' of the order r yielded: 363328042643605888539115171004196443395278889632690559996824944777545992284574303996138757621590086314636141370527481870914096970173200133627434771692717854403236826190609170391804093614411512957332449375739343117825723898014221683903525020431944319918741342775111232812257914407092514201301463886719278970660495249679080362141698773884401817703450110019532819103625137943022931157521302640436553623181676450143860561597855429632465470800413724240659491640669869050434344653883388513422914698655297312164057173650328882712983445279965886013233887837929645561964601939184548201381923025361901164375400559912170875681745610167480039059425795644024812838861988306443453178701325842794737348579011549541638242825028081360917419174142987402512841346460718294992360614579455226717013782034401992432164352498301528481366394347182553223217455233184165456843789931572214672482059804759630186854188750807441498156739919637529326164010457936226702139878243136814870563841076069812250252265957372766518360718301715393334966645747171034896995732705663884787225034642033459140328643681075388757287772805450241373125002357427726778344627000475862366809697923887900180983291682053350676500882580074609136412269830053123284539787450458501385875103269539842912760536212616073555797878646064730963263504938306698053246560876300812949172063153807002286262435805514368433935922202642037547595773425094882661982431121568953804797261465273504215532076875589993382576069359212733120937922028177514832403612953922682761272544798674075035024080046765724023142367296465752144649462095681968335339115235923644803364171322248730043983239362292974171517059268359721927564851630618275165035865649216727305293799095485913951302913041996126105344820537063690948300627644565217756017593634849618561650511147697751535043254208303001347419273520648956179567392648244610081313679019197317926830544324916630343452851150285354058205724220068026013582172134484781124771223371767580279937436028531744563606186390536907178646062603624654491065560331735410440429250230234617863031112296799934317349045124458717745155479761842833101897093232298617037981761571053225567289915799966706786969608294469113213945768855395980473539902515560937121848970073017301564277783955492285917677297578516153863553314036099525393686516608702052389574420713911882548387018205293832407865830328367421174901452242457332924746205817162042612533173379427753245637371773031407525420809937150927479282147121241922908445813509913580151351460212352179842238490906545839057806159276010781558264610874655683476143357253417639900926598622319622957502186857428241926994032682172072400912252427827374350858813828832530571276105561586546374285783015758527366731500830459538566193657835672261422915912816992370704695680227461606655120608145806456261041018628037262551278199656501435889739590885313194660416940460631480871676717099173851577723289886414333486164495399269814059622244785602895451160315724887122295550687123438862859218726666543113279083510675701871647384421285862852453914861466792279562217447785312615332706550242027157441459912085680\n",
      "\n",
      "[ OK ] A multiple r' of the order r was successfully recovered.\n",
      "\n",
      "Solving r for the complete factorization of N yielded: {148857569733497845863220175361223191316606910471581532450259055474768711371113107629205426044478994257558574595136991165136600511913029464646782231738570373037496688123539999718304459199896700908516381223386700474890146402393425991759002285418115786781334562664999448804559301844510515759781443207221888220733, 127464129907058416852419862544206483858533127614682008274342461070998109271419538757945769429936138086254619957140745465270203917586825925647569295659605419357676733795147574470348046548264642162544402366259752825380320428341980294083966523305795128852682450340727440893984049238933040572610068173238150780573, 119195687971922021372621191918058656854608926398271465007706405405764738065574471569348699030790937620461898813512366013331472104865637642884426948120456066512227210065116929693142650859173542010450981698211698894742228497478450587004379236830271423868055749443652299272623654486186450881748620911153631093189, 143653370906962213832221125972548186993793147225256479101915841314636455570619793778626523047081772987291883621498124341980839900153849834901562866869712349175174132611303508678354099155334357961279919040223656876640707689000311229807373332776462112895002715119420109503534890125841668435156145503897816255463, 130500593269878861635497728165486780483045060812770902879685935625342239165548326756881593323235329972983975146745738971624607372491212039011871250072685837925537036408239013280821351637274112077162351031677017624841652747772835987749784749997453168800269127690306410203195465163642584594761429738362705879243, 177533731264587152889112801442700692959945228382752809275658894322845353310784720857215112219935806595928410810449047881109078925761191610481091255082896634138470637785770750427073834998264948783499289515464398777150229911251276698680004792613669184715267553954460485390289098187481557844662344332446058112049, 153002907362889260188667429205566457072628243080067924318126480508262058127483362077728830631609578558105072787402714266565572578343146969539183854639748152640858511084059086685537187537186511162892257678879586392818722835192911749106742990532526075107597854289990819041480653963928157238876664948836595442181, 149804245573510945324970721367576067743105197900625084885333725155216226080363724205737276405911779750500118703557654733975314587200486261827663016404491919671703847335369937542584717321974925756113573249968302322191948935246573646832762563293279359138145576961804490231305998228345387305189451715728757600763, 140749726575732377709605185342331185547632858177534582982016751215130071154534867461948801759250518252372697406764832912764182010835897141581780663294530852798633759891819858555377278388898769298561742603774296359482921908337674123565202383263229945266402028912487961446359719317891278662032975830976681512637, 106153134784350358413063271386813501001164923544918597765901791886784397928018190335997299057888395430750831604751690469446090993345500125851704250449550116482655100367052555882649562794487519355617787511150151335198376269039380945828047567351164548239630158998133279153268206457289372717862632786392510114069}\n",
      "\n",
      "[ OK ] All prime factors of N were successfully recovered.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.orderfinding.general.postprocessing.ekera import solve_j_for_r;\n",
    "from quaspy.factoring.general.postprocessing.ekera import solve_r_for_factors;\n",
    "\n",
    "rp = solve_j_for_r(j, m, l, g, accept_multiple=True);\n",
    "\n",
    "print(\"Solving j for a multiple r' of the order r yielded:\", rp);\n",
    "\n",
    "if (rp != 1) and (r % rp == 0):\n",
    "  print(\"\\n[ OK ] A multiple r' of the order r was successfully recovered.\");\n",
    "\n",
    "  result = solve_r_for_factors(r, N);\n",
    "\n",
    "  print(\"\\nSolving r for the complete factorization of N yielded:\", result);\n",
    "\n",
    "  if result == primes:\n",
    "    print(\"\\n[ OK ] All prime factors of N were successfully recovered.\");\n",
    "  else:\n",
    "    print(\"\\n[FAIL] Failed to completely factor N.\");\n",
    "\n",
    "else:\n",
    "  print(\"\\n[FAIL] Failed to recover a multiple r' of the order r.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Simulating order finding in $\\mathbb Z_N^*$ heuristically to sample $g$ and $r$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to the [<code>sample_r_given_N(N, factors)</code>](../docs/factoring/sampling/sample_r_given_N.md) function used above, [Quaspy](https://github.com/ekera/quaspy) also provides a function [<code>sample_g_r_given_N(N, N_factors, ..)</code>](../docs/factoring/sampling/sample_g_r_given_N.md) for sampling an element $g$ uniformly at random from $\\mathbb Z_N^*$ and heuristically computing and returning its order $r$ alongside $g$.\n",
    "\n",
    "This function requires that the factorization of $N$ is known, as is the case here given that we selected the factors of $N$. (If the function is also fed the factorization of $p_i - 1$ for $i \\in [1, n] \\cap \\mathbb Z$ then the function can be made exact, as explained in the [documentation](../docs/factoring/sampling/sample_r_given_N.md).)\n",
    "\n",
    "Below, we use this function to simulate the initial classical pre-processing step of Shor's algorithm where an element $g$ is selected uniformly at random from $\\mathbb Z_N^*$. This yields $g$ and $r$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled g = 1956784174782571763124417858413159841782231448975404652285046468985053650796816292135414151692805034547734824940562834816531148729196930660385167999687024324301549538986131664613213854542579058624320099944365518681984629502886306874482335568228244448630221539575092628804213620639613669890242727813260696401780665078822742813021702391277848571410419083108573083612603410198625739336663546021566954367969640842723478223372009299835000131914347702141219709874473929007439757755789480832333869367117215279128072620195108232568550692654989249278817841648832878267624909023272361966257253579600879787170115789271176894645267050603216415744432799946537814430439049522098743836927071510060712085577213863825611157685049691752507960238616463915038942491670085048968377388939588080944858125629915174778709666299650473167690003354094997673284663322043376393336333181543736022454637923030031469450760833278039054358483813710230123658643988350055323324552169123350923366880290829488256087880417362520795051055112961020184022949967696584962402090245409863746549240321749445893389267978139263972872029343625644880044146194208096309322535347568606524659029827210705836020829388969314551222494112135239902112719111250295334663565126650260802967894602909277326856799514536410308645707502488496880420470488615337697911006766570818399836743280445633938370074635299471386561310127983956566300026779846842480096200195335352294428050984654217595835598242932244288685260796612365471239361636194480729848328512942290685668709095266052644171596495444446702793886202553660440514267756370720041829563362819431515466953140351404312569300394873369295145961299457278546895310152236072992856120354409948948237119030579951464224928605792599435081668070263627972692081134253026987373150111485522303036270381818580047642873521927796746760536815431695161191209835990222540973440710660450432829338053020936021453376798910340049737336321210917505403388161782906821985906057963666135931215104908122894571414642097548504730035891863742983703897543928518773026953896578878266400952277780549384379843449574936972951875287449161539462933498544622692464737458277348622375663061909783981617720545359733607487977729421310442759607652860438748840451565788323967800490083797557338110066883792661041728672608744022346131809596269055783571140016446844430729091131592588223572783777605992992797070301447828883129272929833601196274555503438701606023400848503540584647876167467645929681650012078617852711053039271685901352873745248395840082913952765253019561685301129756976077654784758454705154350791377872645854316332756028646033803746804324282549488278699229408733164030546640460102809954165693490521786854803162285030759342009010950516588390990153965734412941270402149125530149889449078885167425028318370393016654919409057586511341921789945464832625951043372025413107299786514391638986897805157232426074157789619838215981447076785626479231840373867635602402006064291829212553315542223313092320244977970210684779928773734927666179644277296289561723793670750384408343901043285382243965706029332991729400243707606617716916943171870055 \n",
      "\n",
      "Sampled r = 999152117269916193482566720261540219337016946489899039991268598138251478782579335989381583459372737365249388768950575145013766667976300367475445622154974099608901272024175218577461257439631660632664235783283193574020740719539109630734693806187846879776538692631555890233709264619504414053579025688478017169316361936617470995889671628182104998684487802553715252534969129343313060683183582261200522463749610237895616544394102431489280044701137741661813602011842139888694447798179318411913015421302067608451157227538404427460704474519906186536393191554306525295402655332757507553800288319745228202032351539758469908124800427960570107413420938021068235306870467842719496241428646067685527708592281761239505167768827223742522902728893215356910313702766975311228991690093501873471787900594605479188451969370329203323757584454752021363848001891256455006320422311823590349325664463088983013849019064720464119931034779003205646951028759324623430884665168626240894050562959191983688193731382775107925491975329717331671158275804720345966738264940575683164868845265592012635903770122957319082541375214988163776093756482926248640447724251308621508726669290691725497704052125646714360377427095205175125133742032646089032484415488760878811156533991234568010091474584694202278444166276678010148974638580343419646428042409827235610223173672969256287221698465164513193323786057265603255888376919010927320451685584314622963192469029502136592713211407872481802084190737835016082579285577488165789109935623287377593499498196353706346316220128605741063641510065280818397786020763125412922182566898790023209251471136184007620953908246305678971671912987989235300803341984200256703848630535346000089557947512586263366083010865489346789698256476925150107826726022554348829048382495836451044538905656168816721368949072833253705403002181784629493810329782672677723612617302792624298783996893520733444495340663284723660065741605187071537350973369833148093120864272360845769827949078462297549917012573976494741276672159967799850430290912272378711180438133145199123335558816199819372709874092261473799177569345067791030217006388821196854449844320396370310047268449908443664166422809790061338350864352338946302234731917792577085084667700797579301763905877603786273612568340919423124771613599273694832637920673930644071329656963257677008064300064558039121631033403010408230978993666757665543052065997195617184466226793426321425502772375836370694907227327165050568025904583415287998225987152262345416216515583968494566155849993001057408966938009029649285227679905303129559394232446898509727548146211378963133131013857927665299233589875973199102508694176525279464861738029289459071009290294363002529285903293335950258511627283763731057032559048098718913018760246729019437913120625519418301581672400967754717862801227102472016015049055378948696783874934611285316146586266736572397110972022728091838739047187639417086952362347991988663961173160407962490690868243439586312764389589456872862851498332993561517479654358180147030307158536122844248265869033678768796097981409609692164943013165574682964014758235620 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.sampling import sample_g_r_given_N;\n",
    "\n",
    "[g, r] = sample_g_r_given_N(N, factors);\n",
    "\n",
    "print(\"Sampled g =\", g, \"\\n\");\n",
    "print(\"Sampled r =\", r, \"\\n\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1. Simulating the quantum part of Shor's order-finding algorithm to sample $j$\n",
    "[Quaspy](https://github.com/ekera/quaspy) provides a function [<code>sample_j_given_r(r, m, l, ..)</code>](../docs/orderfinding/general/sampling/sample_j_given_r.md) for simulating Shor's order-finding algorithm exactly (up to arbitrary precision) for a given order $r$. Below, we use the this function to simulate running the algorithm for $r$ with a control register of $m + \\ell$ bits.\n",
    "\n",
    "This yields a frequency $j$ sampled from the probability distribution induced by the algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled j = 79762211419653412818345814480677198019988679196076485997417789043330760821219698778385105244977958476739848870418395949181785439325020800877898693387194657461968247073162740262711649794955496697965571010375276431380274058525957007857198788187089401053929293687338353460765882330303633012426614807866658206256489138418600810487026804686094999210593866204545057591267513377307308508080975770027084883561919099341170709197645389977966274550339873003855458872971870380687371532610147333228982904932388584287544765155235899271431853285852419073231273033521180023386069246341692987355893821875795144725479754862969701095249047437854931448615010622367657025459775771153791830895377949229368596042335094461106853314294368010489577591589132567536341456630482762502580144206559920957753405930384874387098809635065891057224629052205514948805516036701203589822590203841459796616812767755728485358124924654358511091380347377964098018427773136327938712047361489815021230696304147236894506186237828325526153625066181219929609655842898738452982371470890300256442118147694574906057063856285044010822549017005795825742956448033540504037379458585265717939102366737197259711180732900104934733318760092307557423779501448242989278858886178950169617381177926217048941627833705902986115227434379279802696410317124851732983237049773991478187374856986385927251372842888189707814971549991402737284153603704794249866533134798706267470220770680844998583310989021021568260714533955766196701646683646442569338962883665711645447904012153306746171437979635213184144421329219526982747674525887928103246678435600480722470279567564843581176336232732049385052931390712937602589003865960053581882930763250844485378264795866900733275222157643388458055996835003119701706521485383496665266719292517839643480621115111433605257771417004823875673852987022381685984891478827793844587686871174633278814999765058144900271219062393161973849518733397772296491175865740993010800422684946834500275818747635527661372602577897801198179446619620906536003732660628655097101203204252256797721999405933549748437779183843362621310927208541150810263594283129112014211622205649900816275060163470376087797654647563346619118372422562901050856607635233264683625884167317319403662692430740872875506736992988451882008574033618695077255193984957219588105426106686919741936745287062333826136805064106412971988931800546504731560750840347800227732719958688262080877087347478921041870019491193607401510090516871269187643302261850216024344087813859958608232876346651458100246731837388574005045049769313857948735820639856867473627769683283173357539530019058314289655302936616698608029724297724696956700135010194291202413691062832654713887467022424302137027464591058836092209603190188382260769433813993022505630461152395417463346722925694263588118045732676847071505490842135797321026736299641690577484012479270378890197293804457356481744328949852461826098937259230434439674200835714400781726886922479210278074504751585699507540662054376592369677090638225987743838339503008977841337583167047684756961800580703017370970534666273852458172572720875879261382083993839539636172109549132280308015488277368144327959598771334630351560967972034919201631142106813580368228402978846371857371806827314526167566524835285532141422351760573253929878831322088657018532953381852453183218143828610993927499233857483823232691702959106854044204892822806592051711724284235008965187269431116209490710759010635816732502341418590593254724970541918672066510512275733972096344462188174950319998776523140023539329436003379855105645281351937444016143898928787054394449105601502727625670795881383906039039288676192428133814643327334865152808560842807752396785028963148008241822749131523772306243429402029410205912547581779559152091143153113052436693564430279396098248426216143213920657201904412493206290919205361678388639357762918497405936503206458966261197630181179814051705377618065907564456669713813168820604658781952310839020449152479660026005473707526000754100007222261387641163270354836700147416126059876749141572720305266361277863668729110310370949464105491305194750995864883350466070137029275978646539252913015952830302204598842506699355993117866061160260005814893191533332348197335077829726769296985380806977336755960798054973987027975920271054253618697469662059005167786370987099539575849391360258732629920454447361023860122033565520096768353585125644333311814004470113279182709774015733411837692297735325065111995715384330434779944463283273450998477512496707194378830451355372927341212190193192666408126254159567768794069841926414489444814513599520708195572583432328185704880460324691727488984643766828929221968533932290896343475946957849296419295488948885980484822473860545163472972539831053355214130718544035299744031274819551321061282106290962797816484379180742816046262333428858931771383513847257564918238151863548326872549670867810735000555927271566769370272557635258491795428600005441438000909918496154813141451041043094679808895939357335312119088864813162060718491973671193269799017785775646532165048546462312371495177664302243889053945427823056142402950873834376139060136707080676584345523698385074640173331818138605135027952742588175588977226943601263350915784765926743171120921699036846530125406047987373889760254184965624236440000525972670033812018909652009242773764572096160802427160153683521549140711850861202115797422330830515794683574588742584088788331918179349090847602699042186161296799365566116807636697566500190652309767106195422164020691866322188401039923094219227326342777041242382646557698434746473940086005739263096327439546676682208069751832083199632683541348861009752173769365471130825320425628521937260114057869368804112909468258929615215420138131128011419192098818892287442102389456297261407679669274562960743159775258536267554220716346527573481206880205131567847803537811956944614289614256047039146612932140637294319775726234429170117284665594609690249024574011101240701124779242533024682953648054290224289477542260753974162916780134832311708915556562857690323685945872080434043407978672970826086453479197859399167301469387708649084372579889420706954286851266754018699900626544043704595968426526318648185823246086828838793123\n"
     ]
    }
   ],
   "source": [
    "from quaspy.orderfinding.general.sampling import sample_j_given_r;\n",
    "\n",
    "m = N.bit_length() - 1;\n",
    "l = m; # Ensures that r^2 < 2^(m + l) as r < 2^m;\n",
    "\n",
    "j = sample_j_given_r(r, m, l);\n",
    "\n",
    "print(\"Sampled j =\", j);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2. Solving $j$ for the complete factorization of $N$\n",
    "We may then e.g. use the [<code>solve_j_for_factors_mod_N(j, m, l, g, N, ..)</code>](../docs/factoring/general/postprocessing/ekera/solve_j_for_factors_mod_N.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy) to first solve $j$ for a positive integer multiple of $r$ using the lattice-based post-processing from [[E24]](https://doi.org/10.1145/3655026), and to then solve $r$ for the prime factors of $N$ using the post-processing in [[E21p]](https://doi.org/10.1007/s11128-021-03069-1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for all prime factors of N via [E21b] yielded: {148857569733497845863220175361223191316606910471581532450259055474768711371113107629205426044478994257558574595136991165136600511913029464646782231738570373037496688123539999718304459199896700908516381223386700474890146402393425991759002285418115786781334562664999448804559301844510515759781443207221888220733, 127464129907058416852419862544206483858533127614682008274342461070998109271419538757945769429936138086254619957140745465270203917586825925647569295659605419357676733795147574470348046548264642162544402366259752825380320428341980294083966523305795128852682450340727440893984049238933040572610068173238150780573, 119195687971922021372621191918058656854608926398271465007706405405764738065574471569348699030790937620461898813512366013331472104865637642884426948120456066512227210065116929693142650859173542010450981698211698894742228497478450587004379236830271423868055749443652299272623654486186450881748620911153631093189, 143653370906962213832221125972548186993793147225256479101915841314636455570619793778626523047081772987291883621498124341980839900153849834901562866869712349175174132611303508678354099155334357961279919040223656876640707689000311229807373332776462112895002715119420109503534890125841668435156145503897816255463, 130500593269878861635497728165486780483045060812770902879685935625342239165548326756881593323235329972983975146745738971624607372491212039011871250072685837925537036408239013280821351637274112077162351031677017624841652747772835987749784749997453168800269127690306410203195465163642584594761429738362705879243, 177533731264587152889112801442700692959945228382752809275658894322845353310784720857215112219935806595928410810449047881109078925761191610481091255082896634138470637785770750427073834998264948783499289515464398777150229911251276698680004792613669184715267553954460485390289098187481557844662344332446058112049, 153002907362889260188667429205566457072628243080067924318126480508262058127483362077728830631609578558105072787402714266565572578343146969539183854639748152640858511084059086685537187537186511162892257678879586392818722835192911749106742990532526075107597854289990819041480653963928157238876664948836595442181, 149804245573510945324970721367576067743105197900625084885333725155216226080363724205737276405911779750500118703557654733975314587200486261827663016404491919671703847335369937542584717321974925756113573249968302322191948935246573646832762563293279359138145576961804490231305998228345387305189451715728757600763, 140749726575732377709605185342331185547632858177534582982016751215130071154534867461948801759250518252372697406764832912764182010835897141581780663294530852798633759891819858555377278388898769298561742603774296359482921908337674123565202383263229945266402028912487961446359719317891278662032975830976681512637, 106153134784350358413063271386813501001164923544918597765901791886784397928018190335997299057888395430750831604751690469446090993345500125851704250449550116482655100367052555882649562794487519355617787511150151335198376269039380945828047567351164548239630158998133279153268206457289372717862632786392510114069}\n",
      "\n",
      "[ OK ] All prime factors of N were successfully recovered.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.general.postprocessing.ekera import solve_j_for_factors_mod_N;\n",
    "\n",
    "result = solve_j_for_factors_mod_N(j, m, l, g, N);\n",
    "\n",
    "print(\"Solving for all prime factors of N via [E21b] yielded:\", result);\n",
    "\n",
    "if result == primes:\n",
    "  print(\"\\n[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"\\n[FAIL] Failed to completely factor the integer N.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3. Solving $j$ for $r$\n",
    "We may also use the use the [<code>solve_j_for_r_mod_N(j, m, l, g, N, ..)</code>](../docs/factoring/general/postprocessing/ekera/solve_j_for_r_mod_N.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy) to solve $j$ for $r$ using the lattice-based post-processing from [[E24]](https://doi.org/10.1145/3655026)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving j for r via [E22b] yielded: 999152117269916193482566720261540219337016946489899039991268598138251478782579335989381583459372737365249388768950575145013766667976300367475445622154974099608901272024175218577461257439631660632664235783283193574020740719539109630734693806187846879776538692631555890233709264619504414053579025688478017169316361936617470995889671628182104998684487802553715252534969129343313060683183582261200522463749610237895616544394102431489280044701137741661813602011842139888694447798179318411913015421302067608451157227538404427460704474519906186536393191554306525295402655332757507553800288319745228202032351539758469908124800427960570107413420938021068235306870467842719496241428646067685527708592281761239505167768827223742522902728893215356910313702766975311228991690093501873471787900594605479188451969370329203323757584454752021363848001891256455006320422311823590349325664463088983013849019064720464119931034779003205646951028759324623430884665168626240894050562959191983688193731382775107925491975329717331671158275804720345966738264940575683164868845265592012635903770122957319082541375214988163776093756482926248640447724251308621508726669290691725497704052125646714360377427095205175125133742032646089032484415488760878811156533991234568010091474584694202278444166276678010148974638580343419646428042409827235610223173672969256287221698465164513193323786057265603255888376919010927320451685584314622963192469029502136592713211407872481802084190737835016082579285577488165789109935623287377593499498196353706346316220128605741063641510065280818397786020763125412922182566898790023209251471136184007620953908246305678971671912987989235300803341984200256703848630535346000089557947512586263366083010865489346789698256476925150107826726022554348829048382495836451044538905656168816721368949072833253705403002181784629493810329782672677723612617302792624298783996893520733444495340663284723660065741605187071537350973369833148093120864272360845769827949078462297549917012573976494741276672159967799850430290912272378711180438133145199123335558816199819372709874092261473799177569345067791030217006388821196854449844320396370310047268449908443664166422809790061338350864352338946302234731917792577085084667700797579301763905877603786273612568340919423124771613599273694832637920673930644071329656963257677008064300064558039121631033403010408230978993666757665543052065997195617184466226793426321425502772375836370694907227327165050568025904583415287998225987152262345416216515583968494566155849993001057408966938009029649285227679905303129559394232446898509727548146211378963133131013857927665299233589875973199102508694176525279464861738029289459071009290294363002529285903293335950258511627283763731057032559048098718913018760246729019437913120625519418301581672400967754717862801227102472016015049055378948696783874934611285316146586266736572397110972022728091838739047187639417086952362347991988663961173160407962490690868243439586312764389589456872862851498332993561517479654358180147030307158536122844248265869033678768796097981409609692164943013165574682964014758235620\n",
      "\n",
      "[ OK ] The order r was successfully recovered.\n"
     ]
    }
   ],
   "source": [
    "from quaspy.orderfinding.general.postprocessing.ekera import solve_j_for_r_mod_N;\n",
    "\n",
    "result = solve_j_for_r_mod_N(j, m, l, g, N);\n",
    "\n",
    "print(\"Solving j for r via [E22b] yielded:\", result);\n",
    "\n",
    "if result == r:\n",
    "  print(\"\\n[ OK ] The order r was successfully recovered.\");\n",
    "else:\n",
    "  print(\"\\n[FAIL] Failed to recover the order r.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4. Splitting $N$ given $g$ and $r$ using Shor's original algorithm\n",
    "\n",
    "We may then split $N$ given $g$ and $r$ using Shor's original algorithm in [[Shor94]](https://doi.org/10.1109/SFCS.1994.365700).\n",
    "\n",
    "To this end, we use the [<code>split_N_given_g_r(g, r, N)</code>](../docs/factoring/general/postprocessing/shor/split_N_given_g_r.md) convenience function provided by [Quaspy](https://github.com/ekera/quaspy)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Attempting to split N using Shor's algorithm yielded: {405845698954978023777115984221813761162044717496005602587484779494352691667208409981644347156357879204481021403785722167755824439066543563730004401804321452482491057891434042265849201807220984512740697460958343906226678877050096229841237060823065089982984664416521183060578816679980361022719149781011438264877772883426890140216209203340307119638998735395540102300992625943957586766903505133196137115832554397394578042335749897990509720172969404695216837322065697239688363221258760638829146151171959045102772670708656794712183300747222186568888336249675280209277392753044278873070417004002145328617251796642212436150928206231125342519187115373601178721699556678802059381900526182727413667319212192688313433973442436442966391256196730127488588848434433604239025145732861886538642988533805195718352057403333604982269732137266029157159468923677794925648262774238414702933072382953445407526314663705543042894302913203753959557369649765112428853984990448738127135961661156905760291634601085950049090687177803427905166566004644044757419921640760471080916856478267272332974572125972865729720282663939774866551591184773931930673655165542900851822631324489194727520204798881609286570047591441259649168289689063903465756517459651337545376183157, 6351435381258557826000753485463618511412500182448694822244431663434987524755090168312792531564283315944982349783963492494565641440130344388488680053536824683373212530797469769981273420728166975261003869093430810274830716398912975518298692144025853367514288973022599956314998366200506552162761684093449958024913474453152473616512039971580743337999793136239260931496318786952303514727792885403950288399904257825128024150291384861316449266096811009344462588398982412307802860150682017753113396416584959093401202897843962219442979189834793484471277737053999494067913662585130872084213210820683842549034384308505130470147710554809554043749275702245531055921418661221876093934518014635139283140455273009207298215695473601402844245178990778439553086043691453801244194384666407584424512849566875506502466855238107356729793869470563320927185935179258837955816289200655430620383333714352120689064201403424134060013489417386353977169278145048865608036247236461347574745712618216910088949816687816280526379757107397380771238677558565864523653435597541372953969363735040687940408653804485939630900495892963990302586107440590023557930594232507663035755435677545994625865603379537028499634596920153371890282280638432767034839913648540440396890006860505037847641556907325783880682897783489006629570820679835081733523396551031710308171726520793207313748401883795792813028731948013341192889729913856015072073582364805919024166738571573822165134885470797440442313929599260258244913862607159632125972866863849276300691661765606769253208109102881822361510446523804916411328442418018366585186345132713084508754451525829316226406345990264020204621138764062880962088983549013168727072598432122375100007404704833787562210756407416519499702329403631580495818128802914810600873695641149404135108856278875336019728693929832023766908264621751685637553498189317656665868160653267}\n"
     ]
    }
   ],
   "source": [
    "from quaspy.factoring.general.postprocessing.shor import split_N_given_g_r;\n",
    "\n",
    "result = split_N_given_g_r(g, r, N);\n",
    "\n",
    "print(\"Attempting to split N using Shor's algorithm yielded:\", result);"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
  },
  "kernelspec": {
   "display_name": "Python 3.8.9 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}