Согласно комментариям, пересмотренным оригинальный вопрос: ОП предполагает, что 100 цифр $y_n$ в $\{0,1,2,3,4,5\}$ в их распоряжении, получаются с использованием выражения C(++), эквивалентного ранд ()% 6 с ранд() используя (некриптографический) PRNG на основе линейного конгруэнтного генератора с кодом, эквивалентным
статический беззнаковый длинный x;
интервал рандом (недействительным) {
х = 214013*х+2531011; // или это 22695477*x+1
возврат (целое число)((x>>16)&0x7FFF);
}
Заметь $х$ по крайней мере 32-бит, но только младшие 31 бит имеют значение из-за (х>>16)&0x7FFF и C исполнение беззнаковый длинный умножение с усечением старших разрядов, которые не помещаются в переменную.
Если абстрагироваться от деталей программирования, можно предположить, что $х$ развивается за $x_{n+1}:=a\cdot x_n+b\bmod m$ с $м=2^{31}$ и $(а,б)$ для некоторых фиксированных констант, которые считаются либо $(214013,2531011)$ или же $(22695477,1)$. И ранд() выводит биты 30–16 $х$ Таким образом $y_n:=\lfloor x_n/2^{16}\rfloor\bmod 6$ даны для $n=0$ к $99$ (с затравкой неизвестное целое число $x_{-1}$ в каком-то нематериальном диапазоне, поскольку только $x_{-1}\bmod m$ будет иметь значение; и нам лучше попытаться найти $x_0$ тем не мение).
ОП спрашивает, можно ли подтвердить или опровергнуть эту гипотезу и (если она верна) найти, какая $(а,б)$ используются и предсказывают, что следует в последовательности.
Да, это возможно, с отличной уверенностью. Эффективное состояние рассматриваемых ГПСЧ имеет 31-бит, рассмотрено только два ГПСЧ, они пригодны для целей моделирования, поэтому мы должны быть в состоянии найти их состояние, которое используется с чуть более чем $31+1=32$ бит информации; и мы получаем $100\cdot\log_2(6)\приблизительно258,5$ бит, что даст множество подтверждений.
Самое простое - попробовать оба предполагаемых $(а,б)$, и изучить возможные значения $x_0$. Есть только $2^{31}$, зная $y_0$ позволяет систематически снижать его в $6$. Каждый следующий $y_i$ далее устраняет $5$ кандидаты из $6$. Если ни один кандидат не выживет $y_i$, гипотеза опровергнута. Если совпадение найдено, мы знаем, какое $(а,б)$ мы использовали, и можем вычислить дополнительные $y_i$. Грамотная реализация на скомпилированном языке заняла бы секунду на современном настольном ПК.
Но, может быть, вы хотите сломать это в режиме реального времени с современным процессором стоимостью 0,5 доллара, работающим от батареи стоимостью 0,2 доллара, или застряли на программируемый калькулятор 1970-х годов, или ЭНИАК. Заметьте, что $6$ четно, а делитель $2^{16}$. Следует $y_n\bmod 2$ немного $16$ из $x_n$. Также заметьте, что поскольку $м$ это степень двойки, изменение бита в $x_n$ не распространяется на младшие биты $x_{n+1}$. Если следует, что бит 16 из $x_n$ зависит только от младших 17 бит $x_0$. Мы знаем бит 16 из $x_0$, поэтому нужно проверить не более $2^{16}$ кандидаты на биты 15–0 $x_0$. Затем мы можем найти остальные 14 бит, как указано выше. Что разделяй и властвуй подход позволил бы решать гораздо более крупные параметры, например. переменная Икс типа uin64_t и вернуть х>>33, на современном процессоре.
Интересно, что мы могли бы сделать, если бы $а$, $б$ и/или $м$ были неизвестны.
Примечания к вышеизложенному:
- Он использует доминирующее соглашение в информатике (и криптографии с несколькими исключениями, такими как DES): биты отсчитываются от 0 (младший бит), так что если неотрицательное целое число $v$ представлен в двоичном виде как $к$ биты $b_j$, тогда $v=\сумма b_j$ с $0\le j<k$. В соглашении с обратным порядком байтов бит 0 записывается справа: $6\times7=42$ в десятичном виде $110\times111=101010$ в двоичном формате.
- Компьютерная переменная
Икс по крайней мере 32-битный, но только 31 бит младшего разряда (от 0 до 30) имеет значение и используется в $x_n$, таким образом $0\le x_n<m=2^{31}$. Результат ранд() как минимум 16-бит, но важны только младшие 15 бит (от 0 до 14), а все остальные равны нулю, таким образом $0\le$ранд()$\ле$RAND_MAX$=2^{15}-1$. Если $0\le i<15$ затем немного $j$ выпуска ранд() соответствует биту $j+16$ из Икс. Далее следует бит 0 $y_n$ соответствует биту 16 из $x_n$.
(не по теме) комментарии к текущий код:
- Он пытается использовать ускорение, которое стало возможным благодаря
6 быть даже. я утверждаю, что это нет требуется для достижения времени выполнения в секундах, если
- мы исследовать возможные значения $x_0$, а не семя много шагов назад.
- мы используем это $x_0$ является 31-битным, поэтому мы можем ограничить внешний поиск до [
0, 0x7ffffffff] это $2^{31}$ кандидат $x_0$.
- мы используем то, что знаем $y_0$, таким образом, что $x_0=2^{16}\cdot(6\cdot и+ y_0)+v$ за $0\le u<\lceil2^{15}/6\rceil$ и $0\le v<2^{16}$, который ограничивается примерно $2^{31}/6$ кандидаты на $x_0$.
- оптимизируем тест для проверки кандидата $x_0$ против $y_1$ во внутреннем цикле на $v$.
- Суть по желанию ускорение
6 четно, это сначала найти биты 16…0 $x_0$ соответствие значениям $y_0$ собрал, потом биты 30…17. Код этого не делает! С таким ускорением время выполнения сократилось бы до миллисекунды.
- Нам нужны полные значения $y_n$ собрались (как в неоптимизированном поиске, так и во второй части оптимизированного поиска), но они, кажется, не доступны на входе, что, я думаю, $y_n\bmod2$. Далее, я не понимаю, почему это в двумерном массиве
РЕЗУЛЬТАТ[3][7].
- Когда $x_0$ найдено, если было необходимо найти начальное число (или, скорее, его биты 30–0) за известное количество шагов до этого, это можно сделать эффективно, пройдя назад по LCG, используя $x_{n-1}:=a^{-1}\,(x_n-b)\bmod m$ куда $а^{-1}$ это модульный обратный из $а$ по модулю $м$.
Вот рабочий код без дополнительное ускорение (таким образом, способное работать с нечетным конечным модулем уменьшения $г$ где вопрос 6). Попробуйте онлайн!
#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>
#define A 214013 // для VC; 22695477 для БК
#define B 2531011 // для ВК; 1 для БК
#define R 6 // модуль, в [2, 32768]
// static_assert(A > 0 && A % 8 == 5, "Модуль 8 должен быть 5");
// static_assert(B > 0 && B % 2 == 1, "B mod 2 должен быть равен 1");
// static_assert(R >= 2 && R <= 32768, "R должен быть в [2, 32768]");
// решение по модулю, уменьшенное, когда R является степенью двойки
#define M ((uint32_t)(((R-1)&R)!=0 ? 0x8000 : R)<<16)
// Последовательность yn для VC (a=214013, b=2531011), n=6, seed=1639326023
// Если R является степенью двойки, достаточно ceil(16/log2(R))+1 записей
// В противном случае это записи ceil(31/log2(R)), таким образом, 12 для R=6.
константа int16_t у [] = {
0,5,3,0,4,3,1,0,4,5,4,4,4,5,5,3,0,2,0,5,4,5,0, // 0, 2,5,1,3,5,5,5,
};
// модульная обратная INVA для A по модулю M
#define INVA (IN_A(IN_A(IN_A(IN_A((uint32_t)A))))&(M-1))
#define IN_A(v) (v*(2-v*A))
интервал основной (пустой) {
// решить, начиная с x0, чтобы он соответствовал y0
const uint32_t y0 = y[0], y1 = y[1];
int32_t x0 = (int32_t)(((M >> 16) - y0) / R * R + y0) << 16 | 0xffff;
uint32_t найдено = 0;
printf("генератор: ((int)((x = %"PRIu32" * x + %"PRIu32 ") >> 16) & 0x7fff) %% %u\n",
(uint32_t)A, (uint32_t)B, (без знака)R);
в то время как (x0 >= 0) {
uint32_t x1 = A * (uint32_t)x0 + B;
делать {
// утверждать( (x0 >> 16) % R == y0);
// утверждение( x1 == A * (uint32_t)x0 + B);
если (((x1 >> 16) & 0x7fff) % R == y1) {
uint32_t х = х1;
инт н;
для (n = 2; n < sizeof(y) / sizeof(*y); ++n)
если ((((x = A * x + B) >> 16) & 0x7fff) % R != y[n])
перейти к следующему шагу;
// нашел решение
х = (ИНВА * ((uint32_t)x0 - B)) & (M - 1);
printf("x0 может быть %" PRId32 ", то есть seed=%" PRIu32
"по модулю 0x%" PRIx32 ", что дает:\n", x0, x, M);
// подтверждаем точку зрения, показывая вывод
для (n = 0; n < sizeof (y) / sizeof (* y) + 8; ++ n)
printf(" %d", ((int)((x = A * x + B) >> 16) & 0x7fff) % R);
printf("\n");
++найдено;
}
nxt: x1 -= (uint32_t)A;
} while (((x0--) & 0xffff) != 0);
х0 -= (int32_t)(R - 1) << 16;
}
printf("Найдено %" PRIu32 " решение%s\n", найдено, найдено > 1 ? "s" : "");
вернуть 0;
}
// получаем:
// генератор: ((int)((x = 214013 * x + 2531011) >> 16) & 0x7fff) % 6
// x0 может быть 531633902, то есть seed=1639326023 по модулю 0x80000000, что дает:
// 2 3 4 1 5 1 1 5 4 0 3 2 2 5 5 3 5 5 3 4 0 1 1 4 1 3 3 2 5 4 4
// найдено 1 решение
