Stworzyć dobór matematyczny dla dużej liczby

Musisz stworzyć sposób doboru seed, a, b bez generatorów matematycznych, aby czas wynosił milisekundy (maksymalnie do 1 minuty) dla 25 miliardów 4-cyfrowych liczb

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

A także 100% odzyskiwania i maksymalna prędkość

Główny opis zrobiłem z chat gpt

Techniczne zadanie (zaktualizowane)

Cel

Zrealizować system z dwóch modułów:

1. Dobór (Recovery): znaleźć seed, a, b na podstawie krótkiego fragmentu ciągu.

2. Odtwarzanie: wygenerować ciąg o długości do 25 miliardów liczb (1..4).

---

Format danych

Podstawowy element: cyfra z zbioru {1,2,3,4}.

Pakowanie: 8 cyfr → 64 bity (po 2 bity na cyfrę). To jest jeden blok.

Okno doboru: W = 32..64 kolejnych bloków.

---

MODUŁ A. DOBÓR (Recovery)

A1. Wejście

y_window: tablica z W zapakowanych bloków (uint64) — kolejnych.

seed_candidates: lista kandydatów na seed (na przykład, [0..4095] lub dostarczony plik z listą).

n0_local: znany lokalny indeks pierwszego bloku w oknie (może być 0, jeśli globalny nie jest potrzebny).

A2. Wyjście

seed: znaleziony seed.

a: różnica (mnożnik) w module 2⁶⁴, nieparzysta.

b: przesunięcie w module 2⁶⁴.

status: OK / FAIL (+ diagnostyka).

A3. Model (do realizacji)

x_n = (a*n + b) mod 2^64, gdzie a — nieparzysta.

y_n = PRP_seed(x_n), gdzie PRP_seed — odwrócona permutacja 64-bitowa (dostarczamy realizację/interfejs).

A4. Algorytm doboru (bez brute force w całej przestrzeni)

Dla każdego seed w seed_candidates:

1. Obliczyć klucz PRP_seed^{-1}.

2. Odwrócić pierwsze 2 bloki:

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

(Jeśli a jest parzyste — szybkie odrzucenie.)

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

xi = PRP_inv(yi) i sprawdzić (xi - x_{i-1}) == a.

Jeśli gdzieś się nie zgadza — ten seed odrzucamy.

4. Jeśli wszystkie różnice są takie same — seed znaleziony.

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

Zwrócić (seed,a,b) jako wynik.

> Złożoność obliczeniowa ~O(|seed_candidates| · W). Dla |seed_candidates|≤4096 i W≤64 — dziesiątki ms.

A5. Pseudokod

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. Sprawdzanie/walidacja

Po znalezieniu (seed,a,b) sprawdzić jeszcze 8–16 kolejnych bloków (jeśli są) na stałą różnicę.

Opcjonalnie: wygenerować 8–16 bloków z wyprzedzeniem od n0_local i porównać z dostarczonymi.

---

MODUŁ B. OFFSET

B1. Wejście

y_obs: jeden obserwowany blok (uint64).

seed, a, b — uzyskane z Modułu A.

B2. Wyjście

n: globalny indeks bloku (mod 2⁶⁴; jeśli potrzebny absolutny w obrębie pliku — opisać zakres stron/bloków).

B3. Formuła

x = PRP_inv(y_obs, seed)

ainv = inverse_mod_2_64(a) // a nieparzyste

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

B4. Czas

O(1): jedna inwersja PRP + jedna inwersja modularna (wcześniej przygotowana) + kilka operacji 64-bitowych → mikrosekundy.

---

MODUŁ C. ODTWARZANIE CIĄGU

C1. Wejście

seed, a, b

start_n, count (zakres do generacji)

C2. Wyjście

Strumień bloków y_n w zadanym zakresie (zapakowane 64-bity), lub rozpakowane cyfry {1..4} (opcjonalnie).

Wsparcie dla strumieniowego zapisu do pliku w formacie 2 bity/cyfra.

C3. Algorytm

x = a*start_n + b

for i in 0..count-1:

    y = PRP_seed(x)

    output(y)

    x += a

(Rozpakowanie 8 cyfr z 64 bitów — proste wydobycie 2-bitowych pól +1.)

---

Wymagania dotyczące wydajności

Dobór (W=64, |seed_candidates|≤4096): < 100 ms na zwykłym laptopie.

Offset: ≈ mikrosekundy.

Generacja 25 miliardów cyfr (z 2-bitowym pakowaniem, 4 strumienie): ~2–6 min na Dell Latitude 5400 (punkt odniesienia).

---

Wymagania techniczne dotyczące realizacji

Język: C++17/20, kompilacja z -O3 -march=native.

Łatwa PRP (odwrócona): 3–4 rundy Feistel z 4×4 S-box, bez ciężkich zależności.

Inwersja modularna a w mod 2⁶⁴ (Newton/Hensel).

Wielowątkowość: OpenMP lub std::thread (opcjonalnie).

Wyjście: buforowane, blokami 8–32 MB; format—zapakowane 2 bity/cyfra.

Kod z komentarzami, oddzielne moduły: 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" }

---

Testy akceptacyjne

1. Syntetyczny: wygenerować wzorzec (znane seed,a,b), wyciąć 64 bloki, uruchomić recover → oczekujemy dokładnego dopasowania seed,a,b.

2. Offset: dla pierwszego bloku z wzorca — offset powinien odpowiadać jego indeksowi.

3. Regen: z odzyskanymi parametrami wygenerować N bloków i porównać bajt po bajcie z wzorcem.

4. Perf: zmierzyć czas recover (<100 ms) oraz prędkość regen (nie gorsza niż zadany próg).

---

Dodatkowo (opcje)

Wektoryzacja AVX2 (SIMD) dla PRP.

Pakowacz/rozpakowacz {1..4}↔︎2 bity z buforami strumieniowymi.

Dzienniki wydajności (--bench).

Biblioteczny API (styl C/C++ klasa) do wbudowania.

Oto link do rozmowy, gdzie możesz przeczytać lub zadać pytania

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