Нахождение семени функции rand () Программирование TI-84

Я провел много исследований по этой функции rand () в TI-84. Он использует алгоритм L'Ecuyer для генерации псевдослучайных чисел. Однако у меня есть интересный случай.

Если функции rand () задано правильное начальное число, она всегда будет генерировать одни и те же числа. Итак, учитывая первое случайное число, которое генерирует функция rand (), можно ли найти начальное значение функции?

Пусть переменная X представляет неизвестное семя.

    X->rand
    rand->D
    Disp D

Вывод:

    0.114820491

Основываясь на этой информации, можно ли вычислить начальное значение функции rand ()? Можете ли вы каким-то образом работать в обратном направлении от алгоритма rand () TI-84?


person Mattkx4    schedule 23.05.2017    source источник
comment
Это утверждает, что заводское начальное значение по умолчанию равно 0. Это не отвечает на ваш вопрос, но у него есть интересная информация, особенно относительно значения 1.   -  person Jim D.    schedule 23.05.2017
comment
Я это понимаю. @JimD. Программа, которую я напечатал, была просто примером для справки. В моей ситуации я пытаюсь взломать программу шифрования. Мне дается первое сгенерированное случайное число, но я не знаю, что это за семя. Есть ли способ выяснить, что было за семя rand () на основе первого генерируемого им случайного числа? Имеет ли смысл мой вопрос или мне следует его перефразировать?   -  person Mattkx4    schedule 23.05.2017
comment
Я не уверен, что знаю достаточно о свойствах генератора случайных чисел. Если вы проведете мысленный эксперимент по запуску этого алгоритма в обратном порядке, я думаю, вы сможете получить множество возможных значений для s1 и s2, которые генерируют конкретный результат. Но если это самый первый результат, то s1 и s2 получаются из начального числа n. Я не знаю, что это сократит количество возможностей ровно до 1. Таким образом, вам может понадобиться больше 1. Обратите внимание, что отображаемое значение может не отображать достаточно, чтобы знать точное 32-битное число с плавающей запятой, что также увеличивает количество возможных вариантов.   -  person Jim D.    schedule 23.05.2017
comment
Это алгоритм, о котором я говорю.   -  person Jim D.    schedule 23.05.2017
comment
Я думаю, что существует только 2 ^ 32-1 эффективно различных начальных значений, поэтому я тщательно искал ваше значение и нашел 4 начальных числа: 41817, 196206349, 392370881 и 588535413. И все они генерируют разные последовательности. Таким образом, похоже, что вы не можете получить уникальное семя из первого значения, но это не значит, что вы не сможете расшифровать сообщение.   -  person Jim D.    schedule 23.05.2017
comment
@JimD. Подожди, воах! 41817 было семенем !!!!! Не могли бы вы уточнить свое решение в ответ на мой вопрос? Итак, я могу принять ваш ответ и, надеюсь, воспроизвести ваш метод в будущем?   -  person Mattkx4    schedule 23.05.2017
comment
Можете ли вы подтвердить, что другие семена тоже работают? Если они это сделают, я почищу код и выложу его.   -  person Jim D.    schedule 23.05.2017
comment
@JimD. Другие семена действительно дали такое же число для первого случайного числа. Однако семена генерировали разные числа для всех чисел после первого, как и ожидалось. Итак, ради этой программы шифрования текст успешно дешифрировал только первое начальное число, но три других начальных числа действительно удовлетворяли условию.   -  person Mattkx4    schedule 23.05.2017
comment
Алгоритм Л'Экуйера. Что ж, у него есть. Что вы имеете в виду?   -  person plasmacel    schedule 23.05.2017
comment
@plasmacel Взгляните на ссылки, размещенные JimD. а также решение, опубликованное ниже. Это алгоритм.   -  person Mattkx4    schedule 23.05.2017


Ответы (2)


Нет, эмпирически невозможно вычислить начальное число только на основе первого сгенерированного случайного числа, поскольку оно не является уникальным. Следующий код выполнит поиск начального числа методом перебора по первому случайному числу:

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <stdlib.h>

int64_t mod1  = 2147483563;
int64_t mod2  = 2147483399;
int64_t mult1 = 40014;
int64_t mult2 = 40692;
int64_t seed1,seed2;

void Seed(int64_t n){
  if(n<0) //Perform an abs
    n = -n;
  if(n==0){
    seed1 = 12345; //Gotta love these seed values!
    seed2 = 67890;
  } else {
    seed1 = (mult1*n)%mod1;
    seed2 = n%mod2;
  }
}

double Generate(){
  double result;
  seed1  = (seed1*mult1)%mod1;
  seed2  = (seed2*mult2)%mod2;
  result = (double)(seed1-seed2)/(double)mod1;
  if(result<0)
    result = result+1;
  return result;
}

int main(int argc, char **argv){
  double x = 0.114820491; // Mattkx4's value
  double r;
  int64_t n;
  int i;

  if (argc > 2) {
    printf("USAGE: %s <1st generated random number>\n", argv[0]);
    return 1;
  } else if (argc == 2) {
    x = atof(argv[1]);
    printf("[Looking for seed generating %.10f]\n", x);
  } else {
    printf("[Looking for seed generating default value of %.10f]\n", x);
  }

  for (n=0; n<= 2147483647; n++) {
    Seed(n);
    r = Generate();
    if (fabs(r-x) < 10e-10) {
      printf("HIT: seed is %ld; G()=%.10f, G()-x=%.12f\n", (long) n, r, r-x);
      for (i=0; i<5; i++) {
        printf("  G() = %.10f\n", Generate());
      }
    }
  }

  return 0;
}

В случае первого случайного числа OP, он дает следующий результат:

$ time ./a.out
[Looking for seed generating default value of 0.1148204910]
HIT: seed is 41817; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.1928098124
  G() = 0.8785866698
  G() = 0.7541802051
  G() = 0.3236799652
  G() = 0.2698472063
HIT: seed is 196206349; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7255189385
  G() = 0.3079613984
  G() = 0.8041985209
  G() = 0.0959226401
  G() = 0.7729820570
HIT: seed is 392370881; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.2582281409
  G() = 0.7373361269
  G() = 0.8542168367
  G() = 0.8681653150
  G() = 0.2761169842
HIT: seed is 588535413; G()=0.1148204909, G()-x=-0.000000000055
  G() = 0.7909372669
  G() = 0.1667108555
  G() = 0.9042350761
  G() = 0.6404079899
  G() = 0.7792519113
HIT: seed is 1869313916; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.9421831845
  G() = 0.2660259263
  G() = 0.9001868100
  G() = 0.3563914254
  G() = 0.3884731955
HIT: seed is 2065478448; G()=0.1148204919, G()-x=0.000000000876
  G() = 0.4748923105
  G() = 0.6954006549
  G() = 0.9502050494
  G() = 0.1286341003
  G() = 0.8916080463

real    1m24.132s
user    1m24.179s
sys 0m0.000s

Отвечая на этот вопрос, я стою на плечах гигантов, используя код, предоставленный @richard в ответ на этот вопрос о переполнении стека. Если есть лучший способ указать авторство, дайте мне знать или просто отредактируйте этот ответ.

person Jim D.    schedule 23.05.2017

Я нашел одно решение, но не считаю его самой эффективной системой. Ниже приводится программа, которую я использовал для исчерпывающего поиска совпадения с рандомным числом.

0→C

Repeat X=0.114820491
Disp C
C→rand
rand→X
C+1→C
End

Disp "Done!"

Эта программа проверяет каждое семя для функции rand, пока не найдет семя, которое дает желаемое случайное число.

Проблема этой системы в том, что существует безумно большое количество возможностей. В этом случае программа должна была быть запущена немногим более 40 000 раз, но в некоторых случаях эта программа должна была быть запущена миллионы и миллионы раз, прежде чем найти подходящее начальное число. Однако это работает, если семя относительно небольшое.

Это не лучшее решение, но это решение.

См. Ответ @ JimD. Для более точного метода.

person Mattkx4    schedule 23.05.2017