Auxiliary witness for BLS curves

bls-residue.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ef2ffbb9",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = -15132376222941642752 \n",
    "k = 12\n",
    "r = (x**4-x**2+1)\n",
    "q = ((x-1)**2)//3 * r + x\n",
    "h = (q**k - 1) // r\n",
    "\n",
    "lam = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129030796414117214202539\n",
    "m = lam // r\n",
    "\n",
    "p = 5044125407647214251\n",
    "h3 = 2366356426548243601069753987687709088104621721678962410379583120840019275952471579477684846670499039076873213559162845121989217658133790336552276567078487633052653005423051750848782286407340332979263075575489766963251914185767058009683318020965829271737924625612375201545022326908440428522712877494557944965298566001441468676802477524234094954960009227631543471415676620753242466901942121887152806837594306028649150255258504417829961387165043999299071444887652375514277477719817175923289019181393803729926249507024121957184340179467502106891835144220611408665090353102353194448552304429530104218473070114105759487413726485729058069746063140422361472585604626055492939586602274983146215294625774144156395553405525711143696689756441298365274341189385646499074862712688473936093315628166094221735056483459332831845007196600723053356837526749543765815988577005929923802636375670820616189737737304893769679803809426304143627363860243558537831172903494450556755190448279875942974830469855835666815454271389438587399739607656399812689280234103023464545891697941661992848552456326290792224091557256350095392859243101357349751064730561345062266850238821755009430903520645523345000326783803935359711318798844368754833295302563158150573540616830138810935344206231367357992991289265295323280\n",
    "\n",
    "assert(h == 27 * p * h3)\n",
    "assert(m == 3 * p^2)\n",
    "\n",
    "assert(gcd(3, h3) == 1)\n",
    "assert(gcd(p^2, h3) == 1)\n",
    "assert(gcd(3, h3) == 1)\n",
    "assert(gcd(p, h3) == 1)\n",
    "assert(gcd(p, 27 * h3) == 1)\n",
    "assert(gcd(27, p * h3) == 1)\n",
    " \n",
    "F = GF(q, proof=False)\n",
    "R.<w> = PolynomialRing(F)\n",
    "p_irr = w^12 - 2*w^6 + 2\n",
    "Fq12 = F.extension(p_irr, 'z')\n",
    "z = F12.gen()\n",
    "\n",
    "# F = GF(q)\n",
    "# Fq12.<u> = GF(q^12)\n",
    "ONE = Fq12(1)\n",
    "\n",
    "w27 = ONE.nth_root(27); \n",
    "wp = ONE.nth_root(p);\n",
    "\n",
    "assert(w27^9 != ONE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a86de903",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pth_residue(x): \n",
    "    return x^(h3 * 27) == ONE\n",
    "\n",
    "def get_pth_root_inverse(x): \n",
    "    if is_pth_residue(x): \n",
    "        return ONE \n",
    "    \n",
    "    v = 27 * h3 \n",
    "    wj = x^v \n",
    "    \n",
    "    v_inv = inverse_mod(v, p)\n",
    "    s = (-1 * v_inv) % p\n",
    "    \n",
    "    return wj^s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "4253aba3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_order_of_3rd_primitive_root(x): \n",
    "    # correct way is do do r * p * h3 but outputs of equal Tate pairings are always of the form c^r thus there is no rth root contribution\n",
    "    y = x^(p * h3) \n",
    "    \n",
    "    if y == ONE: \n",
    "        return 0 \n",
    "    \n",
    "    if y^3 == ONE: \n",
    "        return 1\n",
    "    \n",
    "    if y^9 == ONE: \n",
    "        return 2 \n",
    "    \n",
    "    if y^27 == ONE: \n",
    "        return 3\n",
    "    \n",
    "\n",
    "def get_any_27th_root_inverse(x): \n",
    "    pw = get_order_of_3rd_primitive_root(x)\n",
    "    \n",
    "    if pw == 0: \n",
    "        return ONE\n",
    "    \n",
    "    _ord = 3^pw\n",
    "    \n",
    "    v = p * h3 \n",
    "    wj = x^v \n",
    "    \n",
    "    v_inv = inverse_mod(v, _ord)\n",
    "    s = (-1 * v_inv) % _ord\n",
    "    \n",
    "    return wj^s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "eb18b2ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "def h3_ord_element_lambda_root(x): \n",
    "    # after appying shifts we know that element is order just h3 \n",
    "    \n",
    "    e = inverse_mod(lam, h3)\n",
    "    return x^e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "84d82cf1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shift_factor:  3078121531037292546197317548791524739607688140774938778218205022034633600138391919997165726685662362476862461041789*z^8\n",
      "step:  0\n",
      "shift_factor:  1579681198453166178999639747464605902336644583481142589494398105333832829907524000836996214449257264106515405211722*z^8\n",
      "step:  1\n",
      "shift_factor:  543642823234940353166949621108401011629826557341535848652195507323489999848813987978198572180357206101946617871511*z^8\n",
      "step:  2\n",
      "shift_factor:  749211108420394583471702734334073156889574570504034124119802956164034859511110386767012121069962074782676639780859\n",
      "step:  3\n",
      "shift_factor:  1501060526682758890813058319647591877904560081723327481763336288187267344611838548546161004713265489841418329169081*z^10 + 2501349028538908502604731506088312278652322738215680403568721847936764305878999315896526624415750174196475943390706*z^4\n",
      "step:  4\n",
      "shift_factor:  3742229627523572289634039270959557675311873196963353723955753918116753724531035493130024268121314493207719872619144\n",
      "step:  5\n",
      "shift_factor:  3093330965185904175502452696276920109218355687729265904067395865300170334814891377108412394535254016459739500810348*z^10 + 909078590035763217915337129458984047338527132209741981264662270823861315675946487334275234593761647578154771749439*z^4\n",
      "step:  6\n",
      "shift_factor:  1207243283601375587665419090801016190937884067327986248837543570926513232504749945166110789680871473726850615526147*z^10 + 2795166271620291805752370734934887965618998752611021636494514565197518417986087919276576839448144190311043657033640*z^4\n",
      "step:  7\n",
      "shift_factor:  1553191028796966459000451744815032427494345568168608856601522536404869073686857605905607326908683383965888484476708\n",
      "step:  8\n",
      "shift_factor:  198935635856492066155262467202106759303543273430931138408195951068324808176183861669293708172118551445246552941112\n",
      "step:  9\n",
      "shift_factor:  190802009934104260075497027458868754284923190893954153975671134593492461471650363916095256068662085527794223099237\n",
      "step:  10\n",
      "shift_factor:  2926565992666623894120006565683818438435672761526967501647341585802910344906696678761942471801807468057538547467308*z^10 + 1075843562555043499297783260052085718121210058412040383684716550321121305584141185680745157327208195980355725092479*z^4\n",
      "step:  11\n",
      "shift_factor:  2663422601824173044789779554092646878215969901270777008647122830515771479153330573330773581578421074595793172064212*z^8\n",
      "step:  12\n",
      "shift_factor:  206972997620454567664723153487155240770799580333367146291435921986938544726160079953504500152416308612467512779623*z^8\n",
      "step:  13\n",
      "shift_factor:  821432115691467132852249506410417607061216535689861231179057869142814709764155799586288916437539342207430010339973*z^10 + 3180977439530200260565540319325486549495666284249146654153000266981216940726682064856398712691476321830464262219814*z^4\n",
      "step:  14\n",
      "shift_factor:  2718631826383094869454630445020594518310499571782596882387500726819987187795065130470659151017699608264490791269326*z^8\n",
      "step:  15\n",
      "shift_factor:  460362918756811065163681122007668431715103075672548557093070113899487650509552957907733812178427811510204451346922*z^10 + 3542046636464856328254108703728235724841779744266459328238988022224543999981284906534953816950587852527689821212865*z^4\n",
      "step:  16\n",
      "shift_factor:  580095621153514493126997650544773966501496950180971045351029848031636614336314525274556469449316365016337107473188*z^10 + 3422313934068152900290792175191130190055385869758036839981028288092395036154523339168131159679699299021557165086599*z^4\n",
      "step:  17\n",
      "shift_factor:  3590966413409299531566154611128280815979800500261106497720973467980865491095943522305207462832855969931779728609105\n",
      "step:  18\n",
      "shift_factor:  2599484957665302476220428326727603547035654913466840596144341200961914274197011288882945487344052220343651392011594*z^8\n",
      "step:  19\n",
      "shift_factor:  378338969969862792555210266558078086202368225003012208018181104954520430983506421071444908018802232154549303748541*z^10 + 3624070585251804600862579559177826070354514594935995677313877031169511219507331443371242721110213431883344968811246*z^4\n",
      "step:  20\n",
      "shift_factor:  2470448985096169731571560819386257337972233141937199901046691963624271550096683217811828438659858694275199555117501*z^10 + 1531960570125497661846229006349646818584649678001807984285366172499760100394154646630859190469156969762694717442286*z^4\n",
      "step:  21\n",
      "shift_factor:  1785007827028972044160101717380540716863209242661176850689112225099214840972466648739299382833160271433436640486133\n",
      "step:  22\n",
      "shift_factor:  518978527696225078854242221771043459905883957030729180985623908605101266827721835946012246982144401842523235092538*z^8\n",
      "step:  23\n",
      "shift_factor:  1139308005362132724141267492269242113272705522667188955387254835205833624230318682352223998027204092896741383290423\n",
      "step:  24\n",
      "shift_factor:  3389319258482358431888526173767248285801098726312866065518578019952754566882417030596157041070860262903996021863849*z^8\n",
      "step:  25\n",
      "shift_factor:  399875810028910580472921920467713872969063081210686366774471674410185993950687630477347433429826715210585456979404\n",
      "step:  26\n",
      "shift_factor:  1374072975979111693732119763672156450942172695570871804291828386799973318563041965683149337430450733830402445963371\n",
      "step:  27\n",
      "shift_factor:  383372115370151568896729595405033995710951573069231908535782616168745270612054550662016218564455200585369407476024\n",
      "step:  28\n",
      "shift_factor:  1361655758965944612471223189028784255222542507312007070119904824581959254183311553694605729131126470145794670909843*z^8\n",
      "step:  29\n",
      "shift_factor:  1734153230462954886987218284829536832567900650006465745325303994082053924306257131182414489781914820725133582215324*z^10 + 2268256324758712506430571540906367323988982169932542140006754142041977726184580733260273139347100843312760690344463*z^4\n",
      "step:  30\n",
      "shift_factor:  227151095783220113534954970169923672874762788391417640757012000724032948118174243399585075374334884529718051577468*z^10 + 3775258459438447279882834855565980483682120031547590244575046135399998702372663621043102553754680779508176220982319*z^4\n",
      "step:  31\n",
      "shift_factor:  3814379268516979593411933474842351536933623492838111022456562258609443725755122124264677534160893038203234470668144*z^8\n",
      "step:  32\n",
      "shift_factor:  3777511596224314492538722753960508002365199646919062581303685578356228583667682722231647625137661384476295386102115*z^8\n",
      "step:  33\n",
      "shift_factor:  3048226491920061746886052019480914719795925582662684585257261518693363661419604440768614258267450036216087198746696\n",
      "step:  34\n",
      "shift_factor:  2798171715691869665097952778497186701420667329024023058814181339858308877333447955733994852710187372225789595950062*z^10 + 1204237839529797728319837047238717455136215490914984826517876796265722773157389908708692776418828291812104676609725*z^4\n",
      "step:  35\n",
      "shift_factor:  3556109522389866572222881547595079684770528268993059953027174168669580659574296632364988993595678026806066626918742*z^10 + 446300032831800821194908278140824471786354550945947932304883967454450990916541232077698635533337637231827645641045*z^4\n",
      "step:  36\n",
      "shift_factor:  3057763073294964329565079483996887006609400227381005029933475415675997029358198283694838519773661294526767671577097*z^10 + 944646481926703063852710341739017149947482592558002855398582720448034621132639580747849109355354369511126600982690*z^4\n",
      "step:  37\n",
      "shift_factor:  3528370069629042598538836068914673836900795187361310133996710493796941992169892286605568733794484407531003427788977*z^8\n",
      "step:  38\n",
      "shift_factor:  1939964497658332575998824659774760928343895520256267919013310051697951836065928192879571060262866923664154634511059*z^8\n",
      "step:  39\n",
      "shift_factor:  2458571641106423477671183424007190362910464232226713840200617829793277015618637737760012219734100751638726547769693*z^10 + 1543837914115243915746606401728713793646418587712294045131440306330754634872200126682675409394914912399167724790094*z^4\n",
      "step:  40\n",
      "shift_factor:  3358864644800212088372876712843733689275818801959242040613167232991963701994108132179535627909626572450060803019437\n",
      "step:  41\n",
      "shift_factor:  1501820595573085454801831948016607780026093090391870498549126686329086176325738837853915018584773345809373354544265\n",
      "step:  42\n",
      "shift_factor:  721762946889828621026766621203613428731831913861726727135735804335692199389025343599956236481597014660964962927227*z^10 + 3280646608331838772391023204532290727825050906077281158196322331788339451101812520842731392647418649376929309632560*z^4\n",
      "step:  43\n",
      "shift_factor:  558819092872445745740613089309611685896015543767344848587469986298291690086953457808038872520023346041591941771782\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step:  44\n",
      "shift_factor:  1920117691156037313777208626225323671935194449766620899036874822984435897073953480291251256073154039474808491832771*z^10 + 2082291864065630079640581199510580484621688370172386986295183313139595753416884384151436373055861624563085780727016*z^4\n",
      "step:  45\n",
      "shift_factor:  321075074376683360258523709990384964250202360723119882383364868372567696584021404256746678862763406384929982417276\n",
      "step:  46\n",
      "shift_factor:  2735124261228266701531474103833515876189713609252312789167823233962260838196846141099389509839810336378559346292615*z^8\n",
      "step:  47\n",
      "shift_factor:  949761853906959551641042897164892029700112320328754915691819383656393051428310894299826414527575493587019310579929*z^8\n",
      "step:  48\n",
      "shift_factor:  828683827514282130081766890127689929404102111523185796487823446747320723364720438352336186954377624948314076771162*z^8\n",
      "step:  49\n",
      "shift_factor:  3125977157600113877704245924297146981987525212252578915057495777566016251846914681304232383375928562114144185459842*z^8\n",
      "step:  50\n",
      "shift_factor:  1707840249215316601459833526003020934466033570867684845613800085010995268248451397078429063158549095363817431496745\n",
      "step:  51\n",
      "shift_factor:  1575646413155794243753683159519638729431154270806249081043755832177018832674004061416277192433416185211482167166276\n",
      "step:  52\n",
      "shift_factor:  1083659604571031727285199524512563478978393273686789298614624933365960821678682689597494000467952641952009969471408\n",
      "step:  53\n",
      "shift_factor:  1561178778969356595678376181204207749366949069752042712707191016735725026789305543311326709085928353962405544858688\n",
      "step:  54\n",
      "shift_factor:  1288860696135070003136413278091089270654049487211745212646924907070665334917425610799663528742595635801864847765378\n",
      "step:  55\n",
      "shift_factor:  1189434666900576281961239028498933051054834313621143844326976462577535200948941524122281514374120297169322641178641\n",
      "step:  56\n",
      "shift_factor:  3782839934883559858463924081397371463162164654256572961342727783919818082579887306692666895219214167723988029613926*z^8\n",
      "step:  57\n",
      "shift_factor:  65284234263212647721236015070448472480944271991963166940140506707203850361760667283404760477580634870309085748507\n",
      "step:  58\n",
      "shift_factor:  2571688308715635317026243709797742434612683521442595007615378504130284218685442634946937043390826218132951082874044*z^8\n",
      "step:  59\n",
      "shift_factor:  3011818954406419731434149970240115628735404831677306672431512634179047370653032678307993665593369909354979261596095*z^8\n",
      "step:  60\n",
      "shift_factor:  1211575549925308142062658809981591849744638906951017863857875454967109869780842686352845449510746243531124300656963*z^8\n",
      "step:  61\n",
      "shift_factor:  2234253232263395814525278539111300208557398614069453738932887321523178213021089816268670602263725906290049883619863*z^8\n",
      "step:  62\n",
      "shift_factor:  3927462598524689657222615461883444387631463865338220624935083863193350221524879246678161222509039013352406537658974*z^8\n",
      "step:  63\n",
      "shift_factor:  3072116583530028842547318846632766038908268302187661208269325581620438644688407758202243525456917507149798163869663\n",
      "step:  64\n",
      "shift_factor:  811666002434027169334474947537715921289595187773293512281910998520671801931914235156492668164807851921878073571641*z^10 + 3190743552787640224083314878198188235267287632165714373050147137603359848558923629286194960964207812116016198988146*z^4\n",
      "step:  65\n",
      "shift_factor:  2821436303612792338860008153067923800096550109165086208722588281876477481175023884955537595043202131706134606593972*z^10 + 1180973251608875054557781672667980356460332710773921676609469854247554169315813979487150034085813532331759665965815*z^4\n",
      "step:  66\n",
      "shift_factor:  2243399446082648892118350322965024978836805966239761257883120289022967231032790054705204825676251133681587649872351*z^10 + 1759010109139018501299439502770879177720076853699246627448937847101064419458047809737482803452764530356306622687436*z^4\n",
      "step:  67\n",
      "shift_factor:  215875937958318727273550618184357994408007682022089606605935581638635826722769884560777842675892680979186615308882*z^10 + 3786533617263348666144239207551546162148875137916918278726122554485395823768067979881909786453122983058707657250905*z^4\n",
      "step:  68\n",
      "shift_factor:  467268434014400077094290260094097139466051101641841878742546633674448986824138133233023283142595744484578418751211*z^8\n",
      "step:  69\n",
      "shift_factor:  293990948858230467141638456327214769833847794891831614965596771729868038967127889454908035683982432603756417494943*z^8\n",
      "step:  70\n",
      "shift_factor:  1176890287572250265283730692502609995503419403929290946288300829194546581445294126569138561314726541545820097799314*z^8\n",
      "step:  71\n",
      "shift_factor:  3666017593505834269731972515671133143670854771306457507402014898477395574290166405495877981656134017888798305183326*z^10 + 336391961715833123685817310064771012886028048632550377930043237646636076200671458946809647472881646149095967376461*z^4\n",
      "step:  72\n",
      "shift_factor:  838583806844183100888317846622383628902218630578469339810563328782882936319783442610518994480792984130793492627970*z^10 + 3163825748377484292529471979113520527654664189360538545521494807341148714171054421832168634648222679907100779931817*z^4\n",
      "step:  73\n",
      "shift_factor:  3291090128954929255387090215691655800270757219092665157841546464186517472132481632075699395769317404526439266813926*z^10 + 711319426266738138030699610044248356286125600846342727490511671937514178358356232366988233359698259511455005745861*z^4\n",
      "step:  74\n",
      "shift_factor:  347468432328630520458402527652484657751365596502934607457554522410679663198314558499337821524847121896829520685362\n",
      "step:  75\n",
      "shift_factor:  3813141511491170738742557349904366857613024424482266868861383667825515356692223749673754515662514808977302206521802*z^8\n",
      "step:  76\n",
      "shift_factor:  2553436429750862162763458196051913218436895207474628369432560179630502732802396339504613239315197836746640209378696*z^8\n",
      "step:  77\n",
      "shift_factor:  59491705561286015451809463286925740518468828887570023657794651520877869617079818544642331964054743162944184575823\n",
      "step:  78\n",
      "shift_factor:  3462056439743320670536765706252849785586447910738534782837555738955181924503985998569355911750191626276507125166997*z^10 + 540353115478346722881024119483054370970434909200473102494502397168849725986851865873331717378824037761387147392790*z^4\n",
      "step:  79\n",
      "shift_factor:  3706344817950485762910914691077504964931487581727049938305623930538926254523334443863096530754875196552545340241045*z^10 + 296064737271181630506875134658399191625395238211957947026434205585105395967503420579591098374140467485348932318742*z^4\n",
      "step:  80\n",
      "shift_factor:  2254327371370505140144671551641895020185877405833261081547327032951718327003889154084802859038417671682814403915732*z^8\n",
      "step:  81\n",
      "shift_factor:  3457938691407723371584503509839683475593263703393652352028270549033537234633576612376979844180146989544456733517250*z^8\n",
      "step:  82\n",
      "shift_factor:  913422258884417973503042301884891751057066937414175370408676742510465266552455609910060300195376772759666630731086\n",
      "step:  83\n",
      "shift_factor:  2153478880653526578868084888107689752011111975328768201470924266105965049612426626416800982709863926758560824376484\n",
      "step:  84\n",
      "shift_factor:  2134788649079484113213830805821888416437658205135031750368924181791963929287067378624639425745171439125345042279794*z^10 + 1867620906142183280203959019914015740119224614803976134963133954332067721203770485818048203383844224912549230279993*z^4\n",
      "step:  85\n",
      "shift_factor:  2860625005231461424323288711485546142925515718500065002276452900723565602540288395640333796630290118600360569861488\n",
      "step:  86\n",
      "shift_factor:  1646685183018426750871936943980062494189257325352039431310416542228712345799024334601569735878293743094922125405711*z^10 + 2355724372203240642545852881755841662367625494586968454021641593895319304691813529841117893250721920942972147154076*z^4\n",
      "step:  87\n",
      "shift_factor:  898700304476891797429658098970406936651919412051547793314498795727125912097177486259787166248896776569612768038062*z^8\n",
      "step:  88\n",
      "shift_factor:  3417531232525154662971445764186756873389041465768302465413032048187947706454123179280992709652178291495802847351349*z^10 + 584878322696512730446344061549147283167841354170705419919026087936083944036714685161694919476837372542091425208438*z^4\n",
      "step:  89\n",
      "shift_factor:  403271175774108489489924344982604511828164249878800514007133850660846166170728453558160326454564543803683914818201*z^8\n",
      "step:  90\n",
      "shift_factor:  2397692856134293283444162060953529656575424394773436749454697007613509022908976017476000919148588719935903528834329*z^10 + 1604716699087374109973627764782374499981458425165571135877361128510522627581861846966686709980426944101990743725458*z^4\n",
      "step:  91\n",
      "shift_factor:  1104942445678312349050360810678658213311239038011071499618388096593580533918309654973271570104174017347107726699170\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step:  92\n",
      "shift_factor:  2303152531903332885352998730842834793827031895843825271060199632538010676038723305995735561007600765208071217358773*z^8\n",
      "step:  93\n",
      "shift_factor:  974833637427145497985780979499899906750133315749477630508770310865643808987599436557714055442033536212730160537656*z^8\n",
      "step:  94\n",
      "shift_factor:  496759270369257861894248708731922721532825288646560940159903959301728739633353049730945475004596036432135138762085*z^8\n",
      "step:  95\n",
      "shift_factor:  1158232069042412590935463333175350040031882702990401944447577093671864025418667178000856813684342439323144492887490*z^8\n",
      "step:  96\n",
      "shift_factor:  2588232799296220637380556416257724803884710311749604970813605095380402294342497712798939621406242161577680497627968*z^8\n",
      "step:  97\n",
      "shift_factor:  3334764018491033047723194134748359615004467523385447436859177944258484801102778903602451440069804989591497777582565*z^10 + 667645536730634345694595690987544541552415296553560448472880191865546849388058960840236189059210674446396494977222*z^4\n",
      "step:  98\n",
      "shift_factor:  257169321251838603387355010946796160972270020849065888415975123792374516031071641057377160768436914292060600885045*z^8\n",
      "step:  99\n"
     ]
    }
   ],
   "source": [
    "for i in range(100): \n",
    "    f = Fq12.random_element()\n",
    "    f = f^r # it will always come as r-th residue in the honest execution\n",
    "\n",
    "    wp_shift = get_pth_root_inverse(f)\n",
    "    w27_shift = get_any_27th_root_inverse(f)\n",
    "    \n",
    "    f_shifted = f * wp_shift * w27_shift\n",
    "    \n",
    "    print(\"shift_factor: \", wp_shift * w27_shift)\n",
    "\n",
    "    root = h3_ord_element_lambda_root(f_shifted)\n",
    "    assert(f_shifted, root^lam)\n",
    "    print('step: ', i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0adee73f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0fdefc7",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.2",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}