pyspeedup/algorithms/_indexCalculus.py
def rowReduce(lstList,p):
    '''Takes a list of lists as a representation of rows of a matrix mod p, and reduces it.'''
    #Partial Gaussian Elimination, pivoting on invertible elements.
    length=min(len(lstList),len(lstList[0])-1)
    for i in range(0,length):
        if lstList[i][i]%p==0 or gcd(lstList[i][i],p)!=1:
            for j in range(i,len(lstList)):
                if lstList[j][i]%p!=0 and gcd(lstList[j][i],p)==1:
                    lstList.insert(i,lstList.pop(j))
                    break
            if lstList[i][i]%p==0:
                continue
        for j in range(i+1,len(lstList)):
            if lstList[j][i]%p==0:
                continue
            try: #Tries division, and has a default alternative.
                scalingfactor=divideMod(lstList[j][i],lstList[i][i],p)
            except: #This won't change the results, but may reduce the magnitude.
                scalingfactor=lstList[j][i]//lstList[i][i]
            for k in range(len(lstList[0])):
                lstList[j][k]-=(scalingfactor*lstList[i][k])
                lstList[j][k]%=p
    for i in range(0,length):
        if lstList[i][i]%p==0:
            continue
        if lstList[i][i]!=1:
            try:
                inv=invMod(lstList[i][i],p)
            except:
                inv=(p//lstList[i][i])+1 #Won't change anything but will allow different values.
            lstList[i]=[(x*inv)%p for x in lstList[i]]
        for j in range(i):
            if lstList[j][i]%p==0:
                continue
            try:
                inv=divideMod(lstList[j][i],lstList[i][i],p)
            except:
                continue
            for k in range(len(lstList[0])):
                lstList[j][k]-=(inv*lstList[i][k])
                lstList[j][k]%=p
    #If this reduces a row to zeros or an unsolvable result, remove it.
    for i in reversed(range(len(lstList))):
        if lstList[i] and not any(lstList[i][0:-1]):
            lstList.pop(i)
    return lstList
Takes a list of lists as a representation of rows of a matrix mod p, and reduces it.
Takes a list of lists as a representation of rows of a matrix mod p, and reduces it.
Takes a list of lists as a representation of rows of a matrix mod p and reduces it .
def rowReduce(lstList,p):
    length=min(len(lstList),len(lstList[0])-1)
    for i in range(0,length):
        if lstList[i][i]%p==0 or gcd(lstList[i][i],p)!=1:
            for j in range(i,len(lstList)):
                if lstList[j][i]%p!=0 and gcd(lstList[j][i],p)==1:
                    lstList.insert(i,lstList.pop(j))
                    break
            if lstList[i][i]%p==0:
                continue
        for j in range(i+1,len(lstList)):
            if lstList[j][i]%p==0:
                continue
            try: 
                scalingfactor=divideMod(lstList[j][i],lstList[i][i],p)
            except: 
                scalingfactor=lstList[j][i]//lstList[i][i]
            for k in range(len(lstList[0])):
                lstList[j][k]-=(scalingfactor*lstList[i][k])
                lstList[j][k]%=p
    for i in range(0,length):
        if lstList[i][i]%p==0:
            continue
        if lstList[i][i]!=1:
            try:
                inv=invMod(lstList[i][i],p)
            except:
                inv=(p//lstList[i][i])+1 
            lstList[i]=[(x*inv)%p for x in lstList[i]]
        for j in range(i):
            if lstList[j][i]%p==0:
                continue
            try:
                inv=divideMod(lstList[j][i],lstList[i][i],p)
            except:
                continue
            for k in range(len(lstList[0])):
                lstList[j][k]-=(inv*lstList[i][k])
                lstList[j][k]%=p
    for i in reversed(range(len(lstList))):
        if lstList[i] and not any(lstList[i][0:-1]):
            lstList.pop(i)
    return lstList
def rowReduce ( lstList , p ) : length = min ( len ( lstList ) , len ( lstList [ 0 ] ) - 1 ) for i in range ( 0 , length ) : if lstList [ i ] [ i ] % p == 0 or gcd ( lstList [ i ] [ i ] , p ) != 1 : for j in range ( i , len ( lstList ) ) : if lstList [ j ] [ i ] % p != 0 and gcd ( lstList [ j ] [ i ] , p ) == 1 : lstList . insert ( i , lstList . pop ( j ) ) break if lstList [ i ] [ i ] % p == 0 : continue for j in range ( i + 1 , len ( lstList ) ) : if lstList [ j ] [ i ] % p == 0 : continue try : scalingfactor = divideMod ( lstList [ j ] [ i ] , lstList [ i ] [ i ] , p ) except : scalingfactor = lstList [ j ] [ i ] // lstList [ i ] [ i ] for k in range ( len ( lstList [ 0 ] ) ) : lstList [ j ] [ k ] -= ( scalingfactor * lstList [ i ] [ k ] ) lstList [ j ] [ k ] %= p for i in range ( 0 , length ) : if lstList [ i ] [ i ] % p == 0 : continue if lstList [ i ] [ i ] != 1 : try : inv = invMod ( lstList [ i ] [ i ] , p ) except : inv = ( p // lstList [ i ] [ i ] ) + 1 lstList [ i ] = [ ( x * inv ) % p for x in lstList [ i ] ] for j in range ( i ) : if lstList [ j ] [ i ] % p == 0 : continue try : inv = divideMod ( lstList [ j ] [ i ] , lstList [ i ] [ i ] , p ) except : continue for k in range ( len ( lstList [ 0 ] ) ) : lstList [ j ] [ k ] -= ( inv * lstList [ i ] [ k ] ) lstList [ j ] [ k ] %= p for i in reversed ( range ( len ( lstList ) ) ) : if lstList [ i ] and not any ( lstList [ i ] [ 0 : - 1 ] ) : lstList . pop ( i ) return lstList
Takes a list of lists as a representation of rows of a matrix mod p, and reduces it.
Takes a list of lists as a representation of rows of a matrix mod p and reduces it .
'''Takes a list of lists as a representation of rows of a matrix mod p, and reduces it.''' #Partial Gaussian Elimination, pivoting on invertible elements. #Tries division, and has a default alternative. #This won't change the results, but may reduce the magnitude. #Won't change anything but will allow different values. #If this reduces a row to zeros or an unsolvable result, remove it.
lstList
p