RSA.cs

using System.Numerics;
using System.Diagnostics;
using System.Text;

namespace InformationSecurity
{
    // https://habr.com/ru/articles/745820/
    // https://ru.wikipedia.org/wiki/RSA
    class RSA : ICryptoAlgorithm
    {
        private readonly List<BigInteger> PRIMES = new List<BigInteger>
        {
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599945537"),
            BigInteger.Parse("807845069898665655304485799661255361480811842944380230065154073278256412004595410413874926352951651680625853478439818902325583345700357720456655960360251867384368512626044506766296163800215617602081454424236045276782684415882060481180470010963340591457766515213713480756850500827894077478647064962797523752319750123888824365717846248590134442808352180354301560347665861538657318865008511314241177530728156468669870233450517232362685672560375863813361121015888736206205817166237026252449993051631569362954112190646672849501371635452138263089508886763262246406526507759598017421349219977267703899474798951725881062739204736358079390362938359464087300416298655940090749823136691024053225357667646861035709529142998400078461156309249694762032331842619223901273144974283030560562089620505106123759451888419403125479260129422024557174712994472066840364513853259343707174656293828581730427494862208891567800438046562472247743927688131800123354695580955036414744269794337484833967247477360173545086400800162687268041132541416104285126336357634092264424747145397093036669078222823248565315193883476967988121518185347814541942542527572703766291578454022930667291975358982767816200433298644028410213346214583158022233259714750266431228380160001311369924695701900286881848827864310041026577597296240038261380295618740370308327617697480734987791100101495205196385889528771574043781277757561630650483565336393562092306622597276026733339437699048177799105347238636953812745059441387962487137633561614962897402622255000562072425589975136667591270601009666577442262787216377346159031784347784362247432954143624166187144908914435006473516565641531795968354614829904322704806203200672664745823229092864595215372426914149056894964249087736212261481524276895241263717236230697617485874473974230347408391984652427840124179105417442172699659878299347201279267306780629004992578018352193859915490771189413454438946316444295140787867738415783817082637926124706116410021784299917084711601905242281352256410654853604931806418414056393764739058413769897726471927842210211132887320071104967493536743165929851215764176533369553597871656353222357242150602749220436612861781592753802569851854623021302661270326879757455143230725318573901095792614273958419305576879024722098407058028986093119813621036172093899303475916354271999013945793683617670208332003801414817093088302774255932298650386950985431861651530820421714835719313529279187600025034070814370767623192861093359782004582392275579764603771"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599948609"),
            BigInteger.Parse("750763146067961095998200586688766080917018270740793628553277805844232664333502845347941072525899530242250881766276109974421438716473825518018789256017533429054624169823649245177407883253681879701874815770460178508483313897414748494439473128890088019064382261173806472329717243367402234339472109338264502843059660887448477132506212825723938186492232004536256356500619855380484256088813891560154343078473026531242847510848826877947384360880682958402255922894592963501478052654752380223210346082016168850195988244231002253313728473575428396779942094794941897944775509889724075143822878087646871373277348928739155347993844738682457361327722674275684208869209314941372477305515630394539253523153624561079456291917437885844871994610348501725453797750916172450447666898702214146598224539558403728216147105591148753340902889208079669988547955621489190832515687317979799499741305884648803385779751460901333398039091599576067846902899643667619572730164403440649612537889159082305667350432633313289292120477611039303368386829594859640730115926899121365755610873454016692751809833047223787087390364406369466351744503109161184648019899908034633802271345999497914028043160263350503230268252448579517793505739582699170559186780834976127207393498574329477445492464506846948368965523569924732935073418165715882755967486441171113170718309923236567421512417613049630016819031461459354467919508987380800039217951919511922808354114171173346760715966004727678767338103107350753906632453315153673715633595948298011451541582822046702560340941866818790245034757973318587171950387815657820029979551073400673666774769477904700632075175184530748603489410062140289626340663573526129693654129329625583926082050423079077313366122755282279993893391823758694774729315822487576369795951226342788678445768316651720238806691557220823559948539772275434922519729051785565264325512195096258589471545540004580293104850391719062688840550528817275589364249100954524239939911915947920738521732440388793641509100109037498809017508632101202577969605624791174865384888598921730868905923782673584313133095978018387648653539304992970690384100166450406244440396437977517390751672998799201435257722632670337442138243228755346129765868677083786308451717264838653006138745776318149270524479086384651380147669577750057917228484456418493944530403602193349225444498335474277763451781115553048669895506151648529272059041470950715826664512833742491255292356769613869465434949192419225041812947021279113104765404028252932587"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599949491"),
            BigInteger.Parse("845231604720534349392511162302569707964627264703270528856676730167427644232254438600313270366402934919566260638129929776275160892952815818928999341439147782632915141784926334659908165514541382016119419528202595305294221077869302016734902007735170846526970934562574739988767716494721470646764024907371071623361731129082561609467342125805708673099922100764031057931207473423118971675554416714410974498521267874103458810972014212971812433468057072235514345790766635294746889515712404972833428682102676718740171349977888302544174373305877788075373600307688068407444391501718185762230767211126788037509869642411081448166653399468254514064906362410256275449955210833282145621716014656231306854119443772845636792933188726373894416285515100987943296736525188050081948741224325445263156572712227291737942356407521986325978571632360718894053890273344460249424947906402641764967668490377403586010049052447844179365792843484408845560795520397264005107306863962582127979889140422903401604576177626477762695369575764420436794467710056977014844234751359704717566614356610062717663034756465074831820138039001618274011843398263495724780411032421463254656911140420447336295989738613205489923262985987298050395220916388606489310120198482058790467833302421002152306545170220247957190216714566537846352183711978577250381079081824426517547214456606013180436820511613907757089295819184710863784928940625866919690912669461863626527682141830055414883817973716464109103804600285307323882559059618314180493776212641070767749090053876539256471470747767200640240114912713509646563243285356894102583008334896673255790775809385220150698877587442031357583960067919336947353289697857211388577653367451371150055883598308784961083073776424590870243571794860219018767736015169067309612884751425915567174058783178227011680607449304816076805384375256415719680361111148822843990349587190251616452141703345731714067028811347855395023016353109949259280574054512013487789108466284300768913364606015201889506229481784775596019302578885510108189079888084275355988778059124780928532342039281928114852526359151737404377070451189880566941606846958370009600550072210083942272378489316985690104182574661764795756612601884632429904516501306318659140115893088938395892272660248618711463698833654008304776585997042599101595631177693152008319386065051916160907708210073626833480743828150965070444275785126332685296937423832239077129010378027162726665245200449534420896319782071489197643472693141574123882699468720705849"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599954647"),
            BigInteger.Parse("818384623688925978523490320106239556199757748623916781887383576298668263344915712568485864907550825845518743078170484702968209305454366440596801339935461098909446718980629180732245529665791629730605607772841372923302088730021049179547880114063771562076518343420176503520548077145100590261823315878868023271282307173348596357037512098302921963959884333741171174161543774982391099256621666459955348741880948834418104993768256461452772586155395561507191859535231893831398482162082460385965122004685395775941500277958798748039438403456489340873047124250560028075390851503907986050428049809993970427257165873539307690611122368295490667945163093843269113173996721670736930096004579058870449836390856340288214228652265180072838351305528993134338787313608348659207421049414893387306928092926813080083352500395289164079536665574388779383984568793691130927016394896601533471701466636163015855927886191679619992857859300870142371068082335279973924553915090079553297584946446606009169401507204740584930256828253483575789831137368868647681530744929992874321730588272798458952744594363797199366400601203285231701665364848774680408261996640933684827847091048023600089832846385047772039774314333244113023635584791259072923967667997921474840500451736921149605205455717412051104729025021871433554599035983202305818992385551597222823939992464802035456637073357619457117738195625468862597720089327642409678147284427011139964458360005108682564421373312942111616571010053506943518848199444883139573531002021440190145626549900672759859602963378565042654167346002231093727706440018049782601410475761335756587237071853315348334117197215476559170428733148816536263967375158124154209600796705131079678700441654161622881983833045865429102487767184710948230357233110507956273111106367860027619436419552632884190859039426737303583684583829753255056142095088712131643508557493298303289862661634806404192038032844468997201363029523256382665751240833315574804439602011057923352609801779744198150860634662084516684638004825989831601873832307725184438569457513855268863677457212185916477847210290906631046969897041960666240934864127903657764057309441657403313332970698069886614040328372641939204932717479418381956203528046879824211863752355077671941168648875858772819097508340069945194574778129120054340103835157631556100305094379105858429388125861571143775365379510672579034608412461062508694824996287405997798549627071526594457508009374630955115246649174414481084546183512515132649650557439017716177"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599945537"),
            BigInteger.Parse("908134103125022936199679045336460088139538259408877239957594002073826384804385901385723360195690069262610882657591310213510122213088189427437166983382258853159670560955610507017358941419403449157237666326363078249811646240347884548318450062265211854228707861973936616426201054692681531565010942629413871407235611688806849031664051375270968951240217106352203661351401566294068505056351460631187663409650549896752107136915134735825345092032760225067273766006674014204518377382219970242018740740757801562187952309243746948782513876154595845453509768355416521573004575978202077650415100605044939862136673010315064815179549695230848911364929147525691473279696313543113221268330345564541450348273356381704214661717543286785541194716702780807288904772093543842285047957993404068778098965470011933409589429206626441899378761103390361096182378670685401898411094658926807306836847081835943357973914748243974553462419659778728424174876744884889337663318622530455646354808135111136017251878548422771995103040397369901316242657957794095881739476705825963577442432097207586951517400412729892129053486698884122525961372194109622094768535168323934781869631942181029734669471712341846452810877843896765796627344263064401292510055777036344602733303854326674934845528279033709181618342658446909538471112162204272561792453195913297839041964572902155716452512394019562924620963157379627471546758091794241270821365631791477621128051701060984143977549987087590518771961200777280619517712307741997414897291291295241686054201772435202891860902780507242769712388816662244825012926008327323146886800105429727344973750097602479852766857144401152661311177412151153208682893812770286702115108630763043657689857866623555374749892118011502129406563816298139435613940290406060665004051554708051952952270691402284823572601143668828635962210467454020142248784320351768992061699527951633085572694723532174965878619929824655904999534951933746345950211608504990157608466461580003511829661409467622226766453736585630422137816430444712548009561686598374374922892173795619753174417957404534022348440975588453772213866826078164587850726254203182343680946413558555375441246330493651239046085296690389996347339974995303461598471781709268019452497811929382017724158717123356449000339269322471854270163768421272079468521355610487261996959301453577172253302003279752226669247940730612687262036424687676380376296018363985629595515684740364199507393165915406305345934347524278322903205275830594027870988975261847209"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599970737"),
            BigInteger.Parse("775856867989898491561321685464747430581561510760896097380837102555721517605810995323700344824352819991702992784768442288913106778964035906696129890566430080965138047855570152165213486152940758870590260558245863774469864155583242576669820481940726206751321723901110621174389300962938272882212304723352329878491926852331565783895504295328833173568543589782079052802914050627384915986897153516647186095554357130665760726764465754561994456130545379242149116467575483362910036203300884281121550010250617282340182364062463057690873047134250530464125906629242292690838321006155610091823763504942755954503760250058541662056982567979936439869283810092898906244853709969309538815539479254163398270913308276281102781736456740787800662066248867703107375794692317126548936412836665675821596148048063094122328147441183602859418455820811706567381739682845816466033381405220155051497563478057757989654228516430972505539844313153888692834377540941044945404021157834064718222040464206174607440982593937812973811515492657978877342042178610095369738382579608563163476142275143513866987087266768211102183953560563813492396673146705688152942461201571663243670882620561751956127455931783422409911422252772206044843556919439773819512338481969018538541107579112871436329383423693030252398160539616549860687886018336428845681325986820485763546069026332586009011316575041206701112936359430036197921765696728866508264987840675395269119441589925049216544607334973323098173537217365252021573697062048437498114598757115416238507843799571984832663014440851714061005720386323302725044985927358000719284042650740629375764853080127780668331454432232007096177508089747076942710362305136791524926476563806290666657238903760160710318761122845428905727195682898855587948956282276307186807864267474229025213642480944693619487161854901307322338247193618994748355761827140102396838996111582089993191978432816696843074789658096375692373117457007724432475469549959757280325672972746246484662945945896690052240967149094655622729144451763730836388018448289253141254082182157694590253356708402385554153481124207163920633094492596713828076317661386341565883730882762447818257529865092524155851720395914405142628938336054978752678636797351719923894005219235258642399380966505944024022007733785380544819465541148907060528380536842553609099804168867039062874523378517712254753425446186819075431678132548110115832310748547001949201421713537003078245489196721002978946877509981909700782194966744543364654363171177250307"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599968157"),
            BigInteger.Parse("849164110275165985960715621423638789347804467709738060292988031130745139404405642348022927839471695212852567859449052729054231097358028480815830018979251830661274852042860737093969653414641632998154972249093003168618020326777768617403332124149826635171641321113137608016178292078458075984916670477269597626112176646342611944924163712964126165747723158628989477924659016644839723277845173483715512290354815605047081707590323188003339271001715650405414139128230974218920629392942645076668993408244296952808306338824173276352841757209724127504552488464641702207879600732050550533579023813921100082961102926827414110737496336491852362963176856037984370838529418776398053047049714113506613999029724650933923340945196120054197655015405249648598649514874717913610156658573228214824765508149447238391857246013974359817510949175536862308553194132753407886149922195129204050426739376624376587389988666101166100011026824677697271075806642527120692552321805855753357265230941410066899146917666255015399759458972702294019140027464151160728742297852923346013081823484708024474748273636636598503579925665813637813287302314096149250688677068608913372467444611277800857839927851883437710277705584849505380275509560116889443648723983677204844623075358518511228830610253194377945234409380222038920804439843552685155174788255239328759350711240720277052899592336499498337365804345198459703172703985322099932947965315433495842320229114573520739801395031166430107316385574147660105347921970916221901673926026237321092651693437790882757094503307649003892287423603819107088135671184461750248525425034327349588256697194849845590376190340341064645685021956158537608030629982728021160553473943768298357981981773105066363945436312773610866140181072672399830603010087777917792972691665737636088439279733963789389563176619610328800789797912522932476289470168090241243116519712161679867799761933389553551901151088426028970253859742584541656574494775729402734839731242219441394005496338143804167424702879372856739004911902616596274260762693250644854726784455066819376416633977552713653826694138521045105536048024151454701126636054949772892475114882531062180610831178995437245524897659559611703057260711523790643231641309460709607191454702062193581875414959253865423780897103543015144483379699941157045290128142757424571797534887651782713207157813329033722415532806792091944370134277248786986302009864607795868394416267086555401615269067459122766611064968505265678162599095105678611282901425087226971"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599965417"),
            BigInteger.Parse("944970524503546594223481379054336717496182564628247347073238774193650248539016514710499571789820275116617099478205752096171230062975985076100742833495971122023868445645885254211766453068778561951508094596523935935802817590156787177148713374822874459480458812390406062663882125535973373097948632005879007312133512871063185486740511968648889218212923113116127722900045921037280634493461763719669567841784199543102008423623882455768151687140557263226738333003700350794386226425515392827749529119920851886878163893286258051699810514305340396371388959886009245799794698843744539481763124125692428976755793622051169660396221212721295112537654017746169672595444509971151192250478460569244040194478755115421062119752436045980278192645703116956828288685346225903256277370302539945411328893894455255283031343481135504224653363380866258344118990972686158364758943611852930377432287915452041130850668313792849623828692964293456848257762468553808951142091220502907128311636226928569489048001251163278274257898308596036810693215542919676712652482185373828866714738505471561820457520677559904772445821409083084152277960905371702729231990014239446494647493445219947067624498453830206924528514488223172607308335235564501062512259422048441013186034815721295952319637618870278209200639494348720546724510149414887926634342960201177636102306397314488998244665667063684709475147827799208757799727166281777859210531722335560375585965937455523312308692654180405973909273578622398456432323535275483330337745704568190345014313985906583746394095672738623541295710590911257177216784066437722859081003397803538848503306433137607099533168434066588173759450594917097375849836918290483288618596238321984295624634745133332251018333226337420800465638058638573621739065843039018773941365151170553906514865508996883640864091253923705790296347215985396491032070285623979597041509689153394821683090119614472891656899835179429983477693274314523571507785491129073496982539821951822456742284720727944549239955722811065368472248030091335536755031136964244393511437806614264413003600153134890307859478636802508075981604824778295973629844005641492201664159042033416276080185141230021849954613651896274629819734650231191082920157021096103129305710248975379926261400365719795469756889752096087299646682522467867825892744630059036713996529455194377885717675258455967111710675708947852216071862689189594400045068142166087957132097782419313785192865964196626634689984971966863700995258599620466672145348763907688637"),
            //BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599963549"),
            BigInteger.Parse("734044596798804732836844182428479591990384105427379733061948901361079597722744192796112313084356245671408380434016387077665957199994488705678249165693304992154495598112706698508509915275493814274485196809181375246298963640539925315484556407648352954364409195974127087997099079923926580469514008360005092839591926290528548809967845739393476548589667805398911828380067794912868111517309808403196948295152519123603770189615179379289974203699215358639518216865036485872119957570756269664103823052589958530921304969072195331893303075160250272489622522948235050033157407456578627233144641292943252097178952755133623215624751268360672985804324143009684834604462464483909405223781077139289949286726660825790795205684421692265323389212047768542169969818965185850631789467443951085387531667990070172677977314557509592285840627854688125435462613737803953097754366792627248606426412773093620546819240630059925684337421350641654728462358403530650667926420206337862470785808170050685778391391880745369549671670320738680760882826586315208197906963503458871563632963519116088918528402967548316407397020002011046767262239507090619247448594736296584246164966610353879559856746964762153827000801018254141960303285581377227622159102195885583304486701230352636659218796097384335994923137539857964526070214045250149839662683690523555783807372160789603609365835557884745434767257140427831056851951068175080678240244771190799129066816576680412054243480605511050793733418306208108101827688593249538033463994000584377041486563856661195571280294675607739323828990426102758085413046227028051297356525919542543847648757862897241509991845724970107630847454869040104121272487607503712645640738394896189941052014378473470108678423244883756629994614379972553445221649126005779471600337245980708928011725052945257405582395241240813909539877742679366987397471992875107601651106936512284427026034826409050166819088057522300094668887293052221749595110558925785462582080997940195806554212050336344312634061610805498688921221123013819783794335097786677054906222635374928234088188538090764056008721251838884477864048388300179243803655851028340250191988717222214974412944110769532706640412127234436614297884025280259747143183928471894973906366282489691750789466105614320513042820443478800425713313947516475993390020858720652927807861926760561066417766331831754392537045214853881129057121892358784793227927699876072112715908464710852772771417699038487669947347209937796188899218524383431757193644886679349687"),
            BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599957089"),
            //BigInteger.Parse("687326639230486313544958173289081242734699342722601646328195180884756820666394404909523173935027672206126938030086476040422927126369137127503294308740410862380254260757496483865242565803205307996632300071103006904384027446245723274484303683586277751094379574185363892855100142726884958531826508373621147285008819584525741889548411639896471359773026488493703460995140429566989652731463494474657034717185372244370756815322099305889153413933926767351786226570193548471584798909629824762321838773399492964668608918506321395981365291395745368664678465287881126129981525276475347991483001134382682511106999809306170525558730705916454500604331958114275192787803904607480837656519849971943688813001218083451875974197029177953029491667025194535632212264917289097454302874221019219869972541187659444056339150743948485733116987172784478195555154386264205390708939234071650590973433321556183601535610257458287508187359882650895028953123554422989884735643801146735874171905603546985896770506598232453360845089916787992400600529292205092988754332085182381601124405789611998431311419819586125158383908015514212653997727103185347740107683990082172437290116785938507797309179894791830535443918576909898184571787292430871938908027045167312092128942352567503084675607666628643574195222011163236333813354241107403661387528594712874207764372001608190668838319891362900124853831495363951088634180511279585621898431832514683261891761896472671564726573721271890403305286442255801323000443551707845270933723576119312076917683698380662554848472015994664986461308739198819396478329571009097397053354049045557976248028586902984826624204567668163564130406756436953610007591510927130933317917631951700067324143164666640136121969996795444877294338125738999224990755140925155534992169996143323177968113417007638412324894979649406877940295006850590866101969534349876674391117787422185143828859301455674379490294086755185563486090535913413577851687944785912579260367364365606874427008529803165296008037867731793469371407420898079248989025244783184356526951194337852505490662242658544340053079859826133958543610397999534457401142010430987050837426912453905094901937133073491353634645723723547864505225040445405855312857623575780451467172267839955441009673801755333775861026020559927252259241943264090521755333886656511274111841889127434389455559207545563761567907603649248729600396420534674418421736663239512631554764227728536139542333279647545377383687894690206150646523017480001497779465956583562551")
        };
        private readonly List<(BigInteger, BigInteger)> PRIME_PAIRS = new List<(BigInteger, BigInteger)>
        {
            (
                BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599965417"),
                BigInteger.Parse("944970524503546594223481379054336717496182564628247347073238774193650248539016514710499571789820275116617099478205752096171230062975985076100742833495971122023868445645885254211766453068778561951508094596523935935802817590156787177148713374822874459480458812390406062663882125535973373097948632005879007312133512871063185486740511968648889218212923113116127722900045921037280634493461763719669567841784199543102008423623882455768151687140557263226738333003700350794386226425515392827749529119920851886878163893286258051699810514305340396371388959886009245799794698843744539481763124125692428976755793622051169660396221212721295112537654017746169672595444509971151192250478460569244040194478755115421062119752436045980278192645703116956828288685346225903256277370302539945411328893894455255283031343481135504224653363380866258344118990972686158364758943611852930377432287915452041130850668313792849623828692964293456848257762468553808951142091220502907128311636226928569489048001251163278274257898308596036810693215542919676712652482185373828866714738505471561820457520677559904772445821409083084152277960905371702729231990014239446494647493445219947067624498453830206924528514488223172607308335235564501062512259422048441013186034815721295952319637618870278209200639494348720546724510149414887926634342960201177636102306397314488998244665667063684709475147827799208757799727166281777859210531722335560375585965937455523312308692654180405973909273578622398456432323535275483330337745704568190345014313985906583746394095672738623541295710590911257177216784066437722859081003397803538848503306433137607099533168434066588173759450594917097375849836918290483288618596238321984295624634745133332251018333226337420800465638058638573621739065843039018773941365151170553906514865508996883640864091253923705790296347215985396491032070285623979597041509689153394821683090119614472891656899835179429983477693274314523571507785491129073496982539821951822456742284720727944549239955722811065368472248030091335536755031136964244393511437806614264413003600153134890307859478636802508075981604824778295973629844005641492201664159042033416276080185141230021849954613651896274629819734650231191082920157021096103129305710248975379926261400365719795469756889752096087299646682522467867825892744630059036713996529455194377885717675258455967111710675708947852216071862689189594400045068142166087957132097782419313785192865964196626634689984971966863700995258599620466672145348763907688637")
            ),
            (
                BigInteger.Parse("687326639230486313544958173289081242734699342722601646328195180884756820666394404909523173935027672206126938030086476040422927126369137127503294308740410862380254260757496483865242565803205307996632300071103006904384027446245723274484303683586277751094379574185363892855100142726884958531826508373621147285008819584525741889548411639896471359773026488493703460995140429566989652731463494474657034717185372244370756815322099305889153413933926767351786226570193548471584798909629824762321838773399492964668608918506321395981365291395745368664678465287881126129981525276475347991483001134382682511106999809306170525558730705916454500604331958114275192787803904607480837656519849971943688813001218083451875974197029177953029491667025194535632212264917289097454302874221019219869972541187659444056339150743948485733116987172784478195555154386264205390708939234071650590973433321556183601535610257458287508187359882650895028953123554422989884735643801146735874171905603546985896770506598232453360845089916787992400600529292205092988754332085182381601124405789611998431311419819586125158383908015514212653997727103185347740107683990082172437290116785938507797309179894791830535443918576909898184571787292430871938908027045167312092128942352567503084675607666628643574195222011163236333813354241107403661387528594712874207764372001608190668838319891362900124853831495363951088634180511279585621898431832514683261891761896472671564726573721271890403305286442255801323000443551707845270933723576119312076917683698380662554848472015994664986461308739198819396478329571009097397053354049045557976248028586902984826624204567668163564130406756436953610007591510927130933317917631951700067324143164666640136121969996795444877294338125738999224990755140925155534992169996143323177968113417007638412324894979649406877940295006850590866101969534349876674391117787422185143828859301455674379490294086755185563486090535913413577851687944785912579260367364365606874427008529803165296008037867731793469371407420898079248989025244783184356526951194337852505490662242658544340053079859826133958543610397999534457401142010430987050837426912453905094901937133073491353634645723723547864505225040445405855312857623575780451467172267839955441009673801755333775861026020559927252259241943264090521755333886656511274111841889127434389455559207545563761567907603649248729600396420534674418421736663239512631554764227728536139542333279647545377383687894690206150646523017480001497779465956583562551"),
                BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599945537")
            ),
            (
                BigInteger.Parse("700659603263148726043253647098324000725292315931957621419637799747993372461352633512643757592917663041832710355100422470528397188909262164976072279278984478784712817158805505596158807905724585389892419802064494610865086337104041912542345810463584923013825961445830887942262674997055922770181868050834801755502711568967948864570394304087812144589276166143562220131736466242652216233480779931722540058370876286196191871181353130327878609314947949931327675395801509871030344623397309268916670720216769731649929974739678966992509359870770118987105461804825586142065631439724359976798430831878074648377433907881732540266946119644657912516044098757262897952401278724411065490550872427911405514547958347984791015251619049084149028683036623726572282588668549564805107156230606931813396740993700928536501891914527794973567682293777541956022836141464327567331350220338229692663522062803252540537158233345408240209594751183717799599025038112202132735423912541536853009341155687394094143914006309836761550404246816382172789542963086900388177952084358087964233816324489044464017421974837751944807300709791132477804366033839545985556671709913564955446603735207407269185815450708349433176090738616295881361286939832454699152479276043197619223108873208876978523774723503018250393374689600852699536288858533281017025880257690863328796473021140682449349309106984236166579917362459578607810362040497321211999035152257172522365314951567701574347460126627684227430422542396962782590517729287825773885664395590765196272726990756771663285296007987979441560751351278623926210702022423996483451063436830170882399827680163107866923979466976939301044596577608012621141104394468631482657109817254881357795962231429243426309471862610357083657308795382696902496579218566512071541007015121597454958488097013387021406075404611676784746227541743576440486117044792291672288544314261769522247109624136614269293587425860416979317833297940353729257843230363277970277371151383121763121885681217160479210407646265113633486772894546176746847309158704383755965935000023612496748662753313153750594764588637148195513527972913230559377075030335812036995201141182589258434332791928340053930939299921839308515791624902911793675590884798865074315014618523587221872497810349142470372583346492008610082949614978609726687683472356367034561545424261411392087801689643667069476382729924033898738100030104575536102459653668251103615421214948583385636645313139831081950846125342732097475658967139865551095257064599954647"),
                BigInteger.Parse("818384623688925978523490320106239556199757748623916781887383576298668263344915712568485864907550825845518743078170484702968209305454366440596801339935461098909446718980629180732245529665791629730605607772841372923302088730021049179547880114063771562076518343420176503520548077145100590261823315878868023271282307173348596357037512098302921963959884333741171174161543774982391099256621666459955348741880948834418104993768256461452772586155395561507191859535231893831398482162082460385965122004685395775941500277958798748039438403456489340873047124250560028075390851503907986050428049809993970427257165873539307690611122368295490667945163093843269113173996721670736930096004579058870449836390856340288214228652265180072838351305528993134338787313608348659207421049414893387306928092926813080083352500395289164079536665574388779383984568793691130927016394896601533471701466636163015855927886191679619992857859300870142371068082335279973924553915090079553297584946446606009169401507204740584930256828253483575789831137368868647681530744929992874321730588272798458952744594363797199366400601203285231701665364848774680408261996640933684827847091048023600089832846385047772039774314333244113023635584791259072923967667997921474840500451736921149605205455717412051104729025021871433554599035983202305818992385551597222823939992464802035456637073357619457117738195625468862597720089327642409678147284427011139964458360005108682564421373312942111616571010053506943518848199444883139573531002021440190145626549900672759859602963378565042654167346002231093727706440018049782601410475761335756587237071853315348334117197215476559170428733148816536263967375158124154209600796705131079678700441654161622881983833045865429102487767184710948230357233110507956273111106367860027619436419552632884190859039426737303583684583829753255056142095088712131643508557493298303289862661634806404192038032844468997201363029523256382665751240833315574804439602011057923352609801779744198150860634662084516684638004825989831601873832307725184438569457513855268863677457212185916477847210290906631046969897041960666240934864127903657764057309441657403313332970698069886614040328372641939204932717479418381956203528046879824211863752355077671941168648875858772819097508340069945194574778129120054340103835157631556100305094379105858429388125861571143775365379510672579034608412461062508694824996287405997798549627071526594457508009374630955115246649174414481084546183512515132649650557439017716177")
            )
        };

        private const int BIT_LENGTH = 1024 * 8;
        private const int BYTE_LENGTH = BIT_LENGTH / 8;
        private const int TEST_SAMPLES = 10;

        private byte[] buff = new byte[BYTE_LENGTH];
        private Random rng  = new Random();
        
        private BigInteger firstPrime_P;
        private BigInteger secondPrime_Q;
        private BigInteger multiplicationOfPAndQ_N;
        private BigInteger eulerFunctionValue_fiN;
        private BigInteger openExponent_E = 65537;
        private BigInteger closeExponent_D;

        public RSA()                                 => CalculateKeys();
        public RSA(BigInteger openExp, BigInteger closedExp, BigInteger multiplication)
        {
            openExponent_E = openExp;
            closeExponent_D = closedExp;
            multiplicationOfPAndQ_N = multiplication;
        }
        private BigInteger Encrypt(BigInteger input) => BigInteger.ModPow(input, openExponent_E, multiplicationOfPAndQ_N);
        public  byte[]     Encrypt(byte[] input)     => Encrypt(new BigInteger(input)).ToByteArray();
        public  string     Encrypt(string input)     => new BigInteger(Encrypt(Encoding.Default.GetBytes(input))).ToString();

        private BigInteger Decrypt(BigInteger input) => BigInteger.ModPow(input, closeExponent_D, multiplicationOfPAndQ_N);
        public  byte[]     Decrypt(byte[] input)     => Decrypt(new BigInteger(input)).ToByteArray();
        public  string     Decrypt(string input)     => Encoding.Default.GetString(Decrypt(BigInteger.Parse(input)).ToByteArray());

        public Tuple<BigInteger, BigInteger> GetPublicKey() => new Tuple<BigInteger, BigInteger>(openExponent_E, multiplicationOfPAndQ_N);
        public Tuple<BigInteger, BigInteger> GetPrivateKey() => new Tuple<BigInteger, BigInteger>(closeExponent_D, multiplicationOfPAndQ_N);

        private void CalculateKeys()
        {
            // I feel bad when i see this shit, but it works. 
            for (; ;)
            {
                (firstPrime_P, secondPrime_Q) = GetPrimes();
                multiplicationOfPAndQ_N = firstPrime_P * secondPrime_Q;
                eulerFunctionValue_fiN = (firstPrime_P - 1) * (secondPrime_Q - 1);
                closeExponent_D = eulerFunctionValue_fiN - BigInteger.Abs(EuclidAlgorithm(openExponent_E, eulerFunctionValue_fiN));
                if ((closeExponent_D * openExponent_E) % eulerFunctionValue_fiN == 1)
                    break;
                //else
                    //DebugPrint();
            }
        }

        public void DebugPrint()
        {
            Console.WriteLine("e = " + openExponent_E);
            Console.WriteLine("d = " + closeExponent_D);
            Console.WriteLine("p = " + firstPrime_P);
            Console.WriteLine("q = " + secondPrime_Q);
            Console.WriteLine("(d * e) mod fiN = " + ((closeExponent_D * openExponent_E) % eulerFunctionValue_fiN));
        }

        private BigInteger GetBigInteger()
        {
            rng.NextBytes(buff);
            var res = new BigInteger(buff);
            int counter = 0;
            while (res.GetBitLength() < BIT_LENGTH)
            {
                res = (res << 1) + 1;
                counter++;
            }
            return res.Sign == -1 ? res * BigInteger.MinusOne : res;
        }

        private BigInteger GetBigInteger(int length)
        {
            byte[] arr = new byte[length];
            rng.NextBytes(arr);
            int counter = 0;
            var res = new BigInteger(arr);
            while (res.GetBitLength() != BIT_LENGTH)
            {
                res = res << 1;
                res += counter % 2 == 0 ? 0 : 1;
                counter++;
            }
            return res;
        }

        private BigInteger GetPrimeBigInteger()
        {
            BigInteger i = GetBigInteger();
            i = i.IsEven ? i + BigInteger.One : i ;
            Stopwatch sw = Stopwatch.StartNew();
            Stopwatch gsw = Stopwatch.StartNew();
            UInt64 iter = 0;

            while (!IsPrime(i))
            {
                if (iter % 500 == 0)
                {
                    sw.Stop();
                    Console.WriteLine("[" + (sw.ElapsedMilliseconds / 1000).ToString() + "s] IsPrime() --> " + IsPrime(i) + " --> changing number...");
                    sw.Reset();
                    sw.Start();
                }
                i += 2;
                iter++;
            }

            gsw.Stop();
            Console.WriteLine(gsw.ElapsedMilliseconds / 1000 + "s -- total search time");

            return i;
        }

        private BigInteger GetPrimeBigInteger(int len)
        {
            BigInteger i = GetBigInteger();
            Stopwatch sw = Stopwatch.StartNew();
            Stopwatch gsw = Stopwatch.StartNew();
            UInt64 iter = 0;

            while (!IsPrime(i) || !(BigInteger.Parse(i.ToString()).GetByteCount() == len))
            {
                if (iter % 1000 == 0)
                {
                    sw.Stop();
                    Console.WriteLine("[" + (sw.ElapsedMilliseconds / 1000).ToString() + "s] IsPrime() --> " + IsPrime(i) + " --> changing number...");
                    sw.Reset();
                    sw.Start();
                }
                i = GetBigInteger(len);
                iter++;
            }

            gsw.Stop();
            Console.WriteLine(gsw.ElapsedMilliseconds / 1000 + "s -- total search time");

            return i;
        }

        private bool IsPrime(BigInteger prime) => IsProbablePrime(prime, TEST_SAMPLES);

        /// <summary>
        /// Тест Миллера-Рабина на простоту числа. Производится k раундов проверки числа n на простоту.
        /// </summary>
        private bool IsProbablePrime(BigInteger n, int k)
        {
            // если n == 2 или n == 3 - эти числа простые, возвращаем true
            if (n == 2 || n == 3)
                return true;

            // если n < 2 или n четное - возвращаем false
            if (n < 2 || n.IsEven)
                return false;

            // представим n − 1 в виде (2^s)·t, где t нечётно, это можно сделать последовательным делением n - 1 на 2
            BigInteger t = n - 1;

            int s = 0;

            while (t.IsEven)
            {
                t /= 2;
                s += 1;
            }

            // повторить k раз
            for (int i = 0; i < k; i++)
            {
                // выберем случайное целое число a в отрезке [2, n − 2]
                

                byte[] _a = new byte[n.ToByteArray().LongLength];

                BigInteger a;

                do
                {
                    rng.NextBytes(_a);
                    a = new BigInteger(_a);
                }
                while (a < 2 || a >= n - 2);

                // x ← a^t mod n, вычислим с помощью возведения в степень по модулю
                BigInteger x = BigInteger.ModPow(a, t, n);

                // если x == 1 или x == n − 1, то перейти на следующую итерацию цикла
                if (x == 1 || x == n - 1)
                    continue;

                // повторить s − 1 раз
                for (int r = 1; r < s; r++)
                {
                    // x ← x^2 mod n
                    x = BigInteger.ModPow(x, 2, n);

                    // если x == 1, то вернуть "составное"
                    if (x == 1)
                        return false;

                    // если x == n − 1, то перейти на следующую итерацию внешнего цикла
                    if (x == n - 1)
                        break;
                }

                if (x != n - 1)
                    return false;
            }

            // вернуть "вероятно простое"
            return true;
        }

        private (BigInteger, BigInteger) GetPrimePair() => PRIME_PAIRS[Convert.ToInt32(rng.NextInt64() % PRIME_PAIRS.Count)];

        private Tuple<BigInteger, BigInteger> GetPrimes()
        {
            var i = rng.NextInt64();
            return new Tuple<BigInteger, BigInteger>
                       (PRIMES[Convert.ToInt32(i % PRIMES.Count)],
                        PRIMES[Convert.ToInt32((i + 1) % PRIMES.Count)]);
        }

        private BigInteger GCD(BigInteger a, BigInteger b) => BigInteger.GreatestCommonDivisor(a, b);

        /// <summary>
        /// Позаимствовано из <a href="https://ru.wikipedia.org/wiki/Расширенный_алгоритм_Евклида">
        /// https://ru.wikipedia.org/wiki/Расширенный_алгоритм_Евклида</a>.
        /// </summary>
        private BigInteger EuclidAlgorithm(BigInteger a, BigInteger b)
        {
            BigInteger old_r, old_s, old_t, r, s, t, quotient;
            (old_r, r) = (a, b);
            (old_s, s) = (1, 0);
            (old_t, t) = (0, 1);

            while (r != 0)
            {
                quotient = old_r / r;
                (old_r, r) = (r, old_r - quotient * r);
                (old_s, s) = (s, old_s - quotient * s);
                (old_t, t) = (t, old_t - quotient * t);
            }

            //Console.WriteLine("коэффициенты Безу:         (" + old_s + ", " + old_t + ")");
            //Console.WriteLine("наибольший общий делитель: " + old_r);
            //Console.WriteLine("частные от деления на НОД: (" + t + ", " + s + ")");

            return Min(old_s, old_t);
        }

        private BigInteger Min(BigInteger a, BigInteger b) => a < b ? a : b;

        private BigInteger FastPower(BigInteger value, BigInteger pow)
        {
            BigInteger result = BigInteger.One;
            while (pow > BigInteger.Zero)
            {
                if (!pow.IsEven)
                    result *= value;

                value *= value;
                pow /= 2;
            }
            return result;
        }
    }
}