Create a mathematical selection for a large number

It is necessary to create a method for selecting seed, a, b mathematically without generators so that it takes milliseconds (maximum up to 1 minute) for 25 billion 4-digit numbers

Like 1234 3214 1122 1234 3412 1123 4234 4411...

Also, 100% recovery and maximum speed

The main description I made with chat gpt

Technical task (updated)

Goal

Implement a system consisting of two modules:

1. Selection (Recovery): find seed, a, b from a short fragment of the series.

2. Reproduction: generate a series of up to 25 billion numbers (1..4).

---

Data format

Base element: digit from the set {1,2,3,4}.

Packaging: 8 digits → 64 bits (2 bits per digit). This is one block.

Window for selection: W = 32..64 consecutive blocks.

---

MODULE A. SELECTION (Recovery)

A1. Input

y_window: array of W packed blocks (uint64) — consecutive.

seed_candidates: list of seed candidates (for example, [0..4095] or provided file with the list).

n0_local: known local index of the first block in the window (can be 0 if global is not needed).

A2. Output

seed: found seed.

a: difference (multiplier) modulo 2⁶⁴, odd.

b: offset modulo 2⁶⁴.

status: OK / FAIL (+ diagnostics).

A3. Model (for implementation)

x_n = (a*n + b) mod 2^64, where a is odd.

y_n = PRP_seed(x_n), where PRP_seed is the inverted permutation 64-bit (we provide implementation/interface).

A4. Selection algorithm (without brute force over the entire space)

For each seed in seed_candidates:

1. Calculate key PRP_seed^{-1}.

2. Invert the first 2 blocks:

x0 = PRP_inv(y0), x1 = PRP_inv(y1), set a = (x1 - x0) mod 2^64.

(If a is even — quick rejection.)

3. For i=2..W-1:

xi = PRP_inv(yi) and check (xi - x_{i-1}) == a.

If there is a mismatch — reject this seed.

4. If all differences are the same — seed found.

Calculate b = (x0 - a*n0_local) mod 2^64.

Return (seed,a,b) as the result.

> Computational complexity ~O(|seed_candidates| · W). For |seed_candidates|≤4096 and W≤64 — tens of ms.

A5. Pseudocode

for seed in seed_candidates:

    key = PRP_make_key(seed)

    x0 = PRP_inv(y[0], key)

    x1 = PRP_inv(y[1], key)

    a = (x1 - x0) mod 2^64

    if (a % 2 == 0): continue

    ok = True

    prev = x1

    for i in 2..W-1:

        xi = PRP_inv(y[i], key)

        if ((xi - prev) mod 2^64) != a: ok = False; break

        prev = xi

    if ok:

        b = (x0 - a*n0_local) mod 2^64

        return (OK, seed, a, b)

return (FAIL, -, -, -)

A6. Checks/validation

After finding (seed,a,b) check another 8–16 subsequent blocks (if any) for constant difference.

Optionally: generate 8–16 blocks ahead from n0_local and compare with provided ones.

---

MODULE B. OFFSET

B1. Input

y_obs: one observed block (uint64).

seed, a, b — obtained from Module A.

B2. Output

n: global index of the block (mod 2⁶⁴; if absolute is needed within the file — describe the range of pages/blocks).

B3. Formula

x = PRP_inv(y_obs, seed)

ainv = inverse_mod_2_64(a) // a is odd

n = (x - b) * ainv (mod 2^64)

B4. Time

O(1): one PRP inversion + one modular inversion (pre-prepared) + several 64-bit operations → microseconds.

---

MODULE C. REPRODUCTION OF THE SERIES

C1. Input

seed, a, b

start_n, count (range for generation)

C2. Output

Stream of blocks y_n in the specified range (packed 64-bit), or unpacked digits {1..4} (optional).

Support for streaming output to file in the format of 2 bits/digit.

C3. Algorithm

x = a*start_n + b

for i in 0..count-1:

    y = PRP_seed(x)

    output(y)

    x += a

(Unpacking 8 digits from 64 bits — simple extraction of 2-bit fields +1.)

---

Performance requirements

Selection (W=64, |seed_candidates|≤4096): < 100 ms on a regular laptop.

Offset: ≈ microseconds.

Generation of 25 billion digits (with 2-bit packaging, 4 streams): ~2–6 minutes on Dell Latitude 5400 (benchmark).

---

Technical requirements for implementation

Language: C++17/20, compilation with -O3 -march=native.

Light PRP (inverted): 3–4 rounds of Feistel with 4×4 S-box, without heavy dependencies.

Modular inversion of a in mod 2⁶⁴ (Newton/Hensel).

Multithreading: OpenMP or std::thread (optional).

Output: buffered, in blocks of 8–32 MB; format—packed 2 bits/digit.

Code with comments, separate modules: prp.h/.cpp, recover.h/.cpp, regen.h/.cpp, pack.h/.cpp, cli.cpp.

---

CLI/API (minimum)

recover --window in.bin --seeds seeds.txt --n0 0 --out params.json

offset --block y.bin --params params.json --out n.txt

regen --params params.json --start 0 --count 100000000 --out stream.bin --packed

params.json:

{ "seed": 1234, "a": "0x1d3f5b7b9d", "b": "0xcafebabe12345678" }

---

Acceptance tests

1. Synthetic: generate a reference (known seed,a,b), cut 64 blocks, run recover → expect an exact match of seed,a,b.

2. Offset: for the first block from the reference — offset should equal its index.

3. Regen: with recovered parameters generate N blocks and byte-by-byte compare with the reference.

4. Perf: measure time recover (<100 ms) and speed regen (not worse than the specified threshold).

---

Additionally (options)

AVX2 vectorization (SIMD) for PRP.

Packager/unpackager {1..4}↔︎2 bits with streaming buffers.

Performance logs (--bench).

Library API (C-style/C++ class) for embedding.

Here is the link to the correspondence where you can read or ask questions

https://chatgpt.com/share/68b0912d-a1b0-8012-af8f-eb6049798075