Recreational Mathematics Club


Recreational Mathematics Club	Discussion #4

12-Eye Portal Seed and the LLL algorithm

Speaker: Dhairya Baxi, Mahek Shamsukha	Indian Institute of Science

1 What is a Linear Congruential Generator?

A Linear Congruential Generator (LCG) is a simple pseudorandom number generator (PRNG) defined by the recurrence relation:

seed := (a ⋅seed+ b) mod m

where the parameters are:

m > 0, the modulus
a, the multiplier, with 0 < a < m
b, the increment, with 0 ≤ b < m
seed, the current state, initialised to some value seed₀ ∈ [0,m)

Each call to the generator updates the seed and outputs it (or some function of it) as the next pseudorandom value. The entire future sequence is thus fully determined by the initial seed and the triple (a,b,m).

2 Primer: Modular Inverses

The modular inverse of an integer a modulo m is the integer a⁻¹ such that:

a⋅a− 1 ≡ 1 (mod m )

It exists if and only if gcd(a,m) = 1. When it does, it can be computed efficiently in O(log m) using the Extended Euclidean Algorithm:

Algorithm 1: mod_inverse(a,m)

1:   Input: integers a, m
2:   Output: a⁻¹ mod m
3:   g,x, _ ← ExtendedGCD(a,m)
4:   if g≠1 then
5:    return inverse does not exist
6:   end if
7:   return x mod m

Modular inverses let us “divide” in modular arithmetic, instead of computing x∕a mod m, we compute x ⋅ a⁻¹ mod m.

3 Next and Forward Routines

We define two fundamental operations on an LCG state.

3.1 Primitive: next

next(x) applies one step of the recurrence:

next(x) = (a⋅x + b) mod m

3.2 Naive forward

forward(x,n) applies next n times iteratively:

Algorithm 2: forward(x,n), naive O(n)

1:   Input: state x, step count n
2:   Output: nextⁿ(x)
3:   for i = 1 to n do
4:    x ← (a ⋅ x + b) mod m
5:   end for
6:   return x

This runs in O(n) time, which is impractical for large n.

3.3 Closed Form

Unrolling the recurrence n times gives:

n−1 forward (x,n) = a(a(...(a ⋅x+ b) ...)+ b) + b mod m = anx + b∑ ai mod m i=0

Applying the geometric series formula (for a≠1):

( ) forward (x,n) = anx + b an −-1 mod m a − 1

This reduces the problem to computing aⁿ mod m, which can be done in O(log n) via fast modular exponentiation.

3.4 Efficient forward in O(log n)

Algorithm 3: forward(x,n), efficient O(log n)

The modular inverse of (a − 1) exists whenever gcd(a − 1, m) = 1, which holds for typical LCG parameters.

4 Prev and Backward Routines

4.1 Primitive: prev

Just as next applies the recurrence forward, prev(x) inverts it, recovering the state that would have produced x. Starting from:

x = (a ⋅x + b) mod m prev

we solve for x_prev:

xprev = a−1(x − b) mod m

where a⁻¹ is the modular inverse of a modulo m (which exists when gcd(a,m) = 1). In code:

4.2 Primitive: backward

backward(x,n) applies prev n times, stepping the generator n steps into the past. The naive implementation runs in O(n):

Algorithm 5: backward(x,n)

1:   Input: state x, step count n
2:   Output: prevⁿ(x)
3:   for i = 1 to n do
4:    x ← Prev(x)
5:   end for
6:   return x

Note that backward(x,n) is equivalent to forward(x,−n), so an efficient O(log n) version follows from the same closed form as before, substituting a⁻¹ and −b ⋅ a⁻¹ as the new multiplier and increment respectively.

5 The Seed-Finding Problem

The general problem is to find an initial seed whose LCG outputs fall within prescribed intervals over several consecutive steps. For a concrete application of this framework to finding Minecraft world seeds with fully-filled stronghold portals, see Appendix A.

5.1 General Problem Formulation

More generally, the problem we study is:

Given bounds m₁,M₁,…,m_k,M_k and an offset n, find an initial seed seed₀ such that for each i ∈{1,…,k}:
$mi ≤ seedn+i ≤ Mi$

That is, we want k consecutive outputs of the LCG, starting from step n, to each fall within a prescribed interval. The challenge is to search over the space of possible seeds seed₀ ∈ [0,m) efficiently, brute force is infeasible when m is large (e.g. m = 2⁴⁸ in Java’s Random).

5.2 Reducing to Constraints on seed₀

Using the closed form for forward, every constraint on seed_n+i can be written directly in terms of seed₀. Crucially, the offset n is handled for free: given any candidate seed_n, we can recover seed₀ = backward(seed_n,n) in O(log n), or equivalently jump ahead with forward(seed₀,n). This means we can freely translate between constraints on seed₀ and constraints on any other step.

Expressing seed_n+i = forward(seed₀, n + i) via the closed form, the system of k constraints becomes (shown here for n = 0, k = 12):

⌊ (a0 − 1) ⌋ min ≤ a0seed0 + b ------ mod m ≤ max 0 a− 1 0

⌊ ( ) ⌋ 1 a1-−-1 min1 ≤ a seed0 + b a− 1 mod m ≤ ma1x

...

⌊ ( 11 ) ⌋ min ≤ a11seed + b a---−-1 mod m ≤ max 11 0 a − 1 11

Each constraint is a modular interval condition on seed₀. The problem reduces to finding all seed₀ ∈ [0,m) satisfying all k such constraints simultaneously.

5.3 Removing the Modulus

The modular reduction is the main obstacle to solving the system directly. We eliminate it by observing that x mod m = x − km for some integer k ≥ 0. That is, for each constraint i there exists an unknown integer k_i such that:

( ) i ai −-1 a seed0 + b a − 1 − kim

is the true (non-reduced) value. Substituting this into the bounds and rearranging, moving the b( ⋅⋅⋅ ) term to both sides, each modular inequality becomes an ordinary linear inequality:

( ) ( ) a0-−-1 0 a0 −-1- mi0n − b a− 1 ≤ a seed0 + k0m ≤ max0 − b a − 1

( 1 ) ( 1 ) min − b a--−-1 ≤ a1 seed + k m ≤ max − b a-−-1- 1 a− 1 0 1 1 a − 1

. ..

( a11 − 1) ( a11 − 1) min − b ------- ≤ a11seed0 + k11m ≤ max − b ------- 11 a − 1 11 a − 1

The system now has k + 1 unknowns (seed₀ and the integers k₀,…,k_k−1) and 2k linear inequalities over the integers. No modular arithmetic remains, the problem has been lifted to an integer linear feasibility problem.

5.4 Matrix Formulation

We can write the system compactly by collecting the unknowns into a vector = (seed₀, k₀, k₁, …, k_n−1)^⊤ and defining:

⌊ ⌋ ( 0 ) ⌊ 1 0 0 ⋅⋅⋅ 0⌋ || b aα1 −-1 || | α1 | || ( a− 1 ) || || aα2 m 0 ⋅⋅⋅ 0|| || aα2 −-1 || A = | a 0 m ⋅⋅⋅ 0| , ˆb = | b a− 1 | , |⌈ ... ... ... ... ...|⌉ || .. || aαn−1 0 0 ⋅⋅⋅ m || ( . )|| ⌈b aαn−1 −-1 ⌉ a− 1

⌊ ⌋ ⌊ ⌋ min0 max0 ^ || min1 || || max1 || min = |⌈ ... |⌉, m^ax = |⌈ ... |⌉. minn− 1 maxn − 1

The entire seed-finding problem then reduces to finding an integer vector such that:

^min ≤ A ˆx+ ˆb ≤ m^ax

subject to 0 ≤ x₁ = seed₀ < m. Crucially, the possible values of A + mod m are exactly the possible tuples of consecutive LCG seeds, so any solution directly yields a valid initial seed.

5.5 Geometric Interpretation: A Lattice Problem

The columns of A generate a lattice, the set of all integer linear combinations A for ∈ ℤⁿ. The constraint ^min ≤ A + ≤ m^ax asks for lattice points that land inside the axis-aligned box [ ^min , m^ax ] after the shift by ˆ
b .

Equivalently, applying A⁻¹ to both sides transforms the axis-aligned box into a (potentially skewed) parallelogram in the space of integer vectors , and we seek all integer points inside that parallelogram. This is illustrated below:

Figure 1: Left: the lattice spanned by columns a₀,a₁ of A, with the target box (grey) and lattice points inside it (green). Right: after applying A⁻¹, the lattice becomes ℤⁿ and the box becomes a skewed parallelogram, we now seek integer points inside it.

This reframing connects the seed-finding problem to classical problems in the geometry of numbers, and motivates the use of lattice reduction algorithms such as LLL to efficiently enumerate solutions.

6 Branch and Bound

Having reduced the problem to finding integer vectors satisfying ^
min ≤ A + ˆ
b ≤ m^ax , we now describe how to enumerate all such solutions via branch and bound.

6.1 The Linear Programme

Because A is lower triangular, the system ^
min ≤ A + ˆ
b ≤ ^max can be solved one variable at a time from the bottom row upward. Suppose components x_i+1,…,x_n−1 have already been fixed. Row i of the system reads:

^ ∑ ˆ mini ≤ Aiixi + Aij xj + bi ≤ m^axi j◟>i--◝◜-----◞ known

Isolating x_i gives the real interval:

^ ˆ ∑ ˆ ∑ l = mini-−-bi −--j>iAij xj-, u = ^maxi-−-bi −--j>iAij xj i Aii i Aii

Since x_i must be an integer, the feasible values are x_i ∈{⌈l_i⌉,…,⌊u_i⌋}. If ⌈l_i⌉ > ⌊u_i⌋, the partial assignment is infeasible and the branch is immediately pruned.

6.2 The Subroutine

The algorithm recurses from the last variable to the first, branching over all integer values in the feasible interval at each level:

Algorithm 6: BranchAndBound(A, , , , , i)

^min — Algorithm 6: BranchAndBound(A, , , , , i)

The outermost call is BranchAndBound(A, , ^min , m^ax , x, n− 1). Each leaf that reaches i < 0 yields a valid , from which seed₀ = x₀ is read off directly.

The worst-case complexity is exponential in the number of solutions, but pruning makes it efficient in practice when the feasible parallelogram is small, which is precisely what LLL achieves by reducing the basis before running this search.

7 Basis Choice and Lattice Reduction

7.1 Different Bases, Same Lattice

A lattice ℒ has infinitely many bases. If B = (b₁,…,b_n) is one basis and U is any unimodular matrix (integer matrix with detU = ±1), then BU is another valid basis generating the same lattice.

Observation. Two bases for the same lattice can produce parallelograms of wildly different shapes. A skewed basis yields a thin, elongated parallelogram; an orthogonal basis yields a compact, box-like one.

7.2 What Makes a Good Basis?

We want a basis B = (b₁,…,b_n) where:

The vectors b_i are reasonably short (no unnecessarily long directions),
The vectors are nearly orthogonal (small off-diagonal Gram–Schmidt coefficients),
The Gram–Schmidt lengths ∥b_i^∗∥ do not drop too rapidly (avoiding highly skewed configurations).

Such a basis makes the corresponding parallelepiped well-shaped and better aligned with the coordinate axes, dramatically improving the performance of branch-and-bound methods.

Motivation for the next step. Finding an optimal basis (e.g. shortest or most orthogonal) is NP-hard in general. However, efficient approximation algorithms exist. The most celebrated is the LLL algorithm (Lenstra–Lenstra–Lovász, 1982), which computes, in polynomial time, a basis that is nearly orthogonal and well-balanced. In particular, it guarantees that the first basis vector is within an exponential factor of the shortest nonzero lattice vector.

8 The LLL Algorithm

8.1 δ-LLL Reduced Basis

Let B = (b₁,…,b_n) be a basis of a lattice ℒ⊂ ℝ^m. Let b₁^∗,…,b_n^∗ be its Gram–Schmidt orthogonalization:

∑ bi = b∗i + μi,jb∗j. j<i

Definition 8.1. Let δ ∈ (1∕4,1). The basis B is called δ-LLL reduced if:

1.: For all i > j, |μ_i,j|≤,
2.: For all i = 1,…,n − 1, $∥b∗ ∥2 ≥ (δ − μ2 )∥b∗∥2. i+1 i+1,i i$

8.2 Bound on the Shortest Vector

Theorem 8.2. If B is a δ-LLL reduced basis of ℒ, then

n−1 ∥b1∥ ≤ 2 2 ⋅λ1(ℒ ),

where λ₁(ℒ) is the length of the shortest nonzero lattice vector.

8.3 LLL Algorithm

Algorithm 7: LLL(B, δ)

1:   Input: B ∈ ℤ^m×n, δ ∈ (1∕4,1)
2:   Output: A δ-LLL reduced basis generating the same lattice
3:   B ← SizeReduce(B)
4:   if ∃i such that ∥b_i+1^∗∥² < (δ − μ_i+1,i²)∥b_i^∗∥² then
5:    Swap b_i,b_i+1
6:    return LLL(B,δ)
7:   end if
8:   return B

8.4 Size Reduction via Column Operations

Recall the Gram–Schmidt decomposition

∗ B = B M,

where B^∗ = (b₁^∗,…,b_n^∗) has orthogonal columns and M = (μ_i,j) is upper triangular with μ_i,i = 1.

Size reduction corresponds to modifying the columns of B using integer column operations so that

1 |μi,j| ≤ 2 for all i > j.

We proceed column by column. For j = 1,…,n, and for i = j − 1,j − 2,…,1, perform the operation

bj ← bj − ⌊μj,i⌉bi,

where ⌊⋅⌉ denotes rounding to the nearest integer.

This is an elementary column operation on B, and corresponds to updating the matrix M by

μj,i ← μj,i − ⌊μj,i⌉,

which ensures

1 |μj,i| ≤ 2.

Key point. Size reduction is achieved purely by integer column operations on B, preserving the lattice, while ensuring all Gram–Schmidt coefficients satisfy |μ_i,j|≤.

8.5 Existence of LLL-Reduced Basis

Theorem 8.3. Let B ∈ ℤ^m×n be an integer basis and let δ ∈ (1∕4,1). Then there exists an integer basis B′ such that:

1.: B′ is δ-LLL reduced,
2.: B′ generates the same lattice as B.

Proof. We prove correctness and finiteness of the LLL algorithm.

(Correctness). If the algorithm terminates, then no Lovász condition is violated, and the basis is size-reduced. Hence the output basis is δ-LLL reduced.

(Lattice preservation). All operations used are integer column operations:

size reduction replaces b_j by b_j − kb_i,
swaps exchange two basis vectors.

Thus the output basis is obtained from the input by unimodular transformations, and therefore generates the same lattice.

(Finiteness) Define a potential

∏n Φ (B) := det(ℒ (b1,...,bi)), i=1

where ℒ(b₁,…,b_i) denotes the lattice generated by b₁,…,b_i.

Equivalently, since

∏i det(ℒ(b1,...,bi)) = vol of the fundamental parallelepiped = ∥b∗j∥, j=1

we may write

n i Φ (B) = ∏ ∏ ∥b∗∥. j i=1j=1

Effect of size reduction. Size reduction does not change the Gram–Schmidt vectors b_j^∗. Hence Φ(B) remains unchanged.

Effect of swapping b_i,b_i+1. All prefixes except the i-th remain unchanged, so only the factor

det(ℒ (b1,...,bi))

changes.

Let Φ′ denote the potential after swapping b_i and b_i+1.

First observe how the Gram–Schmidt vectors change. Consider the prefix

(b1,...,bi−1,bi+1 ).

For this sequence, the Gram–Schmidt vectors are

b∗1,...,b∗i−1, b∗i′+1,

where the first i − 1 vectors remain unchanged, and

i− 1 ∗′ ∑ ∗ ∗ ∗ bi+1 = bi+1 − μi+1,jbj = bi+1 + μi+1,ibi. j=1

Thus,

∥b∗′ ∥2 = ∥b∗ ∥2 + μ2 ∥b∗∥2. i+1 i+1 i+1,i i

Now, since only the i-th prefix changes in the potential, we have

′ ∗′ Φ--= det(ℒ-(b1,...,bi−1,bi+1))= ∥bi+1∥-. Φ det(ℒ (b1,...,bi)) ∥b∗i∥

If the Lovász condition is violated, then

∗ 2 2 ∗ 2 ∥bi+1∥ < (δ − μi+1,i)∥bi∥ ,

and hence

∗′ 2 ∗ 2 ∥bi+1∥ < δ∥bi∥ .

Taking square roots,

Φ′ √-- --< δ < 1. Φ

Finiteness. Observe that for each i,

∘ ---------- det(ℒ(b1,...,bi)) = det(BTi Bi ),

where B_i is the matrix with columns b₁,…,b_i. Since B_i has integer entries, det(B_i^TB_i) is an integer, and hence each factor in Φ(B) is a square root of a positive integer.

Therefore, Φ(B) itself is a product of square roots of integers, and can take values only in a discrete subset of ℝ_>0. In particular, in the interval (0,Φ(Bⁱⁿ)], it can assume only finitely many values.

Since each swap strictly decreases Φ(B) by at least a constant factor √ --
δ < 1, the sequence of potentials is strictly decreasing and cannot be infinite.

Therefore, the algorithm terminates.

Combining the above, a δ-LLL reduced basis B′ exists. □

References

Minecraft 12-Eyed Seed Explanation (YouTube video)
https://www.youtube.com/watch?v=mc9w2iD3Gzs
D. Micciancio, CSE206A: Lattice Algorithms and Applications (Winter 2010)
Lecture notes, UC San Diego
https://cseweb.ucsd.edu/classes/wi10/cse206a/
O. Regev, Lattices in Computer Science (Fall 2004)
Lecture notes, Tel Aviv University
https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/

A Appendix: Minecraft 12-Eyed Seed

In Minecraft, an End Portal consists of 12 slots, each of which requires an Ender Eye to be filled. When a world is generated, each slot may already be pre-filled.

Internally, this is determined using calls to a pseudorandom generator (Random::nextFloat() in Java), which maps the internal seed to a value in [0,1). A slot is filled if this value exceeds 0.9.

The Java random number generator is a linear congruential generator:

seedi+1 ≡ 25214903917 ⋅seedi + 11 (mod 248).

In the world-generation pipeline, the first 760 calls are irrelevant for the portal. Thus, we begin at seed₇₆₁ and require that the next 12 calls all satisfy

nextFloat() > 0.9.

This translates to the constraint

seedi ∈ [253327472328704, 248 − 1], i = 761,...,772,

since

0.9 ⋅248 = 253327472328704.

Connection to our problem. This is an instance of the LCG constraint problem with:

modulus m = 2⁴⁸,
multiplier a = 25214903917, increment b = 11,
n = 760 unconstrained steps,
k = 12 constrained steps,
uniform bounds m_i = 253327472328704 and M_i = 2⁴⁸ − 1.

Thus, finding a 12-eyed seed reduces to finding integer points satisfying linear constraints derived from an LCG, precisely the type of problem we studied using lattice methods and the LLL algorithm.