Здравствуйте! Есть набор чисел от 0 до 15 включительно, их около 70. Нужен ГПСЧ, который сможет сгенерировать все эти числа используя какой-то seed. В общем, нужен легко обратимый ГПСЧ для этой задачи, чтобы так же ещё мог легко вычислить seed, по которому были сгенерированы данные числа. Что посоветуете? Пишу на php. Сами числа были сгенерированы на perl.
-
1Есть пара вариантов на английском stackoverflow stackoverflow.com/questions/2911432/…– ArnialCommented 7 сент. 2017 в 8:11
-
Посоветую снова: не писать на PHP, потому что быстродействие. И второе: изучайте тот ГПСЧ, который предположительно использовался.– Владимир МартьяновCommented 7 сент. 2017 в 9:36
2 ответа
Восстановление "генератора" по набору его отсчетов сводится к восстановлению трех параметров: алгоритма генерации, внутреннего состояния генератора, алгоритма преобразования сырых отсчетов генератора в имеющиеся данные.
Существует множество генераторов: Type3-генератор, msvcrt-генератор, Mersenne Twister, WinAPI, OpenSSL и так далее. Первые три определенно могут использоваться в PHP. Операционная система, параметры сборки и прочее могут влиять на алгоритм генерации.
Внутреннее состояние зависит от типа генератора. MSVCRT, Type3 используют 32-битное целое для состояния, фактически - seed. Mersenne Twister имеет внутреннее состояние значительно большего размера, оно меняется при получении каждого отсчета. WinAPI определенно умеет подмешивать новые данные в состояние, OpenSSL вроде тоже.
В простейшем случае (Type3, msvcrt, Mersenne Twister) выдает 32-битное целое в качестве результата. Дальше с ним должны проводиться преобразования для получения нужного диапазона значений. Ваши данные похожи на data[i] = random_raw() & 0x0F
или, что тоже самое в данном случае data[i] = random_raw() % 16
Общий метод - выдвигается гипотеза о типе генератора, о преобразовании и потом проверяется для каждого сида. Если тройка генератор-сид-преобразование дает ту же последовательность - можно говорить о том, что эта тройка могла (но не должна была!!!) быть использована для генерации.
В PHP есть встроенный генератор случайных чисел: rand()
Читай/изучай, что в твоей задаче подходит лучше всего.
По поводу seed:
Ты либо задаешь его сам изначально и получаешь воспроизводимую ситуацию или его генерирует система в момент запроса.
Если же тебе надо по числам найти seed, то это не тривиальная математическая задача:
вот в этой статье можно найти постановку такой задачи (раздел Линейный конгруэнтный ГПСЧ(LCPRNG))
если очень надо - то можно написать код для вычисления seed (решения этой задачи соответсвенно)
-
Очень нужно решение задачи! Буду очень благодарен, если кто поможет решить. Commented 7 сент. 2017 в 8:59
-
Вот набор чисел: 6, 8, 5, 2, 9, 10, 10, 7, 13, 1, 15, 3, 5, 3, 10, 8, 9, 9, 8, 9, 14, 2, 13, 10, 14, 0, 15, 1, 13, 10, 9, 12, 3, 13, 1, 13, 9, 0, 11, 12, 3, 12, 14, 5, 12, 14, 15, 10, 10, 3, 2, 6, 5, 14, 8, 1, 15, 4, 0, 6, 0, 12, 0, 8. Помогите написать код, чтобы сгенерировать такие числа через ГПСЧ и вычислить сам сид, который использовался для генерации чисел. Есть так же похожие наборы чисел, длина такая же, нужно вычислять по ним seed, с помощью которого можно сгенерировать эти наборы чисел. Commented 7 сент. 2017 в 9:01
-
В смысле сгенерировать именно такие и именно в таком порядке? Откуда числа? Вы точно уверенны, что это числа из стандартного рандома?– DejsvingCommented 7 сент. 2017 в 9:22
-
Просто если числа с /dev/urandom например - в них может и не быть закономерности. Прям сейчас не готов Вам предложить какой-то код. В выходные, если не горит подумаю.– DejsvingCommented 7 сент. 2017 в 9:29
-
Восстановление сида для стандартного rand() - задача нетривиальная математически, но тривиальная с точки зрения программирования: сидов не более 2^32 и полный перебор проходит за пару часов. Commented 7 сент. 2017 в 9:35