p5.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nNIU_ESTUDIANT_1 = 1459132\\nNOM_ESTUDIANT_1 = \"JHOANESTIBEN GRANADA RUIZ\"\\n\\nNIU_ESTUDIANT_2 = None\\nNOM_ESTUDIANT_2 = None\\n'"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# IMPORTANT!!!\n",
    "# [1] Introduïu els vostres NIUs, noms i cognoms.\n",
    "# [2] Desar la pràctica posant els NIUs dels membres del grup tal i com s'especifica en el nom del fitxer\n",
    "# [3] És imprescindible que el worksheet es pugui avaluar completament (Cell->Run All) sense que es produeixi cap error de sintaxi.\n",
    "# [4] No s'avaluaran worksheets que no compleixin els requisits anteriors.\n",
    "\"\"\"\n",
    "NIU_ESTUDIANT_1 = 1459132\n",
    "NOM_ESTUDIANT_1 = \"JHOANESTIBEN GRANADA RUIZ\"\n",
    "\n",
    "NIU_ESTUDIANT_2 = None\n",
    "NOM_ESTUDIANT_2 = None\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Definition of Test Cases ##\n",
    "TEST_CASE_1 = [(7903126559821964686463557340728820271223543529858019901688309838372108285307732092722360827326246211951376647434255034435564932384099820753498888781877615L, 317972381367064990840510369007541461276421699796106904494686897344835795539271666892617538300755232236454457559774034880884430208166890487378588726592003L, 7592548777848414075243152464261265522912583433632018101996423752018161580785582121152523027483451723740126100470276926899087407703025689336574991899612012L), (152074104640245865992544923627127385070409636762268453615601640828536915249239636592446444995690082201486287476818186937523680842762470853746484001754610L, 3284555144292363429064093827579288695922287488582305823291375087777601747108772322465274421396420144882333019128945395479107224598150323742537126430517439L, 3159180499746066425254825676564286213733923755718231242727849286128673993619250228491278655423833167038161052374052212357729476839611145507131502028907853L), (5988684292561848524790921639531339144574702278362547798697206947681910248908307527142826680666745274020791735971963366779862125467702681048924497312816590L, 3521713949347709828296048327570931513851379393204131904435802850806724899745970487193946162375829096170740176250209901675251928675536265864750081016499632L, 2587170363082959993601397208812113250116107831369749113435817987199082636970282382249684340256094561851854720507384379569179343348623070227841688270246014L)]\n",
    "mTest = 16962\n",
    "vTest = 29424\n",
    "skSignerTest = (39407,27013)\n",
    "pksTest = [(28907,18541),(41917,22491),(39407,26077),(32743,17539)]\n",
    "xsTest = [25816, 11546, None, 28447]\n",
    "ysTest = [15266, 38905, None, 11683]\n",
    "pksTest = [(28907,18541),(41917,22491),(39407,26077),(32743,17539)]\n",
    "expectedSigma = ([(28907, 18541), (41917, 22491), (39407, 26077), (32743, 17539)], 29424, [25816, 11546, 4541, 28447])\n",
    "expectedC = 33272\n",
    "TEST_CASES_2 = [(mTest,vTest,ysTest,xsTest,pksTest,skSignerTest,expectedC,expectedSigma,True)]\n",
    "TEST_CASES_GOOD_SIMPLE= [(10129129434858183542827359596490740841457608537607360302303045991097046494779583439281170857567862816295188929325116572603485035238219730061150184047912248L, 308951784973181806918324464673492508514374652806389180386062557676764787111304609504166047648837840032865078304630077702740368399358867025946025778790016318975185524313087077419341830377385671360875466299928559229807733580529899411797402373202458587330769999642405079655814737675733677114412879264093681389178L, None, [None, 275852883580796798760160078636444627637458450026752205535545910200048670491517749252146229819277300845963022539286620357655978594839786100529027547072814728583240899077640400524779850766004037224075419253721195548593205315085360059510410171484938968418417198225313815768510295647607064825404272446639063799363L], [(127304889973075553401792986592452370351913952833520554455415833081723619887508365393998374504861082111409059769059142565217479874599162282728640167597219594706454440315517181114450677091668602690985792067737349082457377056059048608209421369348283496782924084005710629218930808396083475099659170182265197786443L, 65537L), (141816967876424155745231802255735720317376672471719245346183151316105641007898156949925632014859228095333334727405661370268471612228701953560211036555975770114202535861370184169877060942556470543341543618741993577430224435195450688892530529517499916978791893697988270614423932755870165025316683193254060965013L, 65537L)], (127304889973075553401792986592452370351913952833520554455415833081723619887508365393998374504861082111409059769059142565217479874599162282728640167597219594706454440315517181114450677091668602690985792067737349082457377056059048608209421369348283496782924084005710629218930808396083475099659170182265197786443L, 33533184546213639293454877817805289674307499088531140143183904153223291424966918104225001740656680355970743225861238355483915270384749660294864202103099035244015928844067519944913261693794015614249984933503162449055748426009416576821783349677558067467887957820565924903676837159464764903450475709055751369153L), 115206297857546504491932810142611362622301271362609548867784319891163765104682568579567617655909827947108937665661068511257674323880289806241196892172885262809825528001621683047661049819954726414481754521674531839886756562141918867102728979395866049937994842591819511815159833899270668139010407741513822849718L, ([(127304889973075553401792986592452370351913952833520554455415833081723619887508365393998374504861082111409059769059142565217479874599162282728640167597219594706454440315517181114450677091668602690985792067737349082457377056059048608209421369348283496782924084005710629218930808396083475099659170182265197786443L, 65537L), (141816967876424155745231802255735720317376672471719245346183151316105641007898156949925632014859228095333334727405661370268471612228701953560211036555975770114202535861370184169877060942556470543341543618741993577430224435195450688892530529517499916978791893697988270614423932755870165025316683193254060965013L, 65537L)], 308951784973181806918324464673492508514374652806389180386062557676764787111304609504166047648837840032865078304630077702740368399358867025946025778790016318975185524313087077419341830377385671360875466299928559229807733580529899411797402373202458587330769999642405079655814737675733677114412879264093681389178L, [3184346640662790612376960671445461431292379194525312588671422383745820847002696111319874829531683030009388073678567249730389624738661329413108129852911757542344526361561868266703735783398308415546479306220173301738986340826104462353192314510304244410465319057134039948332189115933408984678794977303681042455L, 275852883580796798760160078636444627637458450026752205535545910200048670491517749252146229819277300845963022539286620357655978594839786100529027547072814728583240899077640400524779850766004037224075419253721195548593205315085360059510410171484938968418417198225313815768510295647607064825404272446639063799363L]), True)]\n",
    "TEST_CASES_FAIL_SIMPLE= [(744967814891074442963828085657156080182017120929898948092325187286035469979575900811011945812266853962624939245407048311743262817832872455252400433176160L, 55994092880656773632665258367736154344734329573068374639167348481016644538672116709975757202116024126627108058773846524661176247245962512831822859173192746505530064909747817072578001149606465761702060525337857054790105092603604174627305145370642015114163999105124138248761133723461085474172893936303559980430380705864234304772142442886223170097805766399997645613315883906744551213630592842335629449725008259360245830846012583831127602964463341022824548629416511227115935303701317842796808480431418507739483168490691701884110774481879256922146482860552029076941088374196295737905451715544553626592199528638157424025631L, None, [55171261126549394145537544858958462687108449309722180756700588337774158560827599745574698843520283700625424855903436963842058241589455205699624201059589680030804600290131679711487297333171249492817944343180274784950746952861766370766058542065549276939969440859597597305244753010652496738604269633132035553322057013982927934350908101251268001864359757226231044726811676981417890621259832433487507756248306750907837816462495346547691366800356609499066716626779011577593694721678043000961332098561665907680417519251074146014786372674264826381870394382146735607350737608524823743144737804402881056699034151021686857526834L, 63429500718971834007966619605250492937609690250283466321257513971357829109914945288896061674418014288807459493632749810521221677202620941393938217731472604971681042087611616286104177087955262867919233632377207953767339429949398184315565655232121197639600863285725691188454950954966898811141769293815291544055864595529399415878638215277861839173222752098273758001511142791799733307818667127245083665212874145126723517278246714706368833001872907790874781963180230281606513580485406389701592483770985974311638819118762305570995794331415576799050353697876205863024361231863449409613724224856874080831500325656561149222392L, 34225382660793845817478715088821197016363682080370382540857701018323841083129258070505306141378738744834441951751095363376112246762333362440880307912100119429384160592606996787123321979658359360050056942463707946599221602524531912411761854986384131715040140888506409198559915534776662859358870954238656632592767466236517056775742472007929931072376822421839339406760811976459023742185603391541276066907606153475269659527265577001114367110646327392044449308704964536124565056014161130498376136579211319089877025329900075160953644420792879503038310078558263636101084818965737074041365502564747826836353342728209822702298L, None, 61192023515565831620950286967561806729916502641291680999166467134638808663671129355439873937230454145682305477017187179786508514623568359775827985752585293514821631275212129721015764622461367114438471358935590786691863055938549172738584169789767561713529463692242981501020374686574113608345418317545467065331678053949179949436702175867892521927026744219280403918367449362293024390355850016940774330145731584977348546231486399937341674969968604473572071021452128929881566148658969477480110134516210109365421527817763086603658983754847370504946635869923294297943596419897745787618565572337594970049153251000055054309467L, 34828084457308561234293639233531759975784350518929684306219756647220299801469574451557108384949224305413280231509052629355110355651321522783470397916948429717632171116200024516829997425756088495762432405221047878846311280778379284624634463230186272137408238568149586466087913555563534259067016390916092644838018580458619598945958463520313383757425401821920586712782550153037534058581283090697276577033370974898896501714153013124120770293131302404457059655255853036895385981691062587072331913386712706039268320719386683683205279946704365717557184798089540117335883239101212004070862935897288236822441601187630549176706L, 33484838212020037673909364669659971602003511371373526021096121352917171630077609048518236250999513559946678673178399926308938071038737622129267192353423831154458457663514032637182689264430864550093463145030613227797857164446554969018453477181262201539750466496030345064875272403199951246555374572742002403384848661354619688706058411330281176810573352958479499559192120620371314725463284691127616757368688030603701572779817098866021713664127964146677942702043102017868670279822537145136709863996216565421667324161854429588668639006647003604274141978490101495433862926117728100921973770397110403019883081362338482683207L, 46486167746023721269535263515246143579447160065405650580348518081488421280172006229924948678413431811026842969953736546146820231486455696695696675440691612316380398576393392917368972160102105754091579865562228132719230231653017105734973074160534560825826251503668633865130511587587748288237688423533048773381958919099393264890816936001380910166180938510849290713638376228508063250586976252744543259968586996193869353062532868310405788484073886694394919490682109146213510278941143899550667553399346189925989184755000256908331169653746384358064020740588224075071936410184504050115681139906076842913131099995158001889076L, 63312380672805206705603413866800038253237970556537011488954712896325376728529617537126768699090882629809836792680629964946306016741819903058515351987160814938469046521695175683374668671750126471630610604709231071687463408080557561168973637276821670742323999663672657765601704447625417091680543253759011549721097770867457915795745551524756280837361587636473174507721883283180779106716588010382013685136402088395423442673509308980172109722009601867412639401973109169211655964838800339142317042048477114601471307878300348204799462250433193870307763436456927727889045936033541241967126110791752093633941662305024939296219L], [(19334923526894269333900061758322218111054900093145459552131309570588129544931717812595515843482159367912007028838405623700893812620654591082115029795013706606477997706177862943801334448591237567927896273453105336462320439579129832647391853828640783580241461386222630688800564566121327834558915211258563442107734640653701053666558089201366565311484766827264845932904439941079420049532963609455342083334306066495248343138858495301293853553067216093607937449555952474853680107476744473116881741918045183669823377457098801066728201724588709812361262170662134956395776589267648776660214309475119962572292607264895762357289L, 65537L), (113851910169096446933837680899471735715869258414819274565947251718310551893368915002527349880671186864098752305812904122448137250681941351745582171613226380441658346347447469671659358461682447585010038732467148083360756576894369834885610187935543071949809966611827854607833089489756869407302465213066754423887L, 65537L), (171177684385779675591624450233806276789083132565466328084591506946479891001944727155438081471743020980503726262532361496424540118792363614669356573591300606457869426910378715545405763423733848130715894903899433136503367064475395512328168560267610901198536445547718612594729635751759291941969066907836357940227L, 65537L), (153246463457596113886592261221717295183515466607349238031231999907487337043655603750111897812652801235450817852486234475054309317039710344143297182990904557774538758289711928147615208914582453524744072424140216433676150341174596040444995246128094495330985566003011447992788356991221844186567466227139449559941L, 65537L), (142230052190653899743704438315707855378998114403333301332042355080271681851512962512761574742590371267894969905870732053200208820861219468496497514782656853026745040565688543545686828969107037349555315949633212257256648902717716508527414480272699312656200513643785741623580260209862330957717076899951977666827L, 65537L), (22457038975209759107260433015520056676224510008426561856446044954471366981083780984936303296483548558020538261083928883893221693218681655203086379651030121334588486017046838412692353129176467155434853557322101193128523865803171364773710321957468267257968786689864103117068034308016621957063622805622799138916940117679966751805490579483248432200335463373192170421226731163419301904654544825026679730699976351932781555019713530504895133056462305138384189838384802099476567635193218613875898852458314426356077067416519242183845611665303154734410238216573779926129868778721060626457572884390110119956417630569081285494493L, 65537L), (139371315875484172686461969951230447602190044125904491719025799450838361402819098253744160806177577349935009742400785561256159413620562443777013831195056341006097289252426987662856809252850091449474038860154471985053239485767960401611592570427356862159466662568502334553249020506115895126592666661469267376141L, 65537L), (148903432902925009521898102421314318299654782054373079089181965177605847107159737305442513928237879533913969377208444054452961042207849245396867918817744599657596090851078713466150631462969340734917405271475264267928028417544898355327508864401557192896146246943620186443613197811653403939346066348190545783439L, 65537L), (25537228895971725212781338014119609096286519938538789240351461500375410183461220991923027832705134665743526894509441830838181190837753102994033621585449575150046877481262518523628700958025094082051691439516528700151584070582437502948103424748179986008462306944933435583850728111020121185982288106841426856351798762720740211626404441999392754826100053968913379890722554332747081209614687365375675951525326140314644847268810705186662679213999189956400655657954257527341457762219350083924462462898654677355646286321102857545603837502869521275211100528218946324209113430217606355188537336461154307334687802945993975198271L, 65537L)], (153246463457596113886592261221717295183515466607349238031231999907487337043655603750111897812652801235450817852486234475054309317039710344143297182990904557774538758289711928147615208914582453524744072424140216433676150341174596040444995246128094495330985566003011447992788356991221844186567466227139449559941L, 49202924822233813393986211767816276687238238679705245382809462472394960801876820942518799361793189245713964771839042767049037591729093261233551418656554513991062995892088032201153451605232184803374130732577043657806036436945249944220097788657891188869753980661434044948441108795876575414360099303213585177217L), 7040079989666008350617741697605128814234902152975607706551245747893492113947613258055507031364214050494603891979822090459814970057526220376568972145841481940834917739176758259285065602982041881610680945719269167367355947672315968699503242678388206874740276871554093166935373562578453725137509068053763537417410915570014250502760207926335946985321681920587862803605754998955373350417208775413963599361500770172734699981069518620479678014593199859969663659659560791563831030054087934553082278414013727466749623860484909371518640858262984067493663379257168473591410505141963748749721902928775765770475956479735645015640L, ([(19334923526894269333900061758322218111054900093145459552131309570588129544931717812595515843482159367912007028838405623700893812620654591082115029795013706606477997706177862943801334448591237567927896273453105336462320439579129832647391853828640783580241461386222630688800564566121327834558915211258563442107734640653701053666558089201366565311484766827264845932904439941079420049532963609455342083334306066495248343138858495301293853553067216093607937449555952474853680107476744473116881741918045183669823377457098801066728201724588709812361262170662134956395776589267648776660214309475119962572292607264895762357289L, 65537L), (113851910169096446933837680899471735715869258414819274565947251718310551893368915002527349880671186864098752305812904122448137250681941351745582171613226380441658346347447469671659358461682447585010038732467148083360756576894369834885610187935543071949809966611827854607833089489756869407302465213066754423887L, 65537L), (171177684385779675591624450233806276789083132565466328084591506946479891001944727155438081471743020980503726262532361496424540118792363614669356573591300606457869426910378715545405763423733848130715894903899433136503367064475395512328168560267610901198536445547718612594729635751759291941969066907836357940227L, 65537L), (153246463457596113886592261221717295183515466607349238031231999907487337043655603750111897812652801235450817852486234475054309317039710344143297182990904557774538758289711928147615208914582453524744072424140216433676150341174596040444995246128094495330985566003011447992788356991221844186567466227139449559941L, 65537L), (142230052190653899743704438315707855378998114403333301332042355080271681851512962512761574742590371267894969905870732053200208820861219468496497514782656853026745040565688543545686828969107037349555315949633212257256648902717716508527414480272699312656200513643785741623580260209862330957717076899951977666827L, 65537L), (22457038975209759107260433015520056676224510008426561856446044954471366981083780984936303296483548558020538261083928883893221693218681655203086379651030121334588486017046838412692353129176467155434853557322101193128523865803171364773710321957468267257968786689864103117068034308016621957063622805622799138916940117679966751805490579483248432200335463373192170421226731163419301904654544825026679730699976351932781555019713530504895133056462305138384189838384802099476567635193218613875898852458314426356077067416519242183845611665303154734410238216573779926129868778721060626457572884390110119956417630569081285494493L, 65537L), (139371315875484172686461969951230447602190044125904491719025799450838361402819098253744160806177577349935009742400785561256159413620562443777013831195056341006097289252426987662856809252850091449474038860154471985053239485767960401611592570427356862159466662568502334553249020506115895126592666661469267376141L, 65537L), (148903432902925009521898102421314318299654782054373079089181965177605847107159737305442513928237879533913969377208444054452961042207849245396867918817744599657596090851078713466150631462969340734917405271475264267928028417544898355327508864401557192896146246943620186443613197811653403939346066348190545783439L, 65537L), (25537228895971725212781338014119609096286519938538789240351461500375410183461220991923027832705134665743526894509441830838181190837753102994033621585449575150046877481262518523628700958025094082051691439516528700151584070582437502948103424748179986008462306944933435583850728111020121185982288106841426856351798762720740211626404441999392754826100053968913379890722554332747081209614687365375675951525326140314644847268810705186662679213999189956400655657954257527341457762219350083924462462898654677355646286321102857545603837502869521275211100528218946324209113430217606355188537336461154307334687802945993975198271L, 65537L)], 55994092880656773632665258367736154344734329573068374639167348481016644538672116709975757202116024126627108058773846524661176247245962512831822859173192746505530064909747817072578001149606465761702060525337857054790105092603604174627305145370642015114163999105124138248761133723461085474172893936303559980430380705864234304772142442886223170097805766399997645613315883906744551213630592842335629449725008259360245830846012583831127602964463341022824548629416511227115935303701317842796808480431418507739483168490691701884110774481879256922146482860552029076941088374196295737905451715544553626592199528638157424025631L, [55171261126549394145537544858958462687108449309722180756700588337774158560827599745574698843520283700625424855903436963842058241589455205699624201059589680030804600290131679711487297333171249492817944343180274784950746952861766370766058542065549276939969440859597597305244753010652496738604269633132035553322057013982927934350908101251268001864359757226231044726811676981417890621259832433487507756248306750907837816462495346547691366800356609499066716626779011577593694721678043000961332098561665907680417519251074146014786372674264826381870394382146735607350737608524823743144737804402881056699034151021686857526834L, 63429500718971834007966619605250492937609690250283466321257513971357829109914945288896061674418014288807459493632749810521221677202620941393938217731472604971681042087611616286104177087955262867919233632377207953767339429949398184315565655232121197639600863285725691188454950954966898811141769293815291544055864595529399415878638215277861839173222752098273758001511142791799733307818667127245083665212874145126723517278246714706368833001872907790874781963180230281606513580485406389701592483770985974311638819118762305570995794331415576799050353697876205863024361231863449409613724224856874080831500325656561149222392L, 34225382660793845817478715088821197016363682080370382540857701018323841083129258070505306141378738744834441951751095363376112246762333362440880307912100119429384160592606996787123321979658359360050056942463707946599221602524531912411761854986384131715040140888506409198559915534776662859358870954238656632592767466236517056775742472007929931072376822421839339406760811976459023742185603391541276066907606153475269659527265577001114367110646327392044449308704964536124565056014161130498376136579211319089877025329900075160953644420792879503038310078558263636101084818965737074041365502564747826836353342728209822702298L, 7040079989666008350617741697605128814234902152975607706551245747893492113947613258055507031364214050494603891979822090459814970057526220376568972145841481940834917739176758259285065602982041881610680945719269167367355947672315968699503242678388206874740276871554093166935373562578453725137509068053763537417527870616930891085424960400069649328665435651838859253594337131364119872383361884664918775473448781311630696023229526096736307503988444103292378253262920958613844335331302369003861142659771900527276083109511097661783430997996472083784006838934800385175616463475095353196208038374224391559297361008118392747065L, 61192023515565831620950286967561806729916502641291680999166467134638808663671129355439873937230454145682305477017187179786508514623568359775827985752585293514821631275212129721015764622461367114438471358935590786691863055938549172738584169789767561713529463692242981501020374686574113608345418317545467065331678053949179949436702175867892521927026744219280403918367449362293024390355850016940774330145731584977348546231486399937341674969968604473572071021452128929881566148658969477480110134516210109365421527817763086603658983754847370504946635869923294297943596419897745787618565572337594970049153251000055054309467L, 34828084457308561234293639233531759975784350518929684306219756647220299801469574451557108384949224305413280231509052629355110355651321522783470397916948429717632171116200024516829997425756088495762432405221047878846311280778379284624634463230186272137408238568149586466087913555563534259067016390916092644838018580458619598945958463520313383757425401821920586712782550153037534058581283090697276577033370974898896501714153013124120770293131302404457059655255853036895385981691062587072331913386712706039268320719386683683205279946704365717557184798089540117335883239101212004070862935897288236822441601187630549176706L, 33484838212020037673909364669659971602003511371373526021096121352917171630077609048518236250999513559946678673178399926308938071038737622129267192353423831154458457663514032637182689264430864550093463145030613227797857164446554969018453477181262201539750466496030345064875272403199951246555374572742002403384848661354619688706058411330281176810573352958479499559192120620371314725463284691127616757368688030603701572779817098866021713664127964146677942702043102017868670279822537145136709863996216565421667324161854429588668639006647003604274141978490101495433862926117728100921973770397110403019883081362338482683207L, 46486167746023721269535263515246143579447160065405650580348518081488421280172006229924948678413431811026842969953736546146820231486455696695696675440691612316380398576393392917368972160102105754091579865562228132719230231653017105734973074160534560825826251503668633865130511587587748288237688423533048773381958919099393264890816936001380910166180938510849290713638376228508063250586976252744543259968586996193869353062532868310405788484073886694394919490682109146213510278941143899550667553399346189925989184755000256908331169653746384358064020740588224075071936410184504050115681139906076842913131099995158001889076L, 63312380672805206705603413866800038253237970556537011488954712896325376728529617537126768699090882629809836792680629964946306016741819903058515351987160814938469046521695175683374668671750126471630610604709231071687463408080557561168973637276821670742323999663672657765601704447625417091680543253759011549721097770867457915795745551524756280837361587636473174507721883283180779106716588010382013685136402088395423442673509308980172109722009601867412639401973109169211655964838800339142317042048477114601471307878300348204799462250433193870307763436456927727889045936033541241967126110791752093633941662305024939296219L]), True), (12256227178076344826669033823176432617918899329738454151560819638879389401958844414877891069265145126560842193999360865028898124993571435495429693200212029L, 35061494125325478119012833721002854170946917299348124063925749509760051909818455498975436086004245273026049182601138465018855421297611304651476643609656704317444204341411807013281936334969540329054406531686334368338133014299892253795593226125255598214686531781142330861060772141337496203348742778160517177723477316214488549187920479830976466368935002482762668228626118021725788300586454076709167082443008980392398823105502205936588110537023036824171822880953118901867265837733804723894054692595919712806219982689054859660495650318030396839954758996493583182865395217080281973882287786992929194427971153059490879094940L, None, [None, 62142483302580248642460374592929955267421332257263570561658433659044129593601571304566051853563473659257302848348573763838656391978586476016352714036955346996277798279120388018651622719787145461982087406002417245819053773915233992759218525204668059697879624489573674811669304896891653768859668280712475791531411466801422844112061931823001061457237128834098826009266229215838832271396453420794737140353339699480418904198135671019787370428311872741844798539582895238931039804206642356883007782435670144011393443740209412846796544601833529229709899216548644809566482827567743433728100191558974471855105909286442724072989L], [(111470411935170241543551257106897497138829981483204367396670432226512417090631902891282991436866804623749066151882779710836829951301183773661591766866798494936987719782612481394841194977844274189357609507840617793878873198902046774606506989858536293601781723866301190836603429925933737830498698583399956720609L, 65537L), (18667361103925122760111871051235348692944606620840885160951530461735800667340043172042764548404711202726365011342581856571776867477233352947342590083069548851971129919490000094654530834838220111197897830912795519369519385340491590261049059675141827255619323752398237432429317336432368108850520137563055325578468805010864974863875892581859909781291536546918254756694147927364876363063961720431731298130739783861884308296554844122319539929151814037553057691300605766896221966611745314826619981117353802480316023049608573755784643216899327530940190426687087273875657107276445467598360303712465243504049404130775771306901L, 65537L)], (111470411935170241543551257106897497138829981483204367396670432226512417090631902891282991436866804623749066151882779710836829951301183773661591766866798494936987719782612481394841194977844274189357609507840617793878873198902046774606506989858536293601781723866301190836603429925933737830498698583399956720609L, 60857398706690743281326029254997824856605226627234268664309749684370878793701412720297014413401502501453249109882445916867445498841209628478748697964417800501728351366141603723796846795645418419297578691976083046624690449266544346333558571489598108361968970648510776644714721431261538529062550323240009555473L), 62142483302580248642460374592929955267421332257263570561658433659044129593601571304566051853563473659257302848348573763838656391978586476016352714036955346996277798279120388018651622719787145461982087406002417245819053773915233992759218525204668059697879624489573674811669304896891653768859668280712475791531411466801422844112061931823001061457237128834098826009266229215838832271396453420794737140353339699480418904198135671019787370428311872741844798539582895238931039804206642356883007782435670144011393443740209412846796544601833529229709899216548644809566482827567743433728100191558974471855105909286442724072989L, ([(111470411935170241543551257106897497138829981483204367396670432226512417090631902891282991436866804623749066151882779710836829951301183773661591766866798494936987719782612481394841194977844274189357609507840617793878873198902046774606506989858536293601781723866301190836603429925933737830498698583399956720609L, 65537L), (18667361103925122760111871051235348692944606620840885160951530461735800667340043172042764548404711202726365011342581856571776867477233352947342590083069548851971129919490000094654530834838220111197897830912795519369519385340491590261049059675141827255619323752398237432429317336432368108850520137563055325578468805010864974863875892581859909781291536546918254756694147927364876363063961720431731298130739783861884308296554844122319539929151814037553057691300605766896221966611745314826619981117353802480316023049608573755784643216899327530940190426687087273875657107276445467598360303712465243504049404130775771306901L, 65537L)], 35061494125325478119012833721002854170946917299348124063925749509760051909818455498975436086004245273026049182601138465018855421297611304651476643609656704317444204341411807013281936334969540329054406531686334368338133014299892253795593226125255598214686531781142330861060772141337496203348742778160517177723477316214488549187920479830976466368935002482762668228626118021725788300586454076709167082443008980392398823105502205936588110537023036824171822880953118901867265837733804723894054692595919712806219982689054859660495650318030396839954758996493583182865395217080281973882287786992929194427971153059490879094940L, [62142483302580248642460374592929955267421332257263570561658433659044129593601571304566051853563473659257302848348573763838656391978586476016352714036955346996277798279120388018651622719787145461982087406002417245819053773915233992759218525204668059697879624489573674811669304896891653768859668280712475791531411466801422844112061931823001061457237128834098826009266229215838832271396453420794737140353339699480418904198135671019787370428311872741844798539582895238931039804206642356883007782435670144011393443740209412846796544601833529229709899216548644809566482827567743433728100191558974471855105909286442724072989L, 62142483302580248642460374592929955267421332257263570561658433659044129593601571304566051853563473659257302848348573763838656391978586476016352714036955346996277798279120388018651622719787145461982087406002417245819053773915233992759218525204668059697879624489573674811669304896891653768859668280712475791531411466801422844112061931823001061457237128834098826009266229215838832271396453420794737140353339699480418904198135671019787370428311872741844798539582895238931039804206642356883007782435670144011393443740209412846796544601833529229709899216548644809566482827567743433728100191558974471855105909286442724072989L]), True)]\n",
    "TEST_CASES_BAD= [(304212199735718425513987963153370842576981483791022853506122084897617232680961446641145943588783187627748887098150899521401977283855303053786958006156870L, 56157944529137268655768625577864577628449673518753467206780991927626506971775069113166872726868492948961041822800259274906061195494771205837593075897139930526920179428319047262222071033942775916357670909596893050891270758893269511972926338537566037475984806844732102655018803238407291845867346769267119985559944739646695093963583900910301912739922368655670975894111706609625448341049618968600696642899641885908479838160049691650927926378444476392553822529437735642186361552621550490565886537610498041436277261319837954869834413878122964366631066351802779958055054755382549276859118640163060031962318127695116963435906L, [], [43666126423359818380299107289539747128738536969785888655112588544344070445080237638473344644805625962352840454531908130469781097458920877178092475991711673468858377732437664336055622262804235972112656394602331507369156291848317545084231641002779756646348796931777531819158550170274857047537475213786243751459741445629743222739618712812292584679013447004127763579836212668370543961658188375607768683534043138128456253062650498608435617833109503260351415718325281009715647231951765057758209559382684064032140476799626636484465051431967427217096612221890997281917700233541009906920187472906593815359552340168414573587827L, 63310018548215154951753262085366489704926469197979055962810741589023818469565079827603734365754923864284185777713176773105372710496227290019561141774874191852375175105533469998029504849893342447518985242802079995088122136720058582874985911595374017113199060255986962097113279423160330889637113823549540590411118857129560292248431027623452211420036972531159260932060307180622475910155565054570636963664614459748040557922099034293584859672315011593754554719500086380511884307485451179954970966850983488451374197527674431241875462358226171696005832608672745585287478791223960386561421125925087877951122898425910769254125L, 45831315220134719282322451308786544910389438862112028568141337578335515961471700697961221953657710740326075605594935396234298619991090117922186913706395695544726857895275390242206459198349245109081891127288030835957812351968607974737292371707262634582001266087246684661884533004714257874881396005561543687898684872185219297203816572165235002087342576115247679833076454906095402563715907156495861997710483997111035067395687389887655379132196797099138266509811474393468275347420215503875786869474241134726128554581325206553567614662910912799651913701506105738877348728691659669492527792470836815746115145039906723647630L, None], [(23886717043623017856905477973250787179871536663090941133210085363705816721313635907300739148511337307535528348855556093231415361339189208774490910360656473080818431391131661802148736593752918669927913465249400970305332562849920944684763363605717386800704802652405511532213282620518506210701738791332605203954378018871366184513133060323565467367530314499023897162321578840937332724700159499951709154651616453566567668135584098478930096378727750433484195143022627106156802370774374882809539873379072084771964294211897505463230438074694657982885584648970300576313558790637275719863093018977047642005840391086066200592293L, 65537L), (108935754421006150321794883939476898914792477990350543474713340036780570937367550695550764627744624821173061278456131579236451088375699741732644183165767304701301251641091625691884964050177155744448266456781182142985502802083491893119256879377218522689224587781353300781747402452919865022273964256026308898221L, 65537L), (24453381766611862577685630932783739434927355058212609332774260261402449239451595706310993992772911312312732861341514385691694088278858420595775919108158959629138908610900908228684812493991700581357260820527403092630508574322470020752816106490387088386828445618645606537035168195033884920204970737351112227687413424450472034245530274145430175750955561695340041518953504414469636293659353268954671091419012787181490246124368012199684255509232956314826907523518781218437910213024426465992931829119860142054322811668331017943598696808477827255901813592648092801196026131094522986486478527108659865302542230752963023166973L, 65537L), (18787747671944956382818574826750151448134966320343258365645922270541191358297329894991231726700811222905310244971131081678975111157589957531867260456023868299050825490381504647015913562782193139202049032744078683491287728115795141442944240985369396368339811151418868479417685343827539170564981960981248205372224589612804201646261809025952562151156954180642492414164186778402461378860126159492739533050774540165401558662300222691467800425738354104659008924027300944682996547227882625756980181522114275322038004765344424762778748644259906608665534439812655239364883929585906582507875682203866356532457024524732598177901L, 65537L)], (18787747671944956382818574826750151448134966320343258365645922270541191358297329894991231726700811222905310244971131081678975111157589957531867260456023868299050825490381504647015913562782193139202049032744078683491287728115795141442944240985369396368339811151418868479417685343827539170564981960981248205372224589612804201646261809025952562151156954180642492414164186778402461378860126159492739533050774540165401558662300222691467800425738354104659008924027300944682996547227882625756980181522114275322038004765344424762778748644259906608665534439812655239364883929585906582507875682203866356532457024524732598177901L, 5840407454118049291044186107776993689867611713144532137316391876615281315021918945796364862109581260116421038814667340998912979532379880140939190034187928480958274985360062166007830798092094859773308893359401788589163447898181094902377329166652893971530386996473085547571242252617581755678782634100904369868055378321874337792222202310627823498500013328964224350772423965058108556830352725389483079887403404567968979601352673557456152459776433400739665687584698761594969878390562841328708639436609168704431255280807507582306887099398199549814620941913160099833738207442551591111173226277818045161309096574516573291021L), 0L, ([(23886717043623017856905477973250787179871536663090941133210085363705816721313635907300739148511337307535528348855556093231415361339189208774490910360656473080818431391131661802148736593752918669927913465249400970305332562849920944684763363605717386800704802652405511532213282620518506210701738791332605203954378018871366184513133060323565467367530314499023897162321578840937332724700159499951709154651616453566567668135584098478930096378727750433484195143022627106156802370774374882809539873379072084771964294211897505463230438074694657982885584648970300576313558790637275719863093018977047642005840391086066200592293L, 65537L), (108935754421006150321794883939476898914792477990350543474713340036780570937367550695550764627744624821173061278456131579236451088375699741732644183165767304701301251641091625691884964050177155744448266456781182142985502802083491893119256879377218522689224587781353300781747402452919865022273964256026308898221L, 65537L), (24453381766611862577685630932783739434927355058212609332774260261402449239451595706310993992772911312312732861341514385691694088278858420595775919108158959629138908610900908228684812493991700581357260820527403092630508574322470020752816106490387088386828445618645606537035168195033884920204970737351112227687413424450472034245530274145430175750955561695340041518953504414469636293659353268954671091419012787181490246124368012199684255509232956314826907523518781218437910213024426465992931829119860142054322811668331017943598696808477827255901813592648092801196026131094522986486478527108659865302542230752963023166973L, 65537L), (18787747671944956382818574826750151448134966320343258365645922270541191358297329894991231726700811222905310244971131081678975111157589957531867260456023868299050825490381504647015913562782193139202049032744078683491287728115795141442944240985369396368339811151418868479417685343827539170564981960981248205372224589612804201646261809025952562151156954180642492414164186778402461378860126159492739533050774540165401558662300222691467800425738354104659008924027300944682996547227882625756980181522114275322038004765344424762778748644259906608665534439812655239364883929585906582507875682203866356532457024524732598177901L, 65537L)], 56157944529137268655768625577864577628449673518753467206780991927626506971775069113166872726868492948961041822800259274906061195494771205837593075897139930526920179428319047262222071033942775916357670909596893050891270758893269511972926338537566037475984806844732102655018803238407291845867346769267119985559944739646695093963583900910301912739922368655670975894111706609625448341049618968600696642899641885908479838160049691650927926378444476392553822529437735642186361552621550490565886537610498041436277261319837954869834413878122964366631066351802779958055054755382549276859118640163060031962318127695116963435906L, [43666126423359818380299107289539747128738536969785888655112588544344070445080237638473344644805625962352840454531908130469781097458920877178092475991711673468858377732437664336055622262804235972112656394602331507369156291848317545084231641002779756646348796931777531819158550170274857047537475213786243751459741445629743222739618712812292584679013447004127763579836212668370543961658188375607768683534043138128456253062650498608435617833109503260351415718325281009715647231951765057758209559382684064032140476799626636484465051431967427217096612221890997281917700233541009906920187472906593815359552340168414573587826L, 63310018548215154951753262085366489704926469197979055962810741589023818469565079827603734365754923864284185777713176773105372710496227290019561141774874191852375175105533469998029504849893342447518985242802079995088122136720058582874985911595374017113199060255986962097113279423160330889637113823549540590411118857129560292248431027623452211420036972531159260932060307180622475910155565054570636963664614459748040557922099034293584859672315011593754554719500086380511884307485451179954970966850983488451374197527674431241875462358226171696005832608672745585287478791223960386561421125925087877951122898425910769254125L, 45831315220134719282322451308786544910389438862112028568141337578335515961471700697961221953657710740326075605594935396234298619991090117922186913706395695544726857895275390242206459198349245109081891127288030835957812351968607974737292371707262634582001266087246684661884533004714257874881396005561543687898684872185219297203816572165235002087342576115247679833076454906095402563715907156495861997710483997111035067395687389887655379132196797099138266509811474393468275347420215503875786869474241134726128554581325206553567614662910912799651913701506105738877348728691659669492527792470836815746115145039906723647630L, 9133294678956341761087127255223383500255110515027344074875817757930955880012858520221941241073091809738932534831336564572208490807496758673385948129084212522206030680165360471826372232092817941365147666679301727246287386601661031683465998739764747265277530103726580502872850899269838183773902614883288055700964496214160432312905955433900228027567136073473827555142543229167072482880329715542736853651199625157257133990574843888747881748495416875982154520469885742424150214834212851914797016962987970861796430245397856145800789093459271193277008442240048981846884057732039128798776456492679148683752061224036475624509L]), False), (7955101755030595255293479544444564440503491055078332630058241781245220158262734200341212656592325741418678483673767388595531306676246029080777602924644842L, 62669343413330620828838362904305575437842468587020190206335488795025467341184883950191288267515166924987228822893078996060230202454400943068018236630467916470286458411796081108175463854663225391441303944030575151917371342883983224863782712603966825491146864289619527749974504785840294373717341824128668179180724454526927099419273352691504254333257980897672410583246699515645162812591726473979932685546434501654947706103789002535630944183219005094458938780541261524312777909363767453758305967765493087245012989506938934481914711607335617392269195257269927710683294417162959061900102835993789152514472230174872740246271L, [], [None, 39237620462845490086199809382892145751790480938608349139559368223877077816162583289165791452582020739167747313693639064233760134991547124995959015869697815705108937510874263472850184835178521263354609401154730837176178457992222398294909285236532904987494050493098680945150071329027376001958856490409147778025767818046440491006800232415064289139925408491751172767264308544076823357388175672564933198211283177702847451309069265746853883784916872133809379499666273031462302899794792477499318003262358576322437260000678521934804706666230186247969237749553747908476393328737062059298886474964230447693352245414956662773078L, 38279400015408849535372713916564956236290746457816289964557836841403569416953936952320523500324052201939428143127931902887321657662348200234331392701592197943784918563789540574258399069900887498499608155911632599486834496490075293827479492009430335517312839758755644274817192641158368775359477214857682899637649047284562456440724819816308488948407782570420070838019499805160034294629083876351873879634897078240376460126522394686445628584778200838288618336886162294917944103559964629083652457856759220994787764864923479694494345367399176854514662524165439287174087940180848839845473244845569333896280668526325849120512L, 49166907764019369944648926494939212239821535261626684754009571031979368441891949406171439613041161702231827055622262122999208892241424726333081703101483865229155186836698717843868020511476018412962773130613636488492097697884786137755665920666378419028407741139828653565010748736607828259013671803169290371174234179405256367667371626775059515095659722302067914079681538821954423245842550263468207422153886772587479225452595430060704541196018650863106378641976012732113734026714928033790892376370620919412388595616262819382865010964467814791734240172177688119294182823361523882934229547378467527566634746952826231599932L, 46248493716848738490871646050515070846435511092557618123475028889810563706612013847912759316650810451139127951754433022611662060919532384503454548477172342858891944523127672450534668606609094471339369879839459661423565727300418506211683166275764244099002512300248634810185588272039110665140109586790329541448187936736207364304615347715453668529572438611238314086002123883658620862387202361628633501300320262674563480603985581841919494005040437561944386704869767830979268597067690555245590909498399115905450810374926168411818540988187675902686431692905780868099067354764765302503946982001764820289657745959461284455897L, 48235094432932158222657340788939489857873435867213505014543344089704399819042046853293592764486125629830634918956798852135993079647853653517681878348249704089487368230738656650051219058236964713330678421226719005565161256028291617313336479411764636275777413624600038869204872421486044641893532323601909232118219756198299216201949039116774952447583511284109606061102218520541585164100184728270473980133660134180280053692598432283607055872035258276907531621572808869125353516143289405856880744325773127649492534324703125269731466567491927629676472296763768903439277185183764563037452755928620415048136115739143477371937L, 63464142726897452032639462812915453241827417622890728800959918322953466509455789001282700687746549235674118570453134598918245295599875742382187428378966845207632934082037811929180385530507465625049771777550754381965166127674599964594699780325035179280478069904984853774361177080947232867422780086994831317731480642626116008318881099901925986706498464875082584969199163710790787096888764224198439746711554785709139275168159845761166898357828972972795893375106160590332660246695248094013082849236272293186152680806206000269591859447932969797698649619460574589003326285459805062861168021333640731572136958782732156897359L], [(23680421547046292089094485210096357326418189116828847836918518937552367080881198212153627966318815569255492713093264021038181264480744767423735193910937974229746829873720532579150599458945606842361504453024220288345278335497331693905972818167235320916288279172526855625547800416834322301865741978644791717137153116760124156841889419714281984270938966637827364571991879750243844033141215280836423244109688465151590773756490794127268366329698547918081279317525676540797554747382169049313923864214377064853575699996999384161562060488849078181925029540227915962780488321178299395366141300095829670334513050024737230768253L, 65537L), (116174906182524875777102473875153831917269577194591860467386345611038588417827657823317001899815442336076400584975149879126837567364496548814390327908975528387863388159238508124068478096270085847772989357570343518978203414491272637726542306246487055805596089790065025199351894703867722245473067249123266689471L, 65537L), (116334805386390616861930003961583677496059387054341863771968934875666484155755530017234738240030957873121007552375471713588825834949053676589087677062105649771192692935471313255769744705087257285697454171923327145909617538941379001743088218882265179003306224627361061352710700568421570069850942385467817105513L, 65537L), (109050619476178600575086775217587510262497078484279326605290166908837932674782755515632255160003423948423074088854899107869881938949319461761235292107533172270846713946751079442314491934760963268241070006183368358178122680163742822045035058004042420151034683564645033410111001149191993656590683268865399033001L, 65537L), (117638854319357951481885124681513704218870049093673521639716214268688439848553116977028080246552140193716371600563100767422946686870170874431759199742185176336727988087693897810118852517782505123429595176531280515928917745492572009519187894450409996692488818626917216183110158138216120894218183454830068828239L, 65537L), (20965636186639852810125646307885230299747243352872845048069074018688550408689341200378483516339827934873422479846892260753886358019282156587385307591852969047207822351738101765347111317631771709891801964261073107944120691547976326785062866589817012319122106562071771083659707641200428226278536848244350264315013299281628515902455462071506686499348703835345423301341189848065740844046720034208621758938217957765387074506083770537685970388596382885290906165344501978709714874594422351469275069658163333555458597551294208209099294585440328290160358796015289962169803752084223596692886242042070311234509431285505421968269L, 65537L), (167995512921600776717595248415329842480519763109018057326931679806959936211134527989709440374406643276695346399148372566341043543318775365701483887278380645705644918754990449651622484680261990546616968001054101660878754288328780213344403404031017433511354551985009231744793696941298273990393490789085014302199L, 65537L)], (23680421547046292089094485210096357326418189116828847836918518937552367080881198212153627966318815569255492713093264021038181264480744767423735193910937974229746829873720532579150599458945606842361504453024220288345278335497331693905972818167235320916288279172526855625547800416834322301865741978644791717137153116760124156841889419714281984270938966637827364571991879750243844033141215280836423244109688465151590773756490794127268366329698547918081279317525676540797554747382169049313923864214377064853575699996999384161562060488849078181925029540227915962780488321178299395366141300095829670334513050024737230768253L, 18623621578312403479806948085795603236618189777676617410172182173113265851088373258629816632436705861888194537715382366790514346611327140432948706296558662553208280900122124756924793587026785905198539184243623634006627339795893467313146024291249872753823496423552789914887540306765256879057083373717287252768164957755367862201507430592634567962608867663603822226859025391438356326918354340095490193076534459393669947286208535058363474694988183836756070440211215097714712543349695600259188382783206173881836246264651405540123611146140398130899671789857083324644003097503511417307118413057040012330770771963435247148673L), 0L, ([(23680421547046292089094485210096357326418189116828847836918518937552367080881198212153627966318815569255492713093264021038181264480744767423735193910937974229746829873720532579150599458945606842361504453024220288345278335497331693905972818167235320916288279172526855625547800416834322301865741978644791717137153116760124156841889419714281984270938966637827364571991879750243844033141215280836423244109688465151590773756490794127268366329698547918081279317525676540797554747382169049313923864214377064853575699996999384161562060488849078181925029540227915962780488321178299395366141300095829670334513050024737230768253L, 65537L), (116174906182524875777102473875153831917269577194591860467386345611038588417827657823317001899815442336076400584975149879126837567364496548814390327908975528387863388159238508124068478096270085847772989357570343518978203414491272637726542306246487055805596089790065025199351894703867722245473067249123266689471L, 65537L), (116334805386390616861930003961583677496059387054341863771968934875666484155755530017234738240030957873121007552375471713588825834949053676589087677062105649771192692935471313255769744705087257285697454171923327145909617538941379001743088218882265179003306224627361061352710700568421570069850942385467817105513L, 65537L), (109050619476178600575086775217587510262497078484279326605290166908837932674782755515632255160003423948423074088854899107869881938949319461761235292107533172270846713946751079442314491934760963268241070006183368358178122680163742822045035058004042420151034683564645033410111001149191993656590683268865399033001L, 65537L), (117638854319357951481885124681513704218870049093673521639716214268688439848553116977028080246552140193716371600563100767422946686870170874431759199742185176336727988087693897810118852517782505123429595176531280515928917745492572009519187894450409996692488818626917216183110158138216120894218183454830068828239L, 65537L), (20965636186639852810125646307885230299747243352872845048069074018688550408689341200378483516339827934873422479846892260753886358019282156587385307591852969047207822351738101765347111317631771709891801964261073107944120691547976326785062866589817012319122106562071771083659707641200428226278536848244350264315013299281628515902455462071506686499348703835345423301341189848065740844046720034208621758938217957765387074506083770537685970388596382885290906165344501978709714874594422351469275069658163333555458597551294208209099294585440328290160358796015289962169803752084223596692886242042070311234509431285505421968269L, 65537L), (167995512921600776717595248415329842480519763109018057326931679806959936211134527989709440374406643276695346399148372566341043543318775365701483887278380645705644918754990449651622484680261990546616968001054101660878754288328780213344403404031017433511354551985009231744793696941298273990393490789085014302199L, 65537L)], 62669343413330620828838362904305575437842468587020190206335488795025467341184883950191288267515166924987228822893078996060230202454400943068018236630467916470286458411796081108175463854663225391441303944030575151917371342883983224863782712603966825491146864289619527749974504785840294373717341824128668179180724454526927099419273352691504254333257980897672410583246699515645162812591726473979932685546434501654947706103789002535630944183219005094458938780541261524312777909363767453758305967765493087245012989506938934481914711607335617392269195257269927710683294417162959061900102835993789152514472230174872740246271L, [3147422728192416636161551805249817592839841225502194117185225000662324719850402947052643768391198127318699078618666320054017095752372013945743560516602254440108009348699206243874369165190048049295248108589515768341581804023331901898451340215707551634380851001049583242349868437288396931686184692159564855316530159362631338887970674141949180198114453058057394227777432416849921792049771631303625349645697892940764464091042743149093807491586007185804018099352097970416939531593796767722850440734855362476501908762717541983418002300182838374755109240702149963276423607702344362666558719812083072503740369708076270888958L, 39237620462845490086199809382892145751790480938608349139559368223877077816162583289165791452582020739167747313693639064233760134991547124995959015869697815705108937510874263472850184835178521263354609401154730837176178457992222398294909285236532904987494050493098680945150071329027376001958856490409147778025767818046440491006800232415064289139925408491751172767264308544076823357388175672564933198211283177702847451309069265746853883784916872133809379499666273031462302899794792477499318003262358576322437260000678521934804706666230186247969237749553747908476393328737062059298886474964230447693352245414956662773078L, 38279400015408849535372713916564956236290746457816289964557836841403569416953936952320523500324052201939428143127931902887321657662348200234331392701592197943784918563789540574258399069900887498499608155911632599486834496490075293827479492009430335517312839758755644274817192641158368775359477214857682899637649047284562456440724819816308488948407782570420070838019499805160034294629083876351873879634897078240376460126522394686445628584778200838288618336886162294917944103559964629083652457856759220994787764864923479694494345367399176854514662524165439287174087940180848839845473244845569333896280668526325849120512L, 49166907764019369944648926494939212239821535261626684754009571031979368441891949406171439613041161702231827055622262122999208892241424726333081703101483865229155186836698717843868020511476018412962773130613636488492097697884786137755665920666378419028407741139828653565010748736607828259013671803169290371174234179405256367667371626775059515095659722302067914079681538821954423245842550263468207422153886772587479225452595430060704541196018650863106378641976012732113734026714928033790892376370620919412388595616262819382865010964467814791734240172177688119294182823361523882934229547378467527566634746952826231599932L, 46248493716848738490871646050515070846435511092557618123475028889810563706612013847912759316650810451139127951754433022611662060919532384503454548477172342858891944523127672450534668606609094471339369879839459661423565727300418506211683166275764244099002512300248634810185588272039110665140109586790329541448187936736207364304615347715453668529572438611238314086002123883658620862387202361628633501300320262674563480603985581841919494005040437561944386704869767830979268597067690555245590909498399115905450810374926168411818540988187675902686431692905780868099067354764765302503946982001764820289657745959461284455897L, 48235094432932158222657340788939489857873435867213505014543344089704399819042046853293592764486125629830634918956798852135993079647853653517681878348249704089487368230738656650051219058236964713330678421226719005565161256028291617313336479411764636275777413624600038869204872421486044641893532323601909232118219756198299216201949039116774952447583511284109606061102218520541585164100184728270473980133660134180280053692598432283607055872035258276907531621572808869125353516143289405856880744325773127649492534324703125269731466567491927629676472296763768903439277185183764563037452755928620415048136115739143477371937L, 63464142726897452032639462812915453241827417622890728800959918322953466509455789001282700687746549235674118570453134598918245295599875742382187428378966845207632934082037811929180385530507465625049771777550754381965166127674599964594699780325035179280478069904984853774361177080947232867422780086994831317731480642626116008318881099901925986706498464875082584969199163710790787096888764224198439746711554785709139275168159845761166898357828972972795893375106160590332660246695248094013082849236272293186152680806206000269591859447932969797698649619460574589003326285459805062861168021333640731572136958782732156897359L]), False)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib, Crypto.PublicKey.RSA\n",
    "\n",
    "def UAB_h(m):\n",
    "    return int(hashlib.sha1('%s' % m).hexdigest(), 16)\n",
    "\n",
    "def UAB_xor(a, b):\n",
    "    return eval(\"%s^%s\" % (a, b))\n",
    "\n",
    "#Returns a tuple with the (n, e) values of a new public key\n",
    "def UAB_generate_RSA_public_key(nBits):\n",
    "    keys = Crypto.PublicKey.RSA.generate(nBits, os.urandom)\n",
    "    pk = keys.publickey()\n",
    "    return (pk.n, pk.e)\n",
    "\n",
    "#Returns a tuple ((n, e), (n, d)) containing a public key tuple in the 1st position and a private key tuple in the 2nd position.\n",
    "def UAB_generate_RSA_key_pair(nBits):\n",
    "    keys = Crypto.PublicKey.RSA.generate(nBits, os.urandom)\n",
    "    pk = keys.publickey()\n",
    "    pk_vars = (pk.n, pk.e)\n",
    "    sk_vars =  (keys.n, keys.d)\n",
    "    return(pk_vars, sk_vars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 1a: Implement auxiliar functions.\n",
    "# Implement the following auxiliary functions that we will use to generate and verify ring signatures.\n",
    "\n",
    "\n",
    "def UAB_E(k,x):\n",
    "    res = None\n",
    "    \n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    res= UAB_xor(k,x) # ^^ => xor\n",
    "    ##################################\n",
    "    \n",
    "    return res\n",
    "\n",
    "def UAB_f(PK,x):\n",
    "    res = None\n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "\n",
    "    res=power_mod(x,PK[1],PK[0])\n",
    "    ##################################\n",
    "    \n",
    "    return res\n",
    "\n",
    "def UAB_f_inv(SK,y):\n",
    "    res = None\n",
    "    \n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    res=power_mod(y,SK[1],SK[0])\n",
    "    \n",
    "    ##################################\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 1b: Setting the scenario.\n",
    "# Generate all the variables required to sign the message with a ring signature. Use representative names for the variables. For example, the message variable could be named MESSAGE.\n",
    "\n",
    "\n",
    "\n",
    "#### IMPLEMENTATION GOES HERE ####\n",
    "\n",
    "#Message to sign\n",
    "MESSAGE = \"Uranium from conflict areas\"\n",
    "\n",
    "\n",
    "#Public key (pkSigner) and private key (skSigner) of the signer.\n",
    "pkSigner,skSigner=UAB_generate_RSA_key_pair(1024)\n",
    "#List with the public keys of the group. This list has to include the public key of the signer.\n",
    "PK0=UAB_generate_RSA_public_key(1024)\n",
    "PK1=UAB_generate_RSA_public_key(1024)\n",
    "PK2=UAB_generate_RSA_public_key(1024)\n",
    "\n",
    "publicKeysGroup = [PK0,PK1,PK2,pkSigner]\n",
    "\n",
    "ni=[]\n",
    "for element in publicKeysGroup:\n",
    "        ni.append(element[0])\n",
    "        #print (\"element[0]\",element[0])\n",
    "        #print(\"\\n\")\n",
    "        \n",
    "\n",
    "max_ni=max(ni)\n",
    "\n",
    "keep=True\n",
    "b=0\n",
    "while(keep):\n",
    "    if(pow(2,b)>max_ni):\n",
    "        keep=False\n",
    "    else:\n",
    "        b=b+1\n",
    "\n",
    "h=pow(2,b)-1\n",
    "l=pow(2,b-1)\n",
    "#print(l)\n",
    "v =randint(l,h)\n",
    "xs0=randint(l,h)\n",
    "xs1=randint(l,h)\n",
    "xs2=randint(l,h)\n",
    "\n",
    "\n",
    "\n",
    "ys0=UAB_f(PK0,xs0)\n",
    "ys1=UAB_f(PK1,xs1)\n",
    "ys2=UAB_f(PK2,xs2)\n",
    "#xs and ys of the other members of the group. IMPORTANT: Assign None in the position of the signer.\n",
    "xs = [xs0,xs1,xs2,None]\n",
    "ys = [ys0,ys1,ys2,None]\n",
    "\n",
    "\n",
    "##################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 2a: Implement a function to obtain the y value for the signer by solving equation C_k_v(y1, y2, ..., yr) == v.\n",
    "#\n",
    "# Function UAB_solve_C.\n",
    "# * Parameter k: key used in the symmetric crypto system\n",
    "# * Parameter v: initialization vector\n",
    "# * Parameter ys: random inputs. Being signer user i, y[i] = None. E.g. if in a 6 user array, signer is in position 3, then ys = [y0,y1,y2,None,y4,y5]\n",
    "# * Returns: y value of the signer\n",
    "\n",
    "def UAB_solve_C(k,v,ys):\n",
    "    res = None\n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    a=v\n",
    "    pos=0\n",
    "    #apliquem la funció de combinació en sentit horari fins que trobem la y que volem calcular\n",
    "    for x,yi in enumerate(ys):\n",
    "        if(yi != None):\n",
    "            \n",
    "            a=UAB_xor(a,yi)\n",
    "            a=UAB_E(a,k)\n",
    "        else:\n",
    "            pos=x\n",
    "            break\n",
    "    b=v\n",
    "     #apliquem la funció de combinació en sentit antihorari fins que trobem la y que volem calcular\n",
    "    for yi in reversed(ys):\n",
    "        if(yi != None):\n",
    "            b=UAB_xor(b,k)\n",
    "            b=UAB_E(b,yi)\n",
    "        else:\n",
    "            break\n",
    "    b=UAB_E(b,k)# ens queda aplicar una k en l'esquema\n",
    "    res=UAB_xor(a,b)# amb els valors que hem trobat fem una xor per trobar y \n",
    "    ##################################\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 2b: Implement the UAB_sign_ring_simple function.\n",
    "#\n",
    "# Function UAB_sign_ring_simple.\n",
    "# * Parameter m: message to sign.\n",
    "# * Parameter v: initialization vector.\n",
    "# * Parameter xs: Random values for each user. Being signer user i, x[i] = None. E.g. if in a 6 user array, signer is in position 3, then xs = [x0,x1,x2,None,x4,x5]\n",
    "# * Parameter publicKeysGroup: array with the public keys of the members of the group.\n",
    "# * Parameter skSigner: private key of the signer.\n",
    "# * Returns: ring signature sigma. Sigma is a tuple with three elements:\n",
    "#    1. List of public keys of the group members.\n",
    "#    2. Initialization vector v.\n",
    "#    3. List of the x values of all the members.\n",
    "\n",
    "def UAB_sign_ring_simple(m, v, xs, publicKeysGroup, skSigner):\n",
    "    res = None\n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    k=UAB_h(m)\n",
    "    #print(k)\n",
    "    #print(\"\\n\")\n",
    "    ys= [None] * len(xs)\n",
    "    xaux=[]\n",
    "    #no es necessario si se ejecuta cell->Run All. Pero si se ejecuta solamente una celda el valor de xs se ha sobreescrito\n",
    "    # y da un resultado erroneo en los siguientes intentos.\n",
    "    for element in xs:\n",
    "        xaux.append(element)\n",
    "    pos=0\n",
    "    for i,x in enumerate(xs):\n",
    "        if x != None:\n",
    "            \n",
    "            ys[i]=UAB_f(publicKeysGroup[i],x)#calculem les diferents y a partir de les x, excepte pel que signa.\n",
    "        else:\n",
    "            pos=i\n",
    "            \n",
    "    y=UAB_solve_C(k,v,ys)# trobem el valor de y del signant a partir de la funció de combinació\n",
    "    x=UAB_f_inv(skSigner,y)# trobem la x\n",
    "    xaux[pos]=x #assignem la x a la posició on es trobra el None,ja tenim totes les xs\n",
    "    res= (publicKeysGroup,v,xaux)\n",
    "    ##################################\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 2c: Generate the ring signature using the variables that you previously defined and the functions implemented in the previous sections.\n",
    "\n",
    "#### IMPLEMENTATION GOES HERE ####\n",
    "sigma1=UAB_sign_ring_simple(MESSAGE, v, xs, publicKeysGroup, skSigner)\n",
    "\n",
    "##################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'\\nLes dues signatures son les mateixes. Podem pensar que la signatura  varia degut a que variem la K a partir de canviar\\nel missatge, per\\xc3\\xb2 la veritat es que al aplicar la K a UAB_solve_C en aquest cas apliquem Ek (fem una xor) un numero \\nparell de vegades i per tant al final \"no fem res\" i el valor de y en ambdos casos es el mateix.\\n\\n'"
      ]
     },
     "execution_count": 164,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# EXERCISE 2d: Generate another ring signature using the variables that you previously defined with another message. Compare the two signatures.\n",
    "\n",
    "#### IMPLEMENTATION GOES HERE ####\n",
    "MESSAGE2=\"CRIPTOGRAFIA\"\n",
    "sigma2=UAB_sign_ring_simple(MESSAGE2, v, xs, publicKeysGroup, skSigner)\n",
    "print(sigma1 == sigma2 )\n",
    "\n",
    "## Comment the comparison between the two signatures\n",
    "\"\"\"\n",
    "Les dues signatures son les mateixes. Podem pensar que la signatura  varia degut a que variem la K a partir de canviar\n",
    "el missatge, però la veritat es que al aplicar la K a UAB_solve_C en aquest cas apliquem Ek (fem una xor) un numero \n",
    "parell de vegades i per tant al final \"no fem res\" i el valor de y en ambdos casos es el mateix.\n",
    "\n",
    "\"\"\"\n",
    "##################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 3a: Implement the UAB_verify_ring_signature_simple function\n",
    "#\n",
    "# Function UAB_verify_ring_signature_simple.\n",
    "# * Parameter m: message that has been signed.\n",
    "# * Parameter sigma: ring signature. This is a tuple with three elements: \n",
    "#    1. List of public keys of the group members.\n",
    "#    2. Initialization vector v.\n",
    "#    3. List of the x values of all the members.\n",
    "# * Returns: a boolean value indicating if sigma is a valid ring signature for the message m.\n",
    "\n",
    "def UAB_verify_ring_signature_simple(m, sigma):\n",
    "    res = None\n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    k=UAB_h(m)\n",
    "    r=sigma[1] #inicialitem r amb v\n",
    "    for i,signatura in enumerate(sigma[0]):\n",
    "        x=sigma[2][i]\n",
    "        y=UAB_f(signatura,x)#calculem les y a partir de les x\n",
    "        r=UAB_xor(r,y)#fem la xor entre la y i el valor anterior     \n",
    "        r=UAB_E(r,k) #fem la xor entre el valor anterior i k\n",
    "    res= (r == sigma[1])#comprovem si es compleix que el resultat de la funció de combinació és igual a v\n",
    "    ##################################\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# EXERCISE 3b: Verify the signature generated before\n",
    "\n",
    "#### IMPLEMENTATION GOES HERE ####\n",
    "print(UAB_verify_ring_signature_simple(MESSAGE,sigma1))\n",
    "#a vegades dona False...\n",
    "#posibles raons\n",
    " #la y trobada al solve és incorrecta-> al trobar una x a partir d'aquesta y fent servir finv. Si tornem a calcular y\n",
    " # a partir d'aquesta x amb f el resultat és diferent.\n",
    " #es a dir y=UAB_solve_C(k,v,ys) \n",
    " #x=UAB_f_inv(skSigner,y) \n",
    " #y'=UAB_f(pkSigner,x) != y Això es degut a que la y generada al solve és > a la n del que firma.\n",
    " #Una altra posibilitat és que el solve sigui correcte i que les variables d'entrada no estiguin incialitzades correctament (xs i v)\n",
    " #També s'esmenta que les operacions han de ser de b bits, i al generar les yi algunes tenen major mida i mides diferents.Potser te a veure.\n",
    "##################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "# EXERCISE 4a: Test case that fails the simple implementation of the protocol.\n",
    "case = TEST_CASES_FAIL_SIMPLE[0]\n",
    "m = case[0]\n",
    "v = case[1]\n",
    "xs = case[3]\n",
    "pks = case[4]\n",
    "skSigner = case[5]\n",
    "sigma = UAB_sign_ring_simple(m,v,xs,pks,skSigner)\n",
    "res = UAB_verify_ring_signature_simple(m,sigma)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 4b: Implement UAB_g function\n",
    "#\n",
    "# Function UAB_g.\n",
    "# * Parameter key: public or private key\n",
    "# * Parameter m: message\n",
    "# * Parameter b: number of bits\n",
    "# * Returns: result of function g\n",
    "\n",
    "def UAB_g(key,m,b):\n",
    "    res = None\n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    keep=True\n",
    "    qi=0\n",
    "    ni=key[0]\n",
    "    gi=m\n",
    "    keep2=True\n",
    "    p=power(2,b)\n",
    "    q,r=divmod(m,ni)\n",
    "    if((q+1)*ni<=p):\n",
    "        gi=q*ni + UAB_f(key,r)\n",
    "    res=gi\n",
    "    ##################################\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE 4c: Implement the UAB_sign_ring function and UAB_verify_ring_signature.\n",
    "#\n",
    "# Function UAB_sign_ring.\n",
    "# * Parameter m: message to sign.\n",
    "# * Parameter v: initialization vector. \n",
    "# * Parameter xs: Random values for each user. Being signer user i, x[i] = None. E.g. if in a 6 user array, signer is in position 3, then xs = [x0,x1,x2,None,x4,x5]\n",
    "# * Parameter publicKeysGroup: array with the public keys of the members of the group.\n",
    "# * Parameter skSigner: private key of the signer.\n",
    "# * Returns: ring signature sigma. Sigma is a tuple with three elements:\n",
    "#    1. List of public keys of the group members.\n",
    "#    2. Initialization vector v.\n",
    "#    3. List of the x values of all the members.\n",
    "\n",
    "def UAB_sign_ring(m, v, xs, publicKeysGroup, skSigner):\n",
    "    res = None\n",
    "    \n",
    "    #### IMPLEMENTATION GOES HERE ### \n",
    "    k=UAB_h(m)\n",
    "    ys= [None] * len(xs)\n",
    "    ni=[]\n",
    "    for element in publicKeysGroup:\n",
    "        ni.append(element[0])\n",
    "        \n",
    "    max_ni=max(ni)\n",
    "    keep=True\n",
    "    b=0\n",
    "    #calculem el valor de b\n",
    "    while(keep):\n",
    "        \n",
    "        if(pow(2,b)>max_ni):\n",
    "            keep=False\n",
    "        else:\n",
    "            b=b+1\n",
    "    xaux=[]\n",
    "    #no es necessario si se ejecuta cell->Run All. Pero si se ejecuta solamente una celda el valor de xs se ha sobreescrito\n",
    "    # y da un resultado erroneo en los siguientes intentos.\n",
    "    for element in xs:\n",
    "        xaux.append(element)\n",
    "    \n",
    "    pos=0\n",
    "    for i,x in enumerate(xs):\n",
    "        if x != None:\n",
    "            ys[i]=UAB_g(publicKeysGroup[i],x,b)#calculem les y\n",
    "        else:\n",
    "            pos=i       \n",
    "    y=UAB_solve_C(k,v,ys)#calculem la y del signador\n",
    "    x=UAB_g(skSigner,y,b)#calculem la x del signador\n",
    "    xaux[pos]=x#asignem la x del signador a la posició None\n",
    "    res=(publicKeysGroup,v,xaux)#retornem la signatura\n",
    "    ##################################\n",
    "    \n",
    "    return res\n",
    "\n",
    "# Function UAB_verify_ring_signature.\n",
    "# * Parameter m: message that has been signed.\n",
    "# * Parameter sigma: ring signature. This is a tuple with three elements:\n",
    "#    1. List of public keys of the group members.\n",
    "#    2. Initialization vector v.\n",
    "#    3. List of the x values of all the members.\n",
    "# * Returns: a boolean value indicating if sigma is a valid ring signature for the message m.\n",
    "\n",
    "def UAB_verify_ring_signature(m, sigma):\n",
    "    res = None\n",
    "    \n",
    "    #### IMPLEMENTATION GOES HERE ####\n",
    "    ni=[]\n",
    "    for element in sigma[0]:\n",
    "        ni.append(element[0])\n",
    "        \n",
    "    max_ni=max(ni)\n",
    "    keep=True\n",
    "    b=0\n",
    "    \n",
    "    #trobem b\n",
    "    while(keep):\n",
    "        if(pow(2,b)>max_ni):\n",
    "            keep=False\n",
    "        else:\n",
    "            b=b+1\n",
    "    \n",
    "    k=UAB_h(m)\n",
    "    r=Integer(sigma[1]) #inicialitem r amb v\n",
    "    for i,signatura in enumerate(sigma[0]):\n",
    "        x=Integer(sigma[2][i])\n",
    "        y=Integer(UAB_g(signatura,x,b))#trobem la y\n",
    "        r=UAB_xor(r,y)#calculem la xor del pas anterior amb y\n",
    "        r=UAB_xor(r,k)#xor del pas anterior amb k\n",
    "    res = (r == sigma[1])#comprovem que el resultat de la funció de combinació sigui v\n",
    "    ##################################\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# EXERCISE 4d: Test case that fails the simple implementation of the protocol.\n",
    "case = TEST_CASES_FAIL_SIMPLE[0]\n",
    "m = case[0]\n",
    "v = case[1]\n",
    "xs = case[3]\n",
    "pks = case[4]\n",
    "skSigner = case[5]\n",
    "sigma = UAB_sign_ring(m,v,xs,pks,skSigner)\n",
    "res = UAB_verify_ring_signature(m, sigma)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 1a.1: True\n",
      "Test 1a.2: True\n",
      "Test 1a.3: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 1a:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_1a_E(name,cases):\n",
    "    res = True\n",
    "    for case in cases:\n",
    "        k = case[0]\n",
    "        m = case[1]\n",
    "        expectedResult = case[2]\n",
    "        res = res & (expectedResult==UAB_E(k,m))\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "def test_case_1a_f(name, numTries):\n",
    "    res = True\n",
    "    for i in range(numTries):\n",
    "        m = randint(0,2^512)\n",
    "        keys = Crypto.PublicKey.RSA.generate(1024, os.urandom)\n",
    "        res = res & (UAB_f((keys.n, keys.d),m)==keys.sign(long(m),None)[0])\n",
    "    \n",
    "    print \"Test\", name + \":\", res\n",
    "    \n",
    "def test_case_1a_f_inv(name, numTries):\n",
    "    res = True\n",
    "    for i in range(numTries):\n",
    "        m = randint(0,2^512)\n",
    "        keys = Crypto.PublicKey.RSA.generate(1024, os.urandom)\n",
    "        pk = keys.publickey()\n",
    "        res = res & (m%pk.n==UAB_f_inv((pk.n,pk.e),UAB_f((keys.n, keys.d),m)))\n",
    "    \n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "test_case_1a_E(\"1a.1\",TEST_CASE_1)\n",
    "test_case_1a_f(\"1a.2\", 10)\n",
    "test_case_1a_f_inv(\"1a.3\", 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 2a.1: True\n",
      "Test 2a.2: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 2a:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_2a(name, cases):\n",
    "    res = True\n",
    "    for case in cases:\n",
    "        m = case[0]\n",
    "        k = UAB_h(m)\n",
    "        v = case[1]\n",
    "        xs = case[3]\n",
    "        pks = case[4]\n",
    "        ys = []\n",
    "        for i,pk in enumerate(pks):\n",
    "            if xs[i] is None:\n",
    "                ys = ys + [None]\n",
    "            else:\n",
    "                ys = ys + [UAB_f(pk,xs[i])]\n",
    "\n",
    "        expectedC = case[6]\n",
    "        c = UAB_solve_C(k,v,ys)\n",
    "        res = res & (expectedC==c)\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "\n",
    "test_case_2a(\"2a.1\", TEST_CASES_2)\n",
    "test_case_2a(\"2a.2\", TEST_CASES_GOOD_SIMPLE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 2b.1: True\n",
      "Test 2b.2: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 2b:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_2b(name, cases):\n",
    "    res = True\n",
    "    for case in cases:\n",
    "        m = case[0]\n",
    "        v = case[1]\n",
    "        xs = case[3]\n",
    "        pks = case[4]\n",
    "        skSigner = case[5]\n",
    "        expectedSigma = case[7]\n",
    "        sigma = UAB_sign_ring_simple(m,v,xs,pks,skSigner)\n",
    "        res = res & (expectedSigma==sigma)\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "\n",
    "test_case_2b(\"2b.1\", TEST_CASES_2)\n",
    "test_case_2b(\"2b.2\", TEST_CASES_GOOD_SIMPLE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 3a.1: True\n",
      "Test 3a.2: True\n",
      "Test 3a.3: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 3a:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_3a(name, cases):\n",
    "    res = True\n",
    "    for case in cases:\n",
    "        m = case[0]\n",
    "        expectedSigma = case[7]\n",
    "        isCorrect = case[8]\n",
    "        res = res & (UAB_verify_ring_signature_simple(m, expectedSigma)==isCorrect)\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "test_case_3a(\"3a.1\", TEST_CASES_2)\n",
    "test_case_3a(\"3a.2\", TEST_CASES_GOOD_SIMPLE)\n",
    "test_case_3a(\"3a.3\", TEST_CASES_BAD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 4b.1: True\n",
      "Test 4b.2: True\n",
      "Test 4b.3: True\n",
      "Test 4b.4: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 4b:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_4b(name, cases):\n",
    "    res = True\n",
    "    for case in cases:\n",
    "        key = case[0]\n",
    "        m = case[1]\n",
    "        b = case[2]\n",
    "        expectedRes = case[3]\n",
    "        res = res & (UAB_g(key,m,b)==expectedRes)\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "test_case_4b(\"4b.1\", [((49,11),34,8,41)])\n",
    "test_case_4b(\"4b.2\", [((49,11),65,8,53)])\n",
    "test_case_4b(\"4b.3\", [((49,11),254,8,254)])\n",
    "test_case_4b(\"4b.4\", [((49,11),249,8,249)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test 4c.1: True\n",
      "Test 4c.2: True\n",
      "Test 4c.3: True\n"
     ]
    }
   ],
   "source": [
    "####################################################################################\n",
    "# TEST CASES EXERCICE 4c:\n",
    "####################################################################################\n",
    "\n",
    "def test_case_4c(name, cases):\n",
    "    res = True\n",
    "    index = 0\n",
    "    for case in cases:\n",
    "        m = case[0]\n",
    "        expectedSigma = case[7]\n",
    "        isCorrect = case[8]\n",
    "        res = res & (UAB_verify_ring_signature(m, expectedSigma)==isCorrect)\n",
    "        index +=1\n",
    "    print \"Test\", name + \":\", res\n",
    "\n",
    "test_case_4c(\"4c.1\", TEST_CASES_2)\n",
    "test_case_4c(\"4c.2\", TEST_CASES_FAIL_SIMPLE)\n",
    "test_case_4c(\"4c.3\", TEST_CASES_BAD)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.2",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}