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 [[E22p]](https://doi.org/10.48550/arXiv.2201.07791), and with the classical post-processing in [[E21b]](https://doi.org/10.1007/s11128-021-03069-1) and [[E22p]](https://doi.org/10.48550/arXiv.2201.07791).\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": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled p1 = 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057\n",
      "Sampled p2 = 95642517997049540077507871019623337654990291762469900998794020741914418223226219484914512729851833688353703190601239455209547062433116939751007448890615267998873382329217199695921214528065950148996026845185422317190380999890225333854764677525659185445018259171781062372928454310392138160461947896658681809423\n",
      "Sampled p3 = 109464431735294159974378294274525657206318819420403729824301732669900016145525461205808884543364511930776254665221392803793527815537572044604556948966542735803855527632204173348346705081859987947224360357277306159043226383759325438531440117941819331729497009514666791332843453086877496404634366210511817347747\n",
      "Sampled p4 = 137734293786848997376765961551826452203984014389212366230683757589952938454332729666479869035501497167251940842676553615907274050348327052220825105746439846162913516957635781648735939635275359470155315407826225266351395605738710673357017907864055322199231065912750073317386154477224436294719647743036244351673\n",
      "Sampled p5 = 165951452874233136181136823829685944477169120813094977324219339904081602502998759859377104758790444750602872509876350603087715578296226679460636324205777915455954452383672926463963717719325338751267944428335611849825715587461600585280713913844224361456780672144813064757239070504691793241018558337272845680853\n",
      "Sampled p6 = 90543348566041974658147417602188751808239403241216246839558207536035813982115032944018065217805393080618167405195939923840951041445348541641411073416560435766633368921709313907923809547174820951202990616005662507001893688885871387851895358341534539704597308490025714995325954013775819387318340639373201835803\n",
      "Sampled p7 = 167226938706190836553643155843119208197862054995067415100217554047405801743210621031327509390733457696587026428066379600702360290229750029561230959243313199878214139188992093824931076608557202587723520663649688259097308452343733278018286029658158983822856538007385804379149382950315116619472385431466470845443\n",
      "Sampled p8 = 139078725874438214792511647620457473009303261343460036245872006102909511191882278715879081310118596134470678215135314498473748586091354747896910581385798693995223052349219412769428159364993737357340943399699828617275483047657132660367926422660725139840864269119783367437749112823519541516962416224141503859877\n",
      "Sampled p9 = 108248576454812297292757456822797213030391712751901011130749827803842948444668027012029895133008182513586538209530771766102255045591587035757004897031306603163249453053009687298039837327567637047662917872017967215447307047151893415692077744633787971350435158787451852870550191058087741172915928571754480687351\n",
      "Sampled p10 = 106440120364005540555351960306079290814562292731728072991643884321484281978314070705417464297190297513041026042299028959463072893825414003286960419655510762043967268690989062795423893615967015042769167807410938369445762446700441936094341844739246701491961360505234382152206390825577848765149813266698206071501\n",
      "\n",
      "Computed N = 587174661530752246757563670100007956784515608479535632951457772696666689090888723163658875061012900604413340235013049739673350932558563320546605531406297686428986232048191560610775748841342353008796327802089408721350331516814443985097205601135339495947364350818249694159963977208958521124894245803232201826216027150233631114071025904261683117209834062681535103497425548730556126815099862670318378189295101231448808312718639633265949156187838952517542610600024716412355926293361218611051007754986485357649279529118086995724594324452747333036552846055326713293470847158062636495878671746355425911068641146369522040942820115370918759782544646249724952423990032617641430148155988112356197681374183654954773864715331703304666665001169682680128795319921627052575987930575344766537087956740797637212971206431364421683299504857403604455766865133257802001266701580957008932483490378437037104083052395831302665908978385617368621849341948655911800020941009785168714463393639330824799199633338445281577269301391237702438881332788042732702818667676432868820243872525619127402055878873066584139220512284061323544211890765539722009695556264632693777871987696662149869271130260502610192977622081499209208549487072547651555784255613910447442849629335723706026775828507433941327522570407257350078650987674830546843593735700934403779613092884374663645035096776110152213072539084428333110353045535246856459082630402801800834821555136577264666615845109404514019202769406847029371125589401051491742831950079190478906575664136240798627587971352502359378110782772229091030820685861344878335766000338724624624209617709949103901381519321736439189215245535036433303629346530088127966945468835556261947234575943897429312349101080608300090655855428410509153360536955192263951044354036745985650986035201070559260999576268044935954855085879300032974894611584249390075467236906599240322679074164880038217310887105005891490454293469797829184841163136241272754198531175372973202155726778363291071704151156862295325045418178279657389998004388875973121642001270673127343514326447219322724031480515470964429321755358584942624434547983928021190406103523659019162705292905151554923590491518427537383778834456346696340172708316084258263315781970400262461146409610036268997398588163904120101334946534282802835191567922485920085959910412772924032962781469937906880168069863929168479159374112016787727512944256125986900834098783205864893854243301279407072270847806771703865941683138021606484509863978839297994872418814312214945674757335407739240404266190472676166908288194629540363452760549116048683478374501628131230354497288497212778933335796101487608132801398090065274004434584798955154327859907307239826559886055916049852380900567526329563206369476151070947716576421304602742825800144789574728453299113783682912195363022043313983720268391287611225635674186825065919141147351517665197998384914558466270495854408133913509485021138817465350561096024491968790785532579397806233013816807702137172737364946522030131354449533630083186045190955446078233454970030782967595136196086525352433146553737937264705452337234182329473559\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": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled r = 1068707828986540595224111100942470531125461379563831226738174603966336749632074703293981755085791586686358265496133947619041361420431631822294396350239983282313467240814588916753624806580343966661695746091425869176908380228395759623807425930379826037154983672125277010219012318567022602172075065168049835506832429164186945264392603377096524368711893934241676093297472130046577030329065774316200480379263835507350227436179825333972010634191252100279422702567296475794900041115605033597809914117234596890068032617030763776856930423615858136273240781604861415787689792033954209922398544595900425028514401672550773249685296433750455013918138984000077532384204088127601087363164735032155476790563073004255037884957252580316783641407284736180439709036493462343394912701231560224087397293782065933493493176145616990038854437387237841642152318899464413966656981873204924610060653840113817628609978554016939324419527707829594762890889986650849966902222759752557021331858045594691847914620964366183753888664111517295005798717364224930065698183362202059904904903039596825701452669649796988617270563887436961680517233064685220409355320525721965309113240912450174116679077968228561799083461714685934409475941149365370789040971575883593618533349552827881993384056624619600347097208583130932602292766595428367087113814970058099090933299476479025150584510335162643358432737903974792161194189661009231193103194517580935709566934837684808592949367961223730097807401652899666884722434053300356611261831962683866388397668081253177244350853281061501011890829363206530930274150213580166772568199046895570493217661534737111522454536596225942092201816892927221652957314354048930104292972841056619443503280819038812923600413593827428061490001796715404106832697592527657149105134060083724901367755397102381607607252774190886121183438060589769019465478805219683790425624442791188659912278744836060971810019882962535509518463787732290035110143342329479392966439178725592488737936267478175306835860272746773877451202968249521530133646087157438084473615152875159589979865743891710265535359781367475860525534124836701730531106995194478909291945890674805638980128102576085145990818868075322774568301521134459811956565917229525996476525054290595138461246142008917263655071243353955091442532172603176059058537306226185507881420081716246823635596433400381037316570160712648963717199801490905841003904122643836757378272151292488492533102302334800774077231779139340758188555793662575752505555660418676293097149030002032180338854241222143999290897932912043096628235383329458799593968664361843792696712832037941058098470340759128035859421529565974608948721900969359120993170101254483484816587886793127960965558409202850645228858589128278507174162244524662371721939131682330174003552587834565982073110909824344907571881273750092434367977304652016703118421935970155753999861345408695420215969027829566002229738068372154116643596294483254502321798068331498119840147540006956646272231006446996945093428908980310795342745319068194109925085583432393750171421045628480494201138262226178894959549514119341951446200\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": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for the prime factors yielded: {106440120364005540555351960306079290814562292731728072991643884321484281978314070705417464297190297513041026042299028959463072893825414003286960419655510762043967268690989062795423893615967015042769167807410938369445762446700441936094341844739246701491961360505234382152206390825577848765149813266698206071501, 109464431735294159974378294274525657206318819420403729824301732669900016145525461205808884543364511930776254665221392803793527815537572044604556948966542735803855527632204173348346705081859987947224360357277306159043226383759325438531440117941819331729497009514666791332843453086877496404634366210511817347747, 167226938706190836553643155843119208197862054995067415100217554047405801743210621031327509390733457696587026428066379600702360290229750029561230959243313199878214139188992093824931076608557202587723520663649688259097308452343733278018286029658158983822856538007385804379149382950315116619472385431466470845443, 165951452874233136181136823829685944477169120813094977324219339904081602502998759859377104758790444750602872509876350603087715578296226679460636324205777915455954452383672926463963717719325338751267944428335611849825715587461600585280713913844224361456780672144813064757239070504691793241018558337272845680853, 108248576454812297292757456822797213030391712751901011130749827803842948444668027012029895133008182513586538209530771766102255045591587035757004897031306603163249453053009687298039837327567637047662917872017967215447307047151893415692077744633787971350435158787451852870550191058087741172915928571754480687351, 137734293786848997376765961551826452203984014389212366230683757589952938454332729666479869035501497167251940842676553615907274050348327052220825105746439846162913516957635781648735939635275359470155315407826225266351395605738710673357017907864055322199231065912750073317386154477224436294719647743036244351673, 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057, 139078725874438214792511647620457473009303261343460036245872006102909511191882278715879081310118596134470678215135314498473748586091354747896910581385798693995223052349219412769428159364993737357340943399699828617275483047657132660367926422660725139840864269119783367437749112823519541516962416224141503859877, 90543348566041974658147417602188751808239403241216246839558207536035813982115032944018065217805393080618167405195939923840951041445348541641411073416560435766633368921709313907923809547174820951202990616005662507001893688885871387851895358341534539704597308490025714995325954013775819387318340639373201835803, 95642517997049540077507871019623337654990291762469900998794020741914418223226219484914512729851833688353703190601239455209547062433116939751007448890615267998873382329217199695921214528065950148996026845185422317190380999890225333854764677525659185445018259171781062372928454310392138160461947896658681809423}\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(\"[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"[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": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled j = 157245200785852638948834423391282841155392864935198349028146886027164687983144319382507974390294745625398765267195040167732749631297124868311882253744100682561714705416757894820187879936875024449534076990262878089608697031998710690923522367040307438520038955790877088644986297348278171182949215554569729169983053507047650080637711815979459918899380088730882751838867958589307269551339816522011955702086346838663153175494104466502687779910833046720959431529807266468711437440984678721350769595596980898393658052491116412430549506401614845145998697978312904231021148353673403542933472975572068154782141853572707370137855437972250747376537850985403365762808547003691208750257018002220883923628476043863970591185297095012994218809894118750861835417768526673811396437542974326291892958638125787183583223616425423813476625311475957027565695327403833757934753873056472598622539255884809530127316198393290471151627367503537900645480428987251091152940032646280632895112165589340836075469625082220259625051685732299686264156868850639499316655057447820381771950837077296399386917639967051592960000084776817750193425203191242943817317676430102850750054505866641415208269582117175267429122804325268055387360623180040995978824029192219004945734596748658858348514073826371550557932227967829830346744352860076732117894671416388109743985318410832854691125574104188244214126412639130479750967818374613501672953952457603882547363969549827427390144286170621483658353730218203102679320144201040802958628121509862654606863544684195440879745702054340103446009346762841003638764164358348006487692331689123227893390122343119520169802507772406949064975709862391166806358118217195652660265706052197136177769632275284355400135375769969016523770920923047296023949875987181833788084941841209645291633729599968084145942013686701150784422361570153284723501973901192962362010079143825787330601872823012049530704244873951193036185611397929839239477210054492053961275492291553790228038478919308634660123190714736420191576345724907830926278097398057509100162854994163980170606332399664828483767841291794126493352600695083828560229622261685059793911968912280156732086805169137817373182033944117029981842069205152653118492945302985186958622793955082617902409828020892634283104959105734613949158569060509597108772895221012577808517152552880483466377225519412637962906458486842780690055786427057265366598136628376374322273956822137587490976687421562105931060296774834704025699871466088409719993968639972920446959124956339211254996336944656771232027165055929465397545780693205156120012814952749506336077239287481401345040070027033338296045353549837617971908853921090174003517278495115028757340539502928027511421269508901855736612672629337991738890770168682412638390301917141179404212636276036817756419375316993912509543803106735710807257223310020388304588873805090816519983660468469558871334407262608632020110259065403552235064618516276705732184040800826182759968149242880006632437500649923791738198174539813690369859705735501917714825071395850403867857722294087959043498585686624357467296874433300902888386395150299229480196361494976806414879452459824545654088049201010521216160815165339064706369748045968992999575839812968822384700993793161974873959206246057266327373061603627887658443454219606288845442754087643041379784823884514274952215730913023871625900018184960419000836866829469529282246939127520980602429203481902812459664530353546810572350864530794990509113456004763893880712575939954898184658465820449546046330914589090145088727111101918350880217050815664292101167871367335284617658873424140643233001841189977293630912061349560464320170829210002644233442166929485921023636504255498954428056407994734155888935199077362566525353728769824416683001811014169342293739397078920360314538715681824879420332377507434914056388682903434753214945047251413538585648731733960074210538813170994704454359937768582746953034640190963342486271767516886624214169397649170011208194179051747025615013377688867531929392484080227865427495308703777069252937180527902826205441779245861910017267680281161537537441318181350262985398225332609077856897988156879571778040470201343714885255252982824077899023021421696662251888855873982754165984974675126082278535814331655546805947209987529825897238428433472631028594330282124592998418134428792487775766128873115482279038282648140531542505593965169625214775957232913523482023574377325308633118944831627230387120606308786004508202439033913055276654918422782453590730850262632092340371924366537120115921081368170495661255953746509548967208816269654137605164588828733014697309706716491308716783040581482202205799181537825899925512916920725403251965186357647612130030159902055925570146105503312972816146460329075235346252700206871302028943818960019831989496748997875768798523652394547626300232372015721740822768284225999495056891578466825341072664294735405215821008474483575325101238258131649716285474628903077380045770143787581953565843889339229610714473809947344539357721975219932239995740679027702285653474784745644817718855545580675434626472964296931880302154626204180155963223187034272757365135543649739719787195013448118921722296327659371576968146668110805698227103418305926465538465318329289030586973996936126055711644191254534732612782367512469496164859839512270730502085129322537965091294750758246586087094283921221050573624226476332327793644783997852504010563475455868558228313819733425248387307512829152430529539524196342152601320005477992658757516715722441472273727947342889966526391799330573845193478923844151729760306760828847512981392501433870076637051308508641591778043455340225278317396280603982788410190756293815274344579980136948642110097586267110399453748928441793958793032575937441617357804346341464129022801345138484157520863424205028020726736573234170806936362572858974734067452704935253736280327274206124321265937288656667739951079960485837768048441006399656826165773311813777848709257849626956222643120797239078014753788621495126242761710313820943660119810477023197015014040171254454068521986374796718194784192909812535584308832408994918675642665007143446287580528363327751798371850932632077965433850135138749168431440708665019284819841488241486846530087\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": 54,
   "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 [[E22p]](https://doi.org/10.48550/arXiv.2201.07791), 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": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for the prime factors yielded: {106440120364005540555351960306079290814562292731728072991643884321484281978314070705417464297190297513041026042299028959463072893825414003286960419655510762043967268690989062795423893615967015042769167807410938369445762446700441936094341844739246701491961360505234382152206390825577848765149813266698206071501, 109464431735294159974378294274525657206318819420403729824301732669900016145525461205808884543364511930776254665221392803793527815537572044604556948966542735803855527632204173348346705081859987947224360357277306159043226383759325438531440117941819331729497009514666791332843453086877496404634366210511817347747, 167226938706190836553643155843119208197862054995067415100217554047405801743210621031327509390733457696587026428066379600702360290229750029561230959243313199878214139188992093824931076608557202587723520663649688259097308452343733278018286029658158983822856538007385804379149382950315116619472385431466470845443, 165951452874233136181136823829685944477169120813094977324219339904081602502998759859377104758790444750602872509876350603087715578296226679460636324205777915455954452383672926463963717719325338751267944428335611849825715587461600585280713913844224361456780672144813064757239070504691793241018558337272845680853, 108248576454812297292757456822797213030391712751901011130749827803842948444668027012029895133008182513586538209530771766102255045591587035757004897031306603163249453053009687298039837327567637047662917872017967215447307047151893415692077744633787971350435158787451852870550191058087741172915928571754480687351, 137734293786848997376765961551826452203984014389212366230683757589952938454332729666479869035501497167251940842676553615907274050348327052220825105746439846162913516957635781648735939635275359470155315407826225266351395605738710673357017907864055322199231065912750073317386154477224436294719647743036244351673, 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057, 139078725874438214792511647620457473009303261343460036245872006102909511191882278715879081310118596134470678215135314498473748586091354747896910581385798693995223052349219412769428159364993737357340943399699828617275483047657132660367926422660725139840864269119783367437749112823519541516962416224141503859877, 90543348566041974658147417602188751808239403241216246839558207536035813982115032944018065217805393080618167405195939923840951041445348541641411073416560435766633368921709313907923809547174820951202990616005662507001893688885871387851895358341534539704597308490025714995325954013775819387318340639373201835803, 95642517997049540077507871019623337654990291762469900998794020741914418223226219484914512729851833688353703190601239455209547062433116939751007448890615267998873382329217199695921214528065950148996026845185422317190380999890225333854764677525659185445018259171781062372928454310392138160461947896658681809423}\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(\"[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"[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 [[E22p]](https://doi.org/10.48550/arXiv.2201.07791), 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": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving j for a multiple r' of the order r yielded: 1068707828986540595224111100942470531125461379563831226738174603966336749632074703293981755085791586686358265496133947619041361420431631822294396350239983282313467240814588916753624806580343966661695746091425869176908380228395759623807425930379826037154983672125277010219012318567022602172075065168049835506832429164186945264392603377096524368711893934241676093297472130046577030329065774316200480379263835507350227436179825333972010634191252100279422702567296475794900041115605033597809914117234596890068032617030763776856930423615858136273240781604861415787689792033954209922398544595900425028514401672550773249685296433750455013918138984000077532384204088127601087363164735032155476790563073004255037884957252580316783641407284736180439709036493462343394912701231560224087397293782065933493493176145616990038854437387237841642152318899464413966656981873204924610060653840113817628609978554016939324419527707829594762890889986650849966902222759752557021331858045594691847914620964366183753888664111517295005798717364224930065698183362202059904904903039596825701452669649796988617270563887436961680517233064685220409355320525721965309113240912450174116679077968228561799083461714685934409475941149365370789040971575883593618533349552827881993384056624619600347097208583130932602292766595428367087113814970058099090933299476479025150584510335162643358432737903974792161194189661009231193103194517580935709566934837684808592949367961223730097807401652899666884722434053300356611261831962683866388397668081253177244350853281061501011890829363206530930274150213580166772568199046895570493217661534737111522454536596225942092201816892927221652957314354048930104292972841056619443503280819038812923600413593827428061490001796715404106832697592527657149105134060083724901367755397102381607607252774190886121183438060589769019465478805219683790425624442791188659912278744836060971810019882962535509518463787732290035110143342329479392966439178725592488737936267478175306835860272746773877451202968249521530133646087157438084473615152875159589979865743891710265535359781367475860525534124836701730531106995194478909291945890674805638980128102576085145990818868075322774568301521134459811956565917229525996476525054290595138461246142008917263655071243353955091442532172603176059058537306226185507881420081716246823635596433400381037316570160712648963717199801490905841003904122643836757378272151292488492533102302334800774077231779139340758188555793662575752505555660418676293097149030002032180338854241222143999290897932912043096628235383329458799593968664361843792696712832037941058098470340759128035859421529565974608948721900969359120993170101254483484816587886793127960965558409202850645228858589128278507174162244524662371721939131682330174003552587834565982073110909824344907571881273750092434367977304652016703118421935970155753999861345408695420215969027829566002229738068372154116643596294483254502321798068331498119840147540006956646272231006446996945093428908980310795342745319068194109925085583432393750171421045628480494201138262226178894959549514119341951446200\n",
      "[ OK ] A multiple r' of the order r was successfully recovered.\n",
      "\n",
      "Solving r for the complete factorization of N yielded: {106440120364005540555351960306079290814562292731728072991643884321484281978314070705417464297190297513041026042299028959463072893825414003286960419655510762043967268690989062795423893615967015042769167807410938369445762446700441936094341844739246701491961360505234382152206390825577848765149813266698206071501, 109464431735294159974378294274525657206318819420403729824301732669900016145525461205808884543364511930776254665221392803793527815537572044604556948966542735803855527632204173348346705081859987947224360357277306159043226383759325438531440117941819331729497009514666791332843453086877496404634366210511817347747, 167226938706190836553643155843119208197862054995067415100217554047405801743210621031327509390733457696587026428066379600702360290229750029561230959243313199878214139188992093824931076608557202587723520663649688259097308452343733278018286029658158983822856538007385804379149382950315116619472385431466470845443, 165951452874233136181136823829685944477169120813094977324219339904081602502998759859377104758790444750602872509876350603087715578296226679460636324205777915455954452383672926463963717719325338751267944428335611849825715587461600585280713913844224361456780672144813064757239070504691793241018558337272845680853, 108248576454812297292757456822797213030391712751901011130749827803842948444668027012029895133008182513586538209530771766102255045591587035757004897031306603163249453053009687298039837327567637047662917872017967215447307047151893415692077744633787971350435158787451852870550191058087741172915928571754480687351, 137734293786848997376765961551826452203984014389212366230683757589952938454332729666479869035501497167251940842676553615907274050348327052220825105746439846162913516957635781648735939635275359470155315407826225266351395605738710673357017907864055322199231065912750073317386154477224436294719647743036244351673, 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057, 139078725874438214792511647620457473009303261343460036245872006102909511191882278715879081310118596134470678215135314498473748586091354747896910581385798693995223052349219412769428159364993737357340943399699828617275483047657132660367926422660725139840864269119783367437749112823519541516962416224141503859877, 90543348566041974658147417602188751808239403241216246839558207536035813982115032944018065217805393080618167405195939923840951041445348541641411073416560435766633368921709313907923809547174820951202990616005662507001893688885871387851895358341534539704597308490025714995325954013775819387318340639373201835803, 95642517997049540077507871019623337654990291762469900998794020741914418223226219484914512729851833688353703190601239455209547062433116939751007448890615267998873382329217199695921214528065950148996026845185422317190380999890225333854764677525659185445018259171781062372928454310392138160461947896658681809423}\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(\"[ OK ] A multiple r' of the order r was successfully recovered.\\n\");\n",
    "\n",
    "  result = solve_r_for_factors(r, N);\n",
    "\n",
    "  print(\"Solving r for the complete factorization of N yielded:\", result);\n",
    "\n",
    "  if result == primes:\n",
    "    print(\"[ OK ] All prime factors of N were successfully recovered.\");\n",
    "  else:\n",
    "    print(\"[FAIL] Failed to completely factor N.\");\n",
    "\n",
    "else:\n",
    "  print(\"[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": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled g = 33676025468932387705124586032795370310213707143016785133067537925372596357008894823823495894695948990618531616412554744008562009268909630515188256744779552147048051374364123337393244761817327168384365218591875769537900260893376060246004496995243469709837527391947419763589657126982583247880884018248884262645717065193151820298373812930193616368726631767129030330523236305600095950742707006998891054769385438326205096337746340204473049504030261329658399845423873977903497019503252374792292230836640924494902430754822177189659421834101335530061108627974425819969586486032941518613280693665280397732009993004177412142492747989585252664158941611564407338815122401708709946576597655883315013560820566283482513775617933787141251412669327947882690537250614821168590827712832327507878363147925813141180597058173710957288802234782302904927651571937196049210448400071646664196503245039672170306413148132901140624109797381598869311408869852525701950667703820152422663554635163413414609547414560325288746507882209685399876472899550125198777215429579058953153257680160012553141433723996502976196029021328446311985579354327115791496489097344520853273107855476913895557950555759130279248259842187239888233824375591911064566499820449828048029356701760037734836461793893220529222319665430292070268511589818231967885867812586327171130858218245164026945501067093904040995595572670465697810429620831331677631272606575487605731284030368862334101272036940971335829243771688020005522064433864059766933830904521343886198614086307889045795865989034532537211691879996535908098222502889400462670716669289690816621953320708695758554929733382781083974924111915268338309938835750723706448247751375085789438544069991238862078203379127991894099509387918116883820623409961457918902316982406368084022451879068040050478101274814943185288990210010618583797164548229402345216553150313634898496004380908775891684514074008306772444165014448429039298411094670095042945500939255252614217990870293001599901134806010060120499671718137130014973164635076554005762883581096836911895141651432550740050480780153955580440339007954990748990874886179787131500551883543835596882615415040642708178581854480608421088636530955651739222771075660892542165784921458904236523065514185432992890156342819344468252447423635401481578413801447361541865737070660548439986967337289655881595127121071620774730886863381824711564331637226673596195624717369614700324304359126219566306461558014605419533470600181946197149091522787588989370434366448780321591401623329270378401279938821974960594687093999553775330020669643762221164327346774062284143797344078929662321150323230797988777632970526865106721933306900867354355616000326394324667205378400079863331498264106921098415981019067041245563247812557227694709161558029249228257225961584877641323823012700613711499374811396600767115459161872430774295971016311710381782656405726159277251017916071951765349080641269037122675192258256190468217167746552597786351881155824612733844713594961357027524201650399815231307967126336692064166104783285649372857251454435713658019037143229497804400843980410185418367 \n",
      "\n",
      "Sampled r = 16030617434798108928361666514137057966881920693457468401072619059495051244481120549409726326286873800295373982442009214285620421306474477334415945253599749234702008612218833751304372098705159499925436191371388037653625703425936394357111388955697390557324755081879155153285184778505339032581125977520747532602486437462804178965889050656447865530678409013625141399462081950698655454935986614743007205688957532610253411542697380009580159512868781504191340538509447136923500616734075503967148711758518953351020489255461456652853956354237872044098611724072921236815346880509313148835978168938506375427716025088261598745279446506256825208772084760001162985763061321914016310447471025482332151858446095063825568274358788704751754621109271042706595635547401935150923690518473403361310959406730989002402397642184254850582816560808567624632284783491966209499854728098073869150909807601707264429149678310254089866292915617443921443363349799762749503533341396288355319977870683920377718719314465492756308329961672759425086980760463373950985472750433030898573573545593952385521790044746954829259058458311554425207758495970278306140329807885829479636698613686752611750186169523428426986251925720289016142139117240480561835614573638253904278000243292418229900760849369294005206458128746963989034391498931425506306707224550871486363999492147185377258767655027439650376491068559621882417912844915138467896547917763714035643504022565272128894240519418355951467111024793495003270836510799505349168927479440257995825965021218797658665262799215922515178362440448097963954112253203702501588522985703433557398264923021056672836818048943389131383027253393908324794359715310733951564394592615849291652549212285582193854006203907411420922350026950731061602490463887914857236577010901255873520516330956535724114108791612863291817751570908846535291982182078295256856384366641867829898684181172540914577150298244438032642776956815984350526652150134942190894496587680883887331069044012172629602537904091201608161768044523742822952004691307361571267104227293127393849697986158375653983030396720512137907883011872550525957966604927917183639379188360122084584701921538641277189862283021129841618524522817016897179348488758442889947147875814358927076918692130133758954826068650309326371637982589047640885878059593392782618221301225743702354533946501005715559748552410689734455757997022363587615058561839657551360674082269387327387996534535022011611158476687090111372828336904938636287583334906280144396457235450030482705082813618332159989363468993680646449423530749941881993909529965427656890450692480569115871477055111386920537891322943489619134230828514540386814897551518817252272248818301896919414483376138042759678432878836924177607612433667869935575829086975234952610053288817518489731096663647365173613578219106251386515519659569780250546776329039552336309997920181130431303239535417443490033446071025582311749653944417248817534826971024972471797602213100104349694083465096704954176401433634704661930141179786022911648876283751485906252571315684427207413017073933392683424393242711790129271693000 \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": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sampled j = 170585891741851758812587208530322226366076966927408796757307629938341623457842581991963806766334665396948086505150564819623739504178841340060653654647223502453365927159451144750601660830997763686261411718115297417801721854628529880089244017954154945801698640728903752582042406793095988535726910884017098998805253636703958285994940941052657396242573053260423995280521127693210021320443017853808084660349560648050272628942888265031700405786211426668865975929367385430118297862323775369321470481246625944122287915389746926113874184184718781658680591760957735585125328891239506101722367881405885764773873266497101475539868491265125535685123871074638907450831136079141445319272568302251348313224075126258357320813057406512221326289335420041929876565399720905132533156938403613290748624534291682337447060251557862711576006890336463687528596044418160888233880065917549462521032784476280867319903572282813591868825233439847823304394070264982748559229714023293743009898166190137057108236627445478866001146261163317605495660976009139590847123338213183510783403845711075011545743675825100008617549526565807133501615091608897950868001751806779688246246032890011439679879878983645522555542011196553024084301567046756331777078819833853264138871958958895407287319896974020796951456945406001734411466187674284261339624011639545506976887919836393831546904238202972701018117900081077895374962918155651715709040519079472557477791489600907434267277345238507575567161445795634252800697359195654806810727042121538633868786201731495388699736819518405669737505320236877229622647785535875849154285921426701709415641205935497679551450487707069604919822012079345055294504217581280122009700010684751100016504684039390810660626155012987258499497682684171849385721164003526730767970548946643244282882965343006866297144747785152803969158986020945686063090845528189250828832121858664714417701514393361227311666832547602851925558116347956554772746815959384736681521531041463808853906137742094293289728441171916507348772156700321838512240092408883653812373956478389357770217594172822548356372621185098003864269750935248656936877537239026380710390891905477527611041169367745437572533110115161824275830825287532270263938680374567763490868916256276052990568298704655098784512901073998713049963890118110348188276681979343642787943456665923072390618983991333976994745937073654808425684203245940423934968734202342767881396595242464225414657086458439984320646497788046618300051077269457618289808945554471781162883948884044615815526640855912655423890149183857950187719597685208899266083482630529672236266075983836343711037613859141685733293490531011532183432687963727523484968298363173287240876807192881061226697992106341886715631303572396630348367144810956566766595486093164472223363150408084916863654517931373320438654981292573733437262201736505423920604379937490936374264716475637318926164783639027116969485196282243044254445420113943981345048372774890145212452911151867248215229960675652809467017768791981208014920535494466535046485799097887159222636706916904519058476727591062787203335996429663486462285164957589523617279051794837935190683642610912980620061219253953265221891994527945992535374944169746968403852358388034680077186857588328316854281367968383281676285214365602712139584783374745631507331825928035757079401416064120633601023268162475940388623550515435542900271276982053624316974706196133023011632457066352842292571778162099728714816178352502281252860911489307239622721997292657966671263208834396122181430513810781736094493857046731743102790431513165049337459617455916365264948248631979543483936757619196205627209431341851318996501365324677469441757379519889350501292334826961645664131241910839281460916760859326228031352244822852046395675301493991208879065426687970461569529296442431087455730147663642995161797714549782276320518015174597707956491321703136392410339431058369124356231389278727677450153158796132180976257741497527044785348011709153976170432322603137020607361585801158919352533351219753472954526450651993990321580112002222323412586793870853936673627142399085491591173192609575310580412783691209347345215185165600958175196424158042569932783122435349400538113412036995422948201322859588251793325309383385395315475861889275695282763728509291518757979804013983798651665617741717896473992118327160152347368580893402494580621883829311572656723463689009791411736673447702021998830258053075429537576550992517475803812871228465401715823212550210472178133946159839388578465220949617102214994311769647619611955063276488188029564403651131940553600163244962815102544281172013304413669614137106053830527194124851817233251320904520362203804624632161613710790221727158373120073711412022972687295682095340620011927339025135687101663575313619348347405544104468200164617831189182038378395089205243740762283063570491669805305545301727892717682755233058586678926110924300233203232409728536728546811499076667355279505263159714665098822899988027792551636552818384145902899471200950076032758422384552793085750925759162144114894492192510084529852917317164102936439101372044140872377030179252889991922143526573063145382173627346017399843685479423197892943863568300629940911651585810878789770922123357532341630308553200263144883546413368276139205869767924100595218014011476937159900500739038019180698300788828694508889143212650400893530044106065285130703829269372805994201716502747195714509014315460399203009052736392798247384546944169067239217818368807682981258675048171985891711821760590435300614353115934709820502462760023523460483780408466981294088146813393751537471260589873961161417944954667714946488437760074763299133422583048937975053470834563641514306328686810885819935784134425606348614160488983330913193067595691033592671803191399476975386920859183754673371612919189736639910376231468491403265206095669924420118233907466492166141514030653860334690696136026425959688410303460673811449406310975579464081709216687368698780782211090651360202434487459304554889787350278503472603563620691299030352827003245645570324430285671471324112984861470429194724450342140922847050809272417236099481769969615853513703086751198040551249149450849948856122030247588136890706148473611341119156228077609504466320\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 [[E22p]](https://doi.org/10.48550/arXiv.2201.07791), 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": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving for all prime factors of N via [E21b] yielded: {106440120364005540555351960306079290814562292731728072991643884321484281978314070705417464297190297513041026042299028959463072893825414003286960419655510762043967268690989062795423893615967015042769167807410938369445762446700441936094341844739246701491961360505234382152206390825577848765149813266698206071501, 109464431735294159974378294274525657206318819420403729824301732669900016145525461205808884543364511930776254665221392803793527815537572044604556948966542735803855527632204173348346705081859987947224360357277306159043226383759325438531440117941819331729497009514666791332843453086877496404634366210511817347747, 167226938706190836553643155843119208197862054995067415100217554047405801743210621031327509390733457696587026428066379600702360290229750029561230959243313199878214139188992093824931076608557202587723520663649688259097308452343733278018286029658158983822856538007385804379149382950315116619472385431466470845443, 165951452874233136181136823829685944477169120813094977324219339904081602502998759859377104758790444750602872509876350603087715578296226679460636324205777915455954452383672926463963717719325338751267944428335611849825715587461600585280713913844224361456780672144813064757239070504691793241018558337272845680853, 108248576454812297292757456822797213030391712751901011130749827803842948444668027012029895133008182513586538209530771766102255045591587035757004897031306603163249453053009687298039837327567637047662917872017967215447307047151893415692077744633787971350435158787451852870550191058087741172915928571754480687351, 137734293786848997376765961551826452203984014389212366230683757589952938454332729666479869035501497167251940842676553615907274050348327052220825105746439846162913516957635781648735939635275359470155315407826225266351395605738710673357017907864055322199231065912750073317386154477224436294719647743036244351673, 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057, 139078725874438214792511647620457473009303261343460036245872006102909511191882278715879081310118596134470678215135314498473748586091354747896910581385798693995223052349219412769428159364993737357340943399699828617275483047657132660367926422660725139840864269119783367437749112823519541516962416224141503859877, 90543348566041974658147417602188751808239403241216246839558207536035813982115032944018065217805393080618167405195939923840951041445348541641411073416560435766633368921709313907923809547174820951202990616005662507001893688885871387851895358341534539704597308490025714995325954013775819387318340639373201835803, 95642517997049540077507871019623337654990291762469900998794020741914418223226219484914512729851833688353703190601239455209547062433116939751007448890615267998873382329217199695921214528065950148996026845185422317190380999890225333854764677525659185445018259171781062372928454310392138160461947896658681809423}\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(\"[ OK ] All prime factors of N were successfully recovered.\");\n",
    "else:\n",
    "  print(\"[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 [[E22p]](https://doi.org/10.48550/arXiv.2201.07791)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving j for r via [E22b] yielded: 16030617434798108928361666514137057966881920693457468401072619059495051244481120549409726326286873800295373982442009214285620421306474477334415945253599749234702008612218833751304372098705159499925436191371388037653625703425936394357111388955697390557324755081879155153285184778505339032581125977520747532602486437462804178965889050656447865530678409013625141399462081950698655454935986614743007205688957532610253411542697380009580159512868781504191340538509447136923500616734075503967148711758518953351020489255461456652853956354237872044098611724072921236815346880509313148835978168938506375427716025088261598745279446506256825208772084760001162985763061321914016310447471025482332151858446095063825568274358788704751754621109271042706595635547401935150923690518473403361310959406730989002402397642184254850582816560808567624632284783491966209499854728098073869150909807601707264429149678310254089866292915617443921443363349799762749503533341396288355319977870683920377718719314465492756308329961672759425086980760463373950985472750433030898573573545593952385521790044746954829259058458311554425207758495970278306140329807885829479636698613686752611750186169523428426986251925720289016142139117240480561835614573638253904278000243292418229900760849369294005206458128746963989034391498931425506306707224550871486363999492147185377258767655027439650376491068559621882417912844915138467896547917763714035643504022565272128894240519418355951467111024793495003270836510799505349168927479440257995825965021218797658665262799215922515178362440448097963954112253203702501588522985703433557398264923021056672836818048943389131383027253393908324794359715310733951564394592615849291652549212285582193854006203907411420922350026950731061602490463887914857236577010901255873520516330956535724114108791612863291817751570908846535291982182078295256856384366641867829898684181172540914577150298244438032642776956815984350526652150134942190894496587680883887331069044012172629602537904091201608161768044523742822952004691307361571267104227293127393849697986158375653983030396720512137907883011872550525957966604927917183639379188360122084584701921538641277189862283021129841618524522817016897179348488758442889947147875814358927076918692130133758954826068650309326371637982589047640885878059593392782618221301225743702354533946501005715559748552410689734455757997022363587615058561839657551360674082269387327387996534535022011611158476687090111372828336904938636287583334906280144396457235450030482705082813618332159989363468993680646449423530749941881993909529965427656890450692480569115871477055111386920537891322943489619134230828514540386814897551518817252272248818301896919414483376138042759678432878836924177607612433667869935575829086975234952610053288817518489731096663647365173613578219106251386515519659569780250546776329039552336309997920181130431303239535417443490033446071025582311749653944417248817534826971024972471797602213100104349694083465096704954176401433634704661930141179786022911648876283751485906252571315684427207413017073933392683424393242711790129271693000\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(\"[ OK ] The order r was successfully recovered.\");\n",
    "else:\n",
    "  print(\"[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": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Attempting to split N using Shor's algorithm yielded: {5806283263382912787812586433706199981959091144043055126469782855006413868626639776933933981419106195262304729226484578512560253556619384467835149985498513995473336894616516588139045413310335496856024006582923760792321821669369065696049413618690292567813820092772735995036402553543234639796742983548850410700135251251260263805664864312037475885446159841807038438164637330411854483269738324404997093199264346512649942041994136404922750397549069497113262073982683344808758515865225662653151368409965318639431553936849242483333213047449462458187369603676046767927418321132695236904018860764020119910931461378837621196106614369729906065578643322237125407509359529278028376248368924632371070426923047815113061442469301013367529064440423660294010947936428969697251347658535309632411931661707248250842991394661531146514793820347025508319294596488855812733801278681953121974320676364247043955756150751069928545098120258279393551219763861980911427151368580260469468956578855881882270637538569424681605333341673620410955931970098559710976309356755524146295401628677994528730132260795907583730890916608951778799817222833090840957719244773319291144068221766946990372822895363467412707854388308288788825623740585529253460999339258048068824087977676034040623543278205278083508147552270267591165874397622600638891473136300531504603442201052174410045754180112861007375168069523587742098778871802636350608126516619461431622292650991951859796809042764928668975004062700941581658306383663691090539725653416880476465239384041405108783678655035163540156177683453139859442652769579436974959597966127047225987142773688035021839725732692863192657105483239342520600150039650310508218041776224664140643833934570233853458845190120524225170552119085910035815157104681034663294582898109230718179306914459388355919262182424402768618112323325014427555145241370672357519060862461387192433413304452834204282268392610532366907122009167764325215671129374923224815465387972805975202969485572900419466260189391511914198367675821933004800314573788340212688554003958753076612369892471452002826259839525432287051064339440400335574646785734294978592215199428980204931703127364827260693786853627350333286938866359462200970342024144680487110310910830408381849976894519342024007963550513331579246433933467995918077690750423476572324454611058547100284714954200404817294069903864320227731442480279702249982714779458550913869819237471572301211124583965993673360706609681089350418280320647715043384953653683407553468228343602885225297983384849050749245750946458684852914153393959586899617983587970490907897934863106123701808323320161703160137459415884408718810804222205786614528163719078721515163480646282577194176195985623411993895391292247684668779847004690920951239149360711194800168889685656039352688633609126178621887, 101127457083216239607260037524508344625763861962136625242530979023750981716793831621986469519497221632194757946167863568609241093392897486016883574305709475063291084824697893812128808590242719288284160394090553689881780768452386741883917392079192307844818134464666938109877085455288309093554788547515251398057}\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
}