A reversal of the pikmin LCG from some inequalities

gistfile1.txt

import copy

def lcg(seed):
    return (seed*1103515245+12345) % 2**31

def invlcg(seed):
    return ((seed-12345)*1857678181) % 2**31

def getCeils(list):
    newlist = []
    for x in range(0,len(list)):
        newlist.append(RR(list[x]).ceil())
    return newlist

def getFloors(list):
    newlist = []
    for x in range(0,len(list)):
        newlist.append(RR(list[x]).floor())
    return newlist

def isInRegion(point, LowerBounds, UpperBounds):
    for x in range(0,len(point)):
        if point[x] < LowerBounds[x] or point[x] > UpperBounds[x]:
            return false
    return true

def getNextPoint(components, v, A, min1, max1):
    for index in range(0,len(components)):
        components[index]+=1
        v += A[index]
        if components[index] > max1[index]:
            components[index] = min1[index]
            v -= A[index]*(max1[index]-min1[index]+1)
        else:
            return [components, v]
    return None

def printPointForJava(p):
    s = "{"
    for x in range(len(p)-1):
        s += str(p[x])+"L, "
    s+=str(p[-1])+"}"
    print s

def printMatrixForJava(a):
    for x in a:
        s = "{"
        for y in range(len(x)-1):
            s+= str(x[y]) + "L, "
        print s + str(x[-1])+"L},"

def printSmallMatrixForJava(a):
    for x in a:
        s = "{"
        for y in range(len(x)-1):
            s+= str(x[y]) + ", "
        print s + str(x[-1])+"},"

def dumbiterate(mins, maxes, A, P, LowerBounds, UpperBounds): #this can be replaced by an LP based branch and bound solver
    GOOD = []
    temp = copy.deepcopy(mins)
    v = vector(temp)*A+P
    while true:
        if isInRegion(v, LowerBounds, UpperBounds):
            GOOD.append(v)
        n = getNextPoint(temp, v, A, mins, maxes)
        if n == None:
            return GOOD
        temp = n[0]
        v = n[1]

# UpperBounds - A list of 48 bit seeds which are guaranteed to be greater than the desired seeds.
# LowerBounds - A list of 48 bit seeds which are guaranteed to be less than the desired seeds.
# GapsBetweenCalls - A list of the gaps between the seeds you care about. Note that nextLong and nextDouble count as a gap of 2. If there were N nextInt calls between two seeds you have provided upper and lower bounds for, that would be a gap of N.
# This website is very very very very slow. If you have an application which seems to be taking very long and has a constant GapsBetweenCalls list I would recommend printing the matrices P, a, aLLL, and aLLLinv, and implementing the rest of the algorithm in a local program. What takes minutes on here can still run in under a second if done correctly. Attacking nextInt(bound) is not Currently handled by this code but is susceptible to similar methods.
def findAllSeedTuplesInBB(LowerBounds, UpperBounds, GapsBetweenCalls):
    seed = 0;
    N = len(UpperBounds)
    list1 = []
    for i in range(0,N):
        list1.append(seed)
        for i in range(GapsBetweenCalls[i]): #TODO add fast formula for this
            seed = lcg(seed)
    P = vector(list1)
    a = matrix(ZZ,N,N)
    a[0,0] = 1
    for i in range(1,N):
        a[i,i] = 2**31
        a[0,i] = a[0,i-1]*(1103515245**(GapsBetweenCalls[i-1])) % 2**31
    aLLL = a.LLL(.99,.5)
    print aLLL
    aLLLinv = aLLL.inverse()
    print
    print aLLL.inverse()
    min = [0]*N
    max = [0]*N
    for x in range(N):
        for y in range(N):
            if aLLLinv[x][y] < 0:
                min[y] += (UpperBounds[x] - P[x])*aLLLinv[x][y]
                max[y] += (LowerBounds[x] - P[x])*aLLLinv[x][y]
            else:
                max[y] += (UpperBounds[x] - P[x])*aLLLinv[x][y]
                min[y] += (LowerBounds[x] - P[x])*aLLLinv[x][y]
    print getFloors(max);
    print getCeils(min);
    print vector(getFloors(max)) - vector(getCeils(min)) + vector([1]*N)
    avg = vector(getFloors(list((vector(getFloors(max)) + vector(getCeils(min)))/2)))
    return dumbiterate(getCeils(min), getFloors(max), aLLL, P, LowerBounds, UpperBounds)


n = 9;
#the first list and the second list are the minimum and maximum bounds on each s_i. Right now I am looking for seeds which give 9 0s
for x in findAllSeedTuplesInBB([0]*9,[2^31 / 9]*9,[1]*9):
    print invlcg(x[0])