Создать математический подбор для большого числа

Необходимо реализовать способ подбора seed, a, 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-стиль/C++ класс) для встраивания.

Вот ссылка на переписку, где вы можете прочитать или задать вопросы

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