listQ=[0,0,0,0]
rAlpha=[]
factP1=[]
objectA=0
listOfBeta=[]
s=0
def genQ(p=0):
B=float(2**(sqrt(log(float(p))*log(log(float(p))))))
B1=float(2**(2*sqrt(log(float(p))*log(log(float(p))))))
print("B=%s"%B)
print("B1=%s"%B1)
listQ=[]
q=1
while q<B1:
q=int(gap("NextPrimeInt("+str(q)+")"))
if q<B1:
listQ.append(q)
print("listQ=")
print(listQ)
return(listQ)
def factors(p=0):
factP1=list(gap("Factors("+str(p-1)+")"))
factTmp=[]
for i in range(len(factP1)):
if (factP1[i] not in factP1[:i]):
factTmp.append(factP1[i])
countTmp=[factP1.count(k) for k in factTmp]
factP1=list(map(lambda x,y:x**y,factTmp,countTmp))
print("fact(%s)="%(p-1))
print(factP1)
return(factP1)
class AlphaCond(tr.Condition):
def __init__(self,listQ=listQ,p=0):
tr.Condition.__init__(self)
self.listQ=listQ
self.leftAr=0
self.listAlpha=[]
def cond(self,first):
first=first.astype(int)
rightAr=reduce(lambda res,x:res*x,map(lambda x,y:x**y,self.listQ,first),1)
rightAr=int(gap(""+str(int(rightAr))+" mod "+str(p)))
if(rightAr==self.leftAr[1]):
if(list(first) not in self.listAlpha):
self.listAlpha.append(list(first))
return(True)
else:
return(False)
def findAlphas(listQ=listQ,tresholdAlpha=6,a=0,p=0):
aa=ones((len(listQ)))
listOfR=list(range(len(listQ)+1))
listOfR=listOfR[1:]
listAr=[int(gap(str(a**r)+" mod "+str(p))) for r in listOfR]
listAr=map(lambda x,y:(x,y),listOfR,listAr)
print("listAr=")
print(listAr)
print("a,p=%s,%s"%(a,p))
rAlpha={}
oAlphaCond=AlphaCond(listQ=listQ,p=p)
searchAlpha=tr.Search(init=aa,object=oAlphaCond,treshold=tresholdAlpha,findAll=True)
for leftAr in listAr:
searchAlpha.object.leftAr=leftAr
searchAlpha.object.listAlpha=[]
searchAlpha.listOfA=[aa]
oo=searchAlpha.search()
if oo:
rAlpha[leftAr]=oo.listAlpha[:]
else:
print("fail!")
break
print("rAlpha.keys=")
print(list(rAlpha.keys()))
print("len(rAlpha)=")
print([len(rAlpha[k]) for k in rAlpha.keys()] )
return(rAlpha)
class MatrixCond(tr.Condition):
def __init__(self,vectors,factors):
tr.Condition.__init__(self)
self.vectors=vectors
self.matrix=[]
self.listOfR=[]
self.factors=factors
def cond(self,first):
keys=list(self.vectors.keys())
first=first.astype(int)
m=matrix([self.vectors[keys[i]][first[i]] for i in range(len(keys))])
self.listOfR=[keys[i][0] for i in range(len(keys))]
try:
tmpMatrix=[]
for pe in self.factors:
strM="TransposedMat("+str((m.astype(int)).tolist())+")"
mat=matrix(gap(strM))
strM=str((mat.astype(int)).tolist())+'^-1 mod '+str(pe)
m1=matrix(gap(strM))
tmpMatrix.append(mat)
print("tmpMatrixTransposed=")
print(tmpMatrix)
self.matrix=tmpMatrix[:]
return(True)
except:
return(False)
def findUnsingularMatrix(rAlpha=rAlpha,listQ=listQ,factors=factP1,tresholdMatrix=6):
aa=ones((len(listQ)))
print("help")
o=MatrixCond(rAlpha,factors)
search=tr.Search(init=aa,object=o,treshold=tresholdMatrix)
s=search.search()
if s:
return(s)
def findBeta(listQ=listQ,treshold=6,a=0,b=0,p=0):
aa=ones((len(listQ)))
oBetaCond=AlphaCond(listQ=listQ,p=p)
print("a,b,p=%s,%s %s"%(a,b,p))
oBetaCond.leftAr=(0,int(gap(str((a**3)*b)+" mod "+str(p))))
searchBeta=tr.Search(init=aa,object=oBetaCond,treshold=treshold)
s=searchBeta.search()
if s:
listOfBeta=s.listAlpha[0][:]
return((listOfBeta,3))
def solveEqs(objectA=objectA,listOfBeta=listOfBeta,s=s):
listOfR=objectA.listOfR[:]
print("listOfR=")
print(listOfR)
print("listOfBeta=")
print(listOfBeta)
m=[]
for i in range(len(objectA.matrix)):
strM=str((objectA.matrix[i].astype(int)).tolist())+'^-1 mod '+str(objectA.factors[i])
print(strM)
listOfAlpha=list(gap(strM+'*'+str(listOfBeta)+' mod '+str(objectA.factors[i])))
print("listOfAlpha=")
print(listOfAlpha)
tmpM=sum(map(lambda x,y:x*y,listOfAlpha,listOfR))
tmpM=int(gap(str(tmpM)+' mod '+str(objectA.factors[i])))
print("tmpM,s=")
print((tmpM,s))
m.append(tmpM-s)
return(m)
p=11
print("p=%s"%p)
a=6
b=7
def logByAdleman(a=0,r=0,b=0,p=0,treshold=11):
listQ=genQ(p=p)
dim=len(listQ)
print("dim=%s"%dim)
factP1=factors(p=p)
rAlpha=findAlphas(listQ=listQ,tresholdAlpha=treshold,a=a,p=p)
objectA=findUnsingularMatrix(rAlpha=rAlpha,listQ=listQ,factors=factP1,tresholdMatrix=treshold)
listOfBeta,s=findBeta(listQ=listQ,treshold=treshold,a=a,b=b,p=p)
m=solveEqs(objectA=objectA,listOfBeta=listOfBeta,s=s)
print("m=")
print(m)
print("factors=")
print(factP1)
checker=True
for k in range(len(m)):
left=int(gap("%s mod %s"%(r,factP1[k])))
right=int(gap("%s mod %s"%(m[k],factP1[k])))
print("%s and founded %s for mod %s=%s,%s"%(r,m[k],factP1[k],left,right))
if(left==right):
checker=checker and True
else:
checker=checker and False
print("checker for %s^%s=%s mod %s is"%(a,r,b,p))
print(checker)
print("*****************")
arbp=[(6,3,7,11)]
for (a,r,b,p) in arbp:
try:
logByAdleman(a=a,r=r,b=b,p=p,treshold=7)
except:
try:
logByAdleman(a=a,r=r,b=b,p=p,treshold=11)
except:
print("FAILURE for a=%s,r=%s,b=%s,p=%s"%(a,r,b,p))