prfold.py

# run this with json file from previous step
import sys
import json
def modInverse(a, m):
    m0=m
    y=0
    x=1
    if (m == 1):
        return 0
    while (a > 1):
        q=a // m
        t=m
        m=a % m
        a=t
        t=y
        y= x - q * y
        x= t
    if (x < 0):
        x= x + m0
    return x
fl=sys.argv[1]
with open(fl,"r") as f:
  data=json.loads(f.read())
priors=data["priors"]
trees={}


n=0xBCA83D793F493C49DF558612E74C773198AB4901F20369BFAF1598D71E362EF13AB9BE3B4D4D73C63378542D23BEBA56AD4D589C1E7F151E25CF6F7A38F8FF1FF491D5D2DFC971617B6D9559406E3A5127B2AEBDDEA965E0DFCF4C50AE241CAF9E87BFE33B0DB619B5C395E3986E310A3278F990B4139A421AF74B3E4E1548250DEC8F1755B038E61069E2547983ED93878549B4A9F5FAA1BEF72A75A9929FA7240FB1E46B9587170EF993C29C35F1F145E55BFEC0DE85D2B9409D6599B1C348BF76DD441ABD53033475E3267F91647C2584D974D3AD7B8C0C33711556D6C2CF23BF7905B17A68C622A0580A623C1AF9F446294D5F2DE50721D85EB5F49B7013
r=(1<<2048)
ri=modInverse(r,n)
rii=modInverse(ri,n)
endpoint=priors[-1]
stp=pow(endpoint,65537,n)
donotexpand=[0] #,25,61,80,98,216
droot=5

class rootNode(object): #for single root with additions
  def __init__(self):
    self.snodes=[[droot,1]]
class expNode(object):
  def __init__(self):
    self.numconst=1
    self.subnodes={}
  def getVal(self):
    vl=self.numconst
    for sn in self.subnodes:
      if sn>=0:
       k=pow(priors[sn],self.subnodes[sn],n)%n
       vl=vl*k%n
    return vl%n
  def asConst(self, cnst):
    self.numconst=cnst
    self.subnodes={}
    return self
  def asNode(self, nd):
    self.numconst=1
    self.subnodes={nd:1}
    return self
  def asCopy(self,other):
    self.numconst=other.numconst
    self.subnodes={}
    for nd in other.subnodes:
      self.subnodes[nd]=other.subnodes[nd]
    return self
  def canAdd(self,other):
    if len(self.subnodes)!=len(other.subnodes): return False
    for sn in self.subnodes:
      if not sn in other.subnodes: return False
      if self.subnodes[sn]!=other.subnodes[sn]: return False
    return True
  def add(self,other):
    ret=expNode()
    ret.numconst=(self.numconst+other.numconst)%n
    ret.subnodes=self.subnodes.copy()
    return ret
  def convertToConst(self,num,val):
    if not num in self.subnodes: return
    pwr=pow(val,self.subnodes[num],n)*pow(ri,self.subnodes[num]-1,n)%n
    self.numconst=(self.numconst*pwr)%n
    del self.subnodes[num]
  def __repr__(self):
    return "{}".format(self.subnodes)
  def mul(self,other):
    ret=expNode()
    ret.numconst=self.numconst*other.numconst*ri%n
    st=set(self.subnodes.keys())|set(other.subnodes.keys())
    for vl in st:
      a1=self.subnodes.get(vl,0)
      a2=other.subnodes.get(vl,0)
      if vl>=0:
       ret.subnodes[vl]=a1+a2
      else:
       if a1+a2<=1:
        ret.subnodes[vl]=a1+a2
       else:
        ret.numconst=0
    return ret
def reduceList(lst):
  ret=[]
  lc=list(lst)
  while len(lc)>0:
    cr=lc.pop()
    rl=[]
    for pt in lc:
     if cr.canAdd(pt):
      cr=cr.add(pt)
     else:
      rl.append(pt)
    lc=rl
    if cr.numconst>0:
      ret.append(cr)
  return ret
    
def mulList(ls1,ls2):
  retl=[]
  for a in ls1:
    for b in ls2:
      retl.append(a.mul(b))
  if len(ls1)>0 and len(ls2)>0:
    return reduceList(retl)
  else:
    return retl
  
class expVariable(object):
  def __init__(self,num,nodes,priors,rel):
   self.num=num
   self.nodes=[]
   if rel is None:
     self.nodes=[expNode().asConst(priors[num])]
     return
   if rel=="root":
     self.nodes=[expNode().asNode(num)]
     return
   if rel=="ism":
     self.nodes=[expNode().asNode(-1),expNode().asNode(-2)]
     return
   nd1=nodes[rel[1][0]]
   nd2=nodes[rel[1][1]]
   if rel[0]=="mul":
     self.nodes=mulList(nd1.nodes,nd2.nodes)
   elif rel[0]=="sum":
     ndlist=[expNode().asCopy(n) for n in nd1.nodes]+[expNode().asCopy(n) for n in nd2.nodes]
     self.nodes=reduceList(ndlist)
   elif rel[0]=="neg":
     cnst=expNode().asConst((n-1)*r%n)
     ndlist=[expNode().asCopy(n) for n in nd1.nodes]+[n.mul(cnst) for n in nd2.nodes]
     self.nodes=reduceList(ndlist)
  def spow(self):
    ndlist=[kn.mul(expNode().asConst(r*r%n)) for kn in self.nodes]
    ndlist2=mulList(ndlist,ndlist) # ^2
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist2=mulList(ndlist2,ndlist2)
    ndlist=mulList(ndlist,ndlist2)
    lst=[kn.mul(expNode().asConst(1)) for kn in ndlist]
    print(lst)
    print("{:x}".format(lst[0].numconst))
    print("{:x}".format(lst[1].numconst))
    ret=expVariable(-2,nodes,priors,None)
    ret.nodes=lst
    return ret
     
     
for p in priors:
 print("{}: {:x}".format(priors.index(p),p))
 print("> {:x}".format(p*ri%n))
 print("> {:x}".format(modInverse(p*ri%n,n)))
if "relations" in data:
 rels={}
 for et in data["relations"]:
   rels[int(et)]=data["relations"][et]
 lst=[priors.index(endpoint)]
 awl=set([])
 while len(lst)>0:
  kp=lst[0]
  lst=lst[1:]
  if kp in awl: continue
  awl.add(kp)
  kpp=priors[kp]
  if kpp in rels:
   for k in rels[kpp][1]:
     if not k in awl:
      lst.append(k)
      
nodes={}
disms=[]
for k in range(0,len(priors),1):
  ld=expVariable(k,nodes,priors,rels.get(priors[k],None))
  if len (ld.nodes)>100 and len(disms)==0:
       donotexpand.append(k)
       print("Adding as node {}".format(k))
  if k in disms:
   nd=expVariable(k,nodes,priors,"ism")
   nd.nodes.append(expNode().asConst(priors[k]))
   #nd=expVariable(k,nodes,priors,None)
  elif k in donotexpand:
    nd=expVariable(k,nodes,priors,"root")
  else:
    #print(rels.get(priors[k],None))
    nd=expVariable(k,nodes,priors,rels.get(priors[k],None))
  nodes[k]=nd
  print("{}: {}".format(k,rels.get(priors[k],None)))
  print("{}: {} -> {}".format(k,nd.nodes,len(nd.nodes)))
  #if k==len(priors)-1:
  for nod in nd.nodes:
     print("{:x}".format(nod.numconst))
  if len(nd.nodes)==1:
     print("{:x}".format(nd.nodes[0].getVal()))
  if False:#k==len(priors)-1:
     ec=pow(12,65537,n)
     a=priors[25]
     for s in range(29,4385,1):
         nd=nodes[s]
         if len(nd.nodes)!=2: continue
         print(s)
         if len(nd.nodes[0].subnodes)==0:
           res=nd.nodes[0].numconst
           der=nd.nodes[1].numconst
         else:
           res=nd.nodes[1].numconst
           der=nd.nodes[0].numconst    
         print("Res: {:x}".format(res))
         print("Der: {:x}".format(der))  
         print("Aaa: {:x}".format(a))       
         dk=der*a*modInverse(res,n)%n
         #dk=dk*ri%n
         print("Hmm: {:x}".format(dk))
         print(pow(ec,dk,n))
print("Ending")
sys.exit()
nd=nodes[len(priors)-1]
print("{:x}".format(nd.nodes[0].numconst))
print("{:x}".format(nd.nodes[1].numconst))
print("{:x}".format(nd.nodes[3].numconst))
dfx2=nd.nodes[3].numconst
rnd=nd.spow()
print("rn {:x}".format(rnd.nodes[0].numconst))
print("rn {:x}".format(rnd.nodes[1].numconst))
dx2=rnd.nodes[3].numconst
kn=3142033101700003260678755863863267700134374886049156296238778043258513471417667391237505300342672722921505586813412391537592394712287451780540489111338082979901966887630936873112829448279475520471433931949082770983040743133849146064289054900225131501940560027662491217132619227565578893295128589581903273904124801461070363532834633728769178636552784294153467969250254358604276515140477045217505629092433114246051368410587618590542410950189868285511930901887132942539241081579465767831350539339965000260768249119651905050152151634478714116343168832447694793716937575319879226685046081583200335708696821445923072794535
print("rx {:x}".format(kn*65537%n))
print("rrn {:x}".format(rnd.nodes[3].numconst))
x=rnd.nodes[0].numconst
fx=nd.nodes[0].numconst
dfa=nd.nodes[1].numconst*modInverse(rnd.nodes[1].numconst,n)%n
print("{:x}".format(dfa))
dfq=dfa*x*modInverse(fx,n)%n
print("{:x}".format(dfq))
print("{:x}".format(pow(x,dfq,n)))
   #nd.nodes[0].numconst
#res=nd.nodes[0].numconst*2
#der=nd.nodes[1].numconst*2
#dk=der*pow(res,65537,n)*modInverse(res,n)%n
#kn=3142033101700003260678755863863267700134374886049156296238778043258513471417667391237505300342672722921505586813412391537592394712287451780540489111338082979901966887630936873112829448279475520471433931949082770983040743133849146064289054900225131501940560027662491217132619227565578893295128589581903273904124801461070363532834633728769178636552784294153467969250254358604276515140477045217505629092433114246051368410587618590542410950189868285511930901887132942539241081579465767831350539339965000260768249119651905050152151634478714116343168832447694793716937575319879226685046081583200335708696821445923072794535
#print("kn: {:x}".format(kn))
#print("{:x}".format(dk))
#print("{:x}".format(priors[3]))
#print("{:x}".format(pow(res,65537,n)))
#print(res)
for k in range(len(priors)):
  print("{}: {}".format(k,rels.get(priors[k],None)))
sys.exit()