Skip to content

Instantly share code, notes, and snippets.

@mjtb49
Created April 19, 2020 20:42
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mjtb49/a9b750e0048c09ada31896e5617f4fd0 to your computer and use it in GitHub Desktop.
A reversal of the pikmin LCG from some inequalities
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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment