AdlemanAlgorithm.sagews

%md
### Adleman algorithm for the discrete logarithm problem

Adleman algorithm for the discrete logarithm problem

from numpy import *
import tree as tr
import sys

sys.setrecursionlimit(10000)
print("recursion limit = %s"%(sys.getrecursionlimit()))

recursion limit = 10000

# Adleman algorithm for the discrete logarithm problem
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
    #generate list of prime q
    while q<B1:
        q=int(gap("NextPrimeInt("+str(q)+")"))
        if q<B1:
            listQ.append(q)
        #if len(listQ)>1:
        #   break
    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])
    #print("factTmp=")
    #print(factTmp)
    countTmp=[factP1.count(k) for k in factTmp]
    #print("countTmp=")
    #print(countTmp)
    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=[]
        #self.listOfR=[]
    
    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)))#zeros
    listOfR=list(range(len(listQ)+1))#+1 len(listQ)
    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))
    #dictinary for storing solutions
    #for every a^r_{i} it contains list of possible alpha vectors
    rAlpha={}
    oAlphaCond=AlphaCond(listQ=listQ,p=p)
    searchAlpha=tr.Search(init=aa,object=oAlphaCond,treshold=tresholdAlpha,findAll=True)
    #step 2.0: find possible solutions
    for leftAr in listAr:
        searchAlpha.object.leftAr=leftAr
        searchAlpha.object.listAlpha=[]
        searchAlpha.listOfA=[aa]
        oo=searchAlpha.search()
        if oo:
            rAlpha[leftAr]=oo.listAlpha[:]
            #print("rAlpha[leftAr]=")
            #print(rAlpha[leftAr])
        else:
            print("fail!")
            break
    print("rAlpha.keys=")
    print(list(rAlpha.keys()))
    print("len(rAlpha)=")
    print([len(rAlpha[k]) for k in rAlpha.keys()] )
    #print("rAlpha[9]=")
    #print(rAlpha[9])
    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)
        #choice vectors for all keys (i.e. all (r,a^r))
        m=matrix([self.vectors[keys[i]][first[i]] for i in range(len(keys))])
        ##print("m=")
        #print(m)
        #print("vector[keys[0]]=")
        #print(self.vectors[keys[0]])
        #vector r from (r,a^r)
        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)
                #print("m1=")
                #print(strM)
                m1=matrix(gap(strM))
                #print("m=")
                #print(m)
                #print("mat=")
                #print(mat)
                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")
    #step 2.1: find unsingular matrix
    o=MatrixCond(rAlpha,factors)
    search=tr.Search(init=aa,object=o,treshold=tresholdMatrix)
    s=search.search()
    #print("s=")
    #print(s)
    if s:
        return(s)

def findBeta(listQ=listQ,treshold=6,a=0,b=0,p=0):
    aa=ones((len(listQ)))#zeros
    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:
        #print(s.listAlpha[-1])
        listOfBeta=s.listAlpha[0][:]
        return((listOfBeta,3))#

def solveEqs(objectA=objectA,listOfBeta=listOfBeta,s=s):
    #step 3: find log(q_{j}) vectors
    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
#6^3=7 mod 11+
#2^5=6 mod 13-
#2^3=8 mod 11+#2^3=8 mod 11+

def logByAdleman(a=0,r=0,b=0,p=0,treshold=11):
    #step 0: generate list of prime q
    listQ=genQ(p=p)

    dim=len(listQ)
    print("dim=%s"%dim)

    #step 1: factors of p-1 
    factP1=factors(p=p)

    #step 2: find dict with r and possible vectors a(r) i.e:
    #a^{r_{i}}=q_{1}^a_{i,1}*...*q_{k}^a_{i,k}
    rAlpha=findAlphas(listQ=listQ,tresholdAlpha=treshold,a=a,p=p)#11

    #step 3: find matrix A and vector r
    objectA=findUnsingularMatrix(rAlpha=rAlpha,listQ=listQ,factors=factP1,tresholdMatrix=treshold)#11

    #step 4: find betas
    #a^{s}*b=q_{1}^beta_{1}*...*q_{k}^beta_{k} mod p
    listOfBeta,s=findBeta(listQ=listQ,treshold=treshold,a=a,b=b,p=p)

    #step 5: solve matrix equations and find m_{l}
    m=solveEqs(objectA=objectA,listOfBeta=listOfBeta,s=s)
    print("m=")
    print(m)
    print("factors=")
    print(factP1)
    
    #step 6:check
    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("*****************")

#test1
#logByAdleman(a=6,r=3,b=7,p=11,treshold=7)
arbp=[(6,3,7,11)]
#arbp=[(6,3,7,11),(2,3,8,11),(7,3,2,11),(8,3,6,11)]
#arbp=[(2,5,6,13),(6,5,2,13),(7,5,11,13),(11,5,7,13)]
#arbp=[(2,7,11,13),(6,7,7,13),(7,7,6,13),(11,7,2,13)]
#tests
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))

#step 4.0:choice p_{k}
listP=[]
pk=int(B+1)

#generate list of prime q
while pk<B1:
    pk=int(gap("NextPrimeInt("+str(pk)+")"))
    listP.append(pk)
    if len(listP)>0:
        break
#listP=listP[1:]
print("listP=")
print(listP)

#step 4.1: generate listOfBeta
class BetaCond(tr.Condition):
    def __init__(self,listQ=listQ,listP=listP):
        tr.Condition.__init__(self)
        self.listQ=listQ
        self.multP=reduce(lambda x,res:x*res,listP,1)
        self.leftAr=int(gap(str((a**3)*b)+" mod "+str(p)))
        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),self.multP)
        rightAr=int(gap(str(int(rightAr))+" mod "+str(p)))
        if(rightAr==self.leftAr):
            if(list(first) not in self.listAlpha):
                self.listAlpha.append(list(first))
                print("betas=")
                print(self.listAlpha)
            #self.listAlpha.append(list(first))
            return(True)
        else:
            return(False)
oBetaCond=BetaCond()
#aa=ones((len(listP)))
searchBeta=tr.Search(init=aa,object=oBetaCond,treshold=6)
s=searchBeta.search()
if s:
    print(s.listAlpha[-1])
    listOfBeta=s.listAlpha[0][:]
#step 4.2: finding log_{a}(p_{i})
listOfLogsP=findLogs(listQ=listP,tresholdAlpha=11,tresholdMatrix=7)

print(1)

listP= [7] betas= [[1, 1, 2]] found [1, 1, 2] listAr= [(0, 1)] limit overflow rAlpha[leftAr]= [[10]] rAlpha.keys= [(0, 1)] len(rAlpha)= [1]

Error in lines 42-42 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 35, in findLogs File "tree.py", line 26, in search cond=self.object.cond(first) File "", line 16, in cond IndexError: list index out of range

listOfBeta= [2, 3] listOfLogsQ= [ 1, 1 ] listOfLogsP= [ 1, 1 ] 5 logAOfB=5

11 [(1, 0), (3, 1), (9, 2), (8, 3)] [[ 2, 0 ], [ 0, 2 ]] [[ 1, 0 ], [ 0, 1 ]]

'listG=gap(\'AllSmallGroups(27)\')\nfor g in listG:\n if not g.IsCyclic():\n print("IdGroup: %s \n LowerCentralSeries %s"%(g.IdGroup(),g.LowerCentralSeries()))\n' "\nG = gap('Group((1,2,3)(4,5), (3,4))')\nG.IsCyclic()\nG.IdGroup()\nG.LowerCentralSeries()\nvectors={0:[array([1,0]),array([0,1])],\n 1.5:[array([1,0]),array([0,1])]}\nfirst=[1,0]\nkeys=list(vectors.keys())\nm=matrix([vectors[keys[i]][first[i]] for i in range(len(keys))])\n\nMS=MatrixSpace(GF(7),2)\nmS=MS((m.astype(int)).tolist())\n#print(mS.inverse())\n#print(vector)\nv=vector([1,2])\n#print(v)\nstrM=str((m.astype(int)).tolist())+'^-1 mod '+str(7)\n#print(strM)\ngap(strM)\n"