(* ::Package:: *)

(* ::Section:: *)
(*data*)


(* ::Input:: *)
(*e=65537;*)


(* ::Input:: *)
(*x=11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451;*)


(* ::Input:: *)
(*y=11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439;*)


(* ::Input:: *)
(*valueLast=80096058210213458444437404275177554701604739094679033012396452382975889905967;*)


(* ::Input:: *)
(*valueQ=*)
(*5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819;*)


(* ::Input:: *)
(*c=110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478;*)


(* ::Section:: *)
(*1*)


(* ::Input:: *)
(*product=Fold[Mod[#1 #2,x]&,Range[y+1,x-1]];*)


(* ::Input:: *)
(*inverse=PowerMod[-product,-1,x];*)
(*Mod[inverse product,x]==x-1*)


(* ::Input:: *)
(*p=NextPrime@inverse;*)


(* ::Section:: *)
(*2*)


(* ::Input:: *)
(*value=Table[NextPrime[valueLast,i],{i,-9,0}];*)
(*n=Times@@value;*)


(* ::Input:: *)
(*prevQModValue=Table[Echo@PowerMod[Mod[valueQ,v],1/e,v],{v,value}];*)
(*prevQ=ChineseRemainder[prevQModValue,value];*)


(* ::Input:: *)
(*valueQ==PowerMod[prevQ,e,n]*)


(* ::Input:: *)
(*q=NextPrime@prevQ;*)
(*\[CurlyPhi]N=(p-1)(q-1);*)
(*d=PowerMod[e,-1,\[CurlyPhi]N];*)
(*Mod[e d,\[CurlyPhi]N]*)


(* ::Input:: *)
(*m=PowerMod[c,d,p q]*)


(* ::Input:: *)
(*PowerMod[m,e,p q]==c*)


(* ::Input:: *)
(*Log2@m//N*)
