3

Здравствуйте! Есть набор чисел от 0 до 15 включительно, их около 70. Нужен ГПСЧ, который сможет сгенерировать все эти числа используя какой-то seed. В общем, нужен легко обратимый ГПСЧ для этой задачи, чтобы так же ещё мог легко вычислить seed, по которому были сгенерированы данные числа. Что посоветуете? Пишу на php. Сами числа были сгенерированы на perl.

2
  • 1
    Есть пара вариантов на английском stackoverflow stackoverflow.com/questions/2911432/…
    – Arnial
    Commented 7 сент. 2017 в 8:11
  • Посоветую снова: не писать на PHP, потому что быстродействие. И второе: изучайте тот ГПСЧ, который предположительно использовался. Commented 7 сент. 2017 в 9:36

2 ответа 2

1

Восстановление "генератора" по набору его отсчетов сводится к восстановлению трех параметров: алгоритма генерации, внутреннего состояния генератора, алгоритма преобразования сырых отсчетов генератора в имеющиеся данные.

Существует множество генераторов: 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

Общий метод - выдвигается гипотеза о типе генератора, о преобразовании и потом проверяется для каждого сида. Если тройка генератор-сид-преобразование дает ту же последовательность - можно говорить о том, что эта тройка могла (но не должна была!!!) быть использована для генерации.

0

В PHP есть встроенный генератор случайных чисел: rand()

Читай/изучай, что в твоей задаче подходит лучше всего.

По поводу seed:

Ты либо задаешь его сам изначально и получаешь воспроизводимую ситуацию или его генерирует система в момент запроса.

Если же тебе надо по числам найти seed, то это не тривиальная математическая задача:

вот в этой статье можно найти постановку такой задачи (раздел Линейный конгруэнтный ГПСЧ(LCPRNG))

если очень надо - то можно написать код для вычисления seed (решения этой задачи соответсвенно)

7
  • Очень нужно решение задачи! Буду очень благодарен, если кто поможет решить.
    – user262975
    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, с помощью которого можно сгенерировать эти наборы чисел.
    – user262975
    Commented 7 сент. 2017 в 9:01
  • В смысле сгенерировать именно такие и именно в таком порядке? Откуда числа? Вы точно уверенны, что это числа из стандартного рандома?
    – Dejsving
    Commented 7 сент. 2017 в 9:22
  • Просто если числа с /dev/urandom например - в них может и не быть закономерности. Прям сейчас не готов Вам предложить какой-то код. В выходные, если не горит подумаю.
    – Dejsving
    Commented 7 сент. 2017 в 9:29
  • Восстановление сида для стандартного rand() - задача нетривиальная математически, но тривиальная с точки зрения программирования: сидов не более 2^32 и полный перебор проходит за пару часов. Commented 7 сент. 2017 в 9:35

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.