Створити математичний підбір для великого числа

Потрібно зробити спосіб підбору seed ,а,b без генераторів математично щоб було мілісекунди (максимум до 1хв) на 25млрд 4х значних чисел

Типу 1234 3214 1122 1234 3412 1123 4234 4411...

А також 100% відновлення і максимальна швидкість 

Основний опис  я зробив з  chat gpt 

Технічне завдання (оновлене)

Мета

Реалізувати систему з двох модулів:

1. Підбір (Recovery): знайти seed, a, b за коротким фрагментом ряду.

2. Відтворення: згенерувати ряд довжиною до 25 млрд чисел (1..4).

---

Формат даних

Базовий елемент: цифра з множини {1,2,3,4}.

Упаковка: 8 цифр → 64 біти (по 2 біти на цифру). Це один блок.

Вікно для підбору: W = 32..64 послідовних блоків.

---

МОДУЛЬ A. ПІДБІР (Recovery)

A1. Вхід

y_window: масив із W упакованих блоків (uint64) — послідовні.

seed_candidates: список кандидатів seed (наприклад, [0..4095] або наданий файл зі списком).

n0_local: відомий локальний індекс першого блока у вікні (може бути 0, якщо глобальний не потрібен).

A2. Вихід

seed: знайдений seed.

a: різниця (множник) у модулі 2⁶⁴, непарне.

b: зсув у модулі 2⁶⁴.

status: OK / FAIL (+ діагностика).

A3. Модель (для реалізації)

x_n = (a*n + b) mod 2^64, де a — непарне.

y_n = PRP_seed(x_n), де PRP_seed — інвертована перестановка 64-біт (надаємо реалізацію/інтерфейс).

A4. Алгоритм підбору (без брутфорсу по всьому простору)

Для кожного seed у seed_candidates:

1. Обчислити ключ PRP_seed^{-1}.

2. Інвертувати перші 2 блоки:

x0 = PRP_inv(y0), x1 = PRP_inv(y1), задати a = (x1 - x0) mod 2^64.

(Якщо a парне — швидке відсівання.)

3. Для i=2..W-1:

xi = PRP_inv(yi) і перевірити (xi - x_{i-1}) == a.

Якщо десь не співпало — цей seed відхиляємо.

4. Якщо всі різниці однакові — seed знайдено.

Обчислити b = (x0 - a*n0_local) mod 2^64.

Повернути (seed,a,b) як результат.

> Обчислювальна складність ~O(|seed_candidates| · W). Для |seed_candidates|≤4096 і W≤64 — десятки мс.

A5. Псевдокод

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. Перевірки/валідація

Після знаходження (seed,a,b) перевірити ще 8–16 наступних блоків (якщо є) на константну різницю.

Опціонально: згенерувати 8–16 блоків уперед від n0_local і звірити з наданими.

---

МОДУЛЬ B. OFFSET

B1. Вхід

y_obs: один спостережений блок (uint64).

seed, a, b — отримані з Модуля A.

B2. Вихід

n: глобальний індекс блока (mod 2⁶⁴; якщо потрібний абсолютний в межах файлу — описати діапазон сторінок/блоків).

B3. Формула

x = PRP_inv(y_obs, seed)

ainv = inverse_mod_2_64(a) // a непарне

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

B4. Час

O(1): одна інверсія PRP + одна модульна інверсія (попередньо підготовлена) + кілька 64-біт операцій → мікросекунди.

---

МОДУЛЬ C. ВІДТВОРЕННЯ РЯДУ

C1. Вхід

seed, a, b

start_n, count (діапазон для генерації)

C2. Вихід

Потік блоків y_n у заданому діапазоні (упаковані 64-біт), або розпаковані цифри {1..4} (за опцією).

Підтримка потокового запису у файл у форматі 2 біти/цифру.

C3. Алгоритм

x = a*start_n + b

for i in 0..count-1:

    y = PRP_seed(x)

    output(y)

    x += a

(Розпаковка 8 цифр із 64 бітів — просте добування 2-бітових полів +1.)

---

Вимоги до продуктивності

Підбір (W=64, |seed_candidates|≤4096): < 100 мс на звичайному ноутбуку.

Offset: ≈ мікросекунди.

Генерація 25 млрд цифр (із 2-бітовим пакуванням, 4 потоки): ~2–6 хв на Dell Latitude 5400 (орієнтир).

---

Технічні вимоги до реалізації

Мова: C++17/20, компіляція з -O3 -march=native.

Легка PRP (інвертована): 3–4 раунди Feistel з 4×4 S-box, без важких залежностей.

Модульна інверсія a в mod 2⁶⁴ (Ньютон/Хенсел).

Багатопоточність: OpenMP або std::thread (опціонально).

Вивід: буферизований, блоками 8–32 МБ; формат—упаковані 2 біти/цифру.

Код з коментарями, окремі модулі: prp.h/.cpp, recover.h/.cpp, regen.h/.cpp, pack.h/.cpp, cli.cpp.

---

CLI/API (мінімум)

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" }

---

Приймальні тести

1. Синтетичний: згенерувати еталон (відомі seed,a,b), вирізати 64 блоки, запустити recover → очікуємо точний збіг seed,a,b.

2. Offset: для першого блока з еталону — offset має дорівнювати його індексу.

3. Regen: з відновленими параметрами згенерувати N блоків і побайтно звірити з еталоном.

4. Перф: заміряти час recover (<100 мс) та швидкість regen (не гірше заданого порогу).

---

Додатково (опції)

Векторизація AVX2 (SIMD) для PRP.

Пакувальник/розпакувальник {1..4}↔︎2 біти з потоковими буферами.

Логи продуктивності (--bench).

Бібліотечний API (C-стиль/С++ клас) для вбудовування.

Ось лінк на переписку де ви можете прочитати або задати питання 

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