# PRNG Sequence Guessing

# PRNG Sequence Guessing

+ 1 comment There is no editorial, the hints below are somewhat cryptic and even the problem description seems to have changed over time => so I take the freedom to publish some notes (please have merci ;-)

## state the problem

Given a sequence: with unknown seed (48 bit), and 10 successive samples . Determine the next 10 samples.

I will refer with 'lcg' (affine linear congruence generator, nerd speek for add/multiply/mod) to both the sequence and the generating formula.

(note that the reversed sequence is given by , where INV = pow(0x5DEECE66D, -1, 2**48) . )### timing

One can try to reconstruct the (first) seed. This is time critical in Python.

As a rule of thumb the time restrictions allow for about complex operations or simple operations, I'll call that the cost.### information

each sample gives us about 10bit information.

## the 'easy' solution ...

### missing in the description

The seeds for the testcases were generated from timestamps in seconds (date range 2000 - 2014), xor 0x5DEECE66D .

That is seed is 32bit (35bit after xor) .[note that the lcg is iterated 1 time before taking samples]

### determine the lower part of the seeds

Our samples only depend on the higher bits of the seeds, we have no information from the 17 bits to the right. However, as 1000 is divisible by 8, the rightmost 3 bits of the sample and those of seed[bit47..17] are identical. That means, we know seed[bit19..17] of every iteration of the lcg.

So we can**brute force**the lower part of the initial seed by taking any 20bit value, iterate and compare those 3bit. cost: , information: 20bit unknown, 3bit per sample: 7 samples sufficient.We can even start with (3bit from first sample)+17 arbitrary bits - cost: , information as above.

note that this works independent of whether seed is 48bit or 35bit.

### determine the higher part of the seeds

we know the lower 20 bits of all seeds by now.

As the initial seeds in the testcases are 35bit (32bit before xor), we are only missing 15 bit.

this can easily broken by**brute force**at a cost of :

take any combination of 15 bits + known lower part, iterate lcg , take samples and compare to given.## a little harder ...

It is not very satisfying to depend on some hidden weakening of requirements, ie. our algorithm should be able to handle any 48bit seed.

### go for the higher part of the seeds

the lower part of the seeds can be determined as above with cost .

we can

**brute force**the part seed[bit47..17] with values: sample + i*1000

at a cost of: which is just fast enough.

As above we iterate the lcg with this seeds, take samples and compare.

Information perspective: 28 bit of seed unknown, 7 bit per sample: 4 samples should suffice.### other possibilities

I would have liked to restrict the range for brute force even more, by looking at two consecutive seeds.

Did some calculations, but had no breakthrough.

Perhaps it may even be possible to calculate the seed from the samples without brute force - beyond my knowledge, perhaps some number theory wizards drop in here....

+ 1 comment from typing import List MULTIPLIER = 0x5DEECE66D ADDEND = 0xB MASK = (1 << 48) - 1 MODULO = 1000 RIGHT_SHIFT = 17 def update_seed(seed: int) -> int: return (seed * MULTIPLIER + ADDEND) & MASK def next_int(seed: int, n: int = MODULO) -> int: return (seed >> RIGHT_SHIFT) % n def solution(nums: List[int]) -> List[int]: for lower_bits in range(2 ** 20): is_all_match = True seed = lower_bits for value in nums: seed = update_seed(seed) if (next_int(seed) & 7) != (value & 7): is_all_match = False break if not is_all_match: continue for higher_bits in range(2 ** 28): is_all_match = True seed = (higher_bits << 20) | lower_bits for value in nums: seed = update_seed(seed) if (next_int(seed) != value): is_all_match = False break if is_all_match: remaining_nums = [] for _ in range(10): seed = update_seed(seed) remaining_nums.append(next_int(seed)) return remaining_nums return [] def main(): num_inputs = [list(map(int, input().split())) for _ in range(int(input()))] for nums in num_inputs: print(" ".join(map(str, solution(nums)))) main()

[deleted] + 0 comments Java - 7` import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution { public static void main(String[] args) { long seeds[] = {1374037200,1374037459,1057556953,1226891312,1287968623,1282073374,1287158953,1159300833,1139155438,1074640221,1040332083,1347392806,990639200,969276712,1182050116,1265867460,1257725758,1185815629}; Scanner stdin = new Scanner(System.in); int testCaseCount = stdin.nextInt(); for (int testCaseIndex = 0; testCaseIndex < testCaseCount; testCaseIndex += 1) { int[] values = new int[10];

`for (int j = 0; j < 10; j++) { values[j] = stdin.nextInt(); } for (int s=0;s<18;s++) { Random rand = new Random(seeds[s]); boolean bad = false; for (int valueIndex = 0; valueIndex < values.length; valueIndex++) { if (rand.nextInt(1000) != values[valueIndex]) { bad = true; break; } } if (!bad) { //System.out.print(seed); //System.out.print(" "); for (int i = 0; i < 10; i++) { System.out.print(rand.nextInt(1000)); System.out.print(" "); } System.out.print("\n"); } } } }`

} `

+ 0 comments How do we figure out the seeds?

+ 0 comments I don't get how we are supposed to figure out the seed from the generated numbers. We can't work backwards from the math because some of the operations performed are irreversible bit operations.

Sort 51 Discussions, By:

Please Login in order to post a comment