Таблицы случайных чисел: история и применение

Введение

Печатные списки случайно сгенерированных цифр

Таблицы случайных чисел использовались в статистике для таких задач, как выбор случайных выборок. Это было гораздо эффективнее, чем ручной отбор случайных образцов (с помощью костей, карт и т.п.). В настоящее время таблицы случайных чисел заменены вычислительными генераторами случайных чисел. При тщательной подготовке процессы фильтрации и тестирования устраняют любые заметные смещения или асимметрию из исходных чисел, сгенерированных аппаратно, так что такие таблицы предоставляют наиболее "надежные" случайные числа, доступные обычному пользователю. Любая опубликованная (или иным образом доступная) таблица случайных данных непригодна для криптографических целей, поскольку доступность чисел делает их фактически предсказуемыми, а следовательно, и их влияние на криптосистему также предсказуемо. В отличие от этого, истинно случайные числа, доступные только предполагаемому кодировщику и декодировщику, позволяют буквально невозможно взломать шифрование аналогичного или меньшего объема значимых данных (с использованием простой операции исключающего ИЛИ) в методе, известном как одноразовый блокнот, который часто сталкивается с непреодолимыми проблемами, являющимися препятствиями для правильной реализации этого метода.

История

Таблицы случайных чисел обладают необходимыми свойствами независимо от способа выбора чисел из таблицы: по строкам, столбцам, диагонали или произвольным образом. Первая такая таблица была опубликована Л. Х. К. Типпетом в 1927 году, и с тех пор было разработано множество других подобных таблиц. Первые таблицы генерировались различными способами — одна (Л. Х. К. Типпет) использовала числа, выбранные «случайно» из переписных листов, другая (Р. А. Фишер и Фрэнсис Йейтс) использовала числа, взятые «случайно» из логарифмических таблиц, а в 1939 году М. Г. Кендалл и Б. Бэбингтон Смит опубликовали набор из 100 000 цифр, сгенерированных специализированной машиной совместно с оператором. В середине 1940-х годов корпорация RAND приступила к разработке большой таблицы случайных чисел для использования в методе Монте-Карло и, используя аппаратный генератор случайных чисел, создала «Миллион случайных цифр со 100 000 нормальными отклонениями». В таблице RAND использовалось электронное моделирование колеса рулетки, подключенного к компьютеру, результаты которого затем тщательно фильтровались и проверялись перед использованием для создания таблицы. Таблица RAND стала важным прорывом в области получения случайных чисел, поскольку столь большая и тщательно подготовленная таблица ранее не была доступна (самая большая ранее опубликованная таблица была в десять раз меньше), а также потому, что она была доступна на перфокартах IBM, что позволяло использовать ее в компьютерах. В 1950-х годах аппаратный генератор случайных чисел ERNIE использовался для розыгрыша номеров британских премиальных облигаций. Первое «тестирование» случайных чисел на статистическую случайность было разработано М. Г. Кендаллом и Б. Бэбингтон Смитом в конце 1930-х годов и основывалось на поиске определенных типов вероятностных ожиданий в заданной последовательности. Самый простой тест заключался в проверке приблизительного равенства количества цифр 1, 2, 3 и т. д.; более сложные тесты определяли количество цифр между последовательными нулями и сравнивали их общее количество с ожидаемыми вероятностями. Со временем были разработаны более сложные тесты. Кендалл и Смит также ввели понятие «локальной случайности», при котором заданный набор случайных чисел разбивался на сегменты и тестировался по отдельности. Например, в их наборе из 100 000 чисел две тысячи оказались несколько менее «локально случайными», чем остальные, однако набор в целом успешно проходил все тесты. Кендалл и Смит рекомендовали своим читателям не использовать эти конкретные тысячи цифр по отдельности. Опубликованные таблицы до сих пор находят узкоспециализированное применение, особенно при исполнении экспериментальных музыкальных произведений, требующих их использования, таких как «Vision» (1959) и «Poem» (1960) Ла Монте Янга.

Tables of random numbers have the desired properties no matter how chosen from the table: by row, column, diagonal or irregularly. The first such table was published by L. H. C. Tippett in 1927, and since then a number of other such tables were developed. The first tables were generated through a variety of ways—one (by L. H. C. Tippett) took its numbers "at random" from census registers, another (by R. A. Fisher and Francis Yates) used numbers taken "at random" from logarithm tables, and in 1939 a set of 100,000 digits were published by M. G. Kendall and B. Babington Smith produced by a specialized machine in conjunction with a human operator. In the mid 1940s, the RAND Corporation set about to develop a large table of random numbers for use with the Monte Carlo method, and using a hardware random number generator produced A Million Random Digits with 100,000 Normal Deviates. The RAND table used electronic simulation of a roulette wheel attached to a computer, the results of which were then carefully filtered and tested before being used to generate the table. The RAND table was an important breakthrough in delivering random numbers because such a large and carefully prepared table had never before been available (the largest previously published table was ten times smaller in size), and because it was also available on IBM punched cards, which allowed for its use in computers. In the 1950s, a hardware random number generator named ERNIE was used to draw British premium bond numbers. The first "testing" of random numbers for statistical randomness was developed by M. G. Kendall and B. Babington Smith in the late 1930s, and was based upon looking for certain types of probabilistic expectations in a given sequence. The simplest test looked to make sure that roughly equal numbers of 1s, 2s, 3s, etc. were present; more complicated tests looked for the number of digits between successive 0s and compared the total counts with their expected probabilities. Over the years more complicated tests were developed. Kendall and Smith also created the notion of "local randomness", whereby a given set of random numbers would be broken down and tested in segments. In their set of 100,000 numbers, for example, two of the thousands were somewhat less "locally random" than the rest, but the set as a whole would pass its tests. Kendall and Smith advised their readers not to use those particular thousands by themselves as a consequence. Published tables still have niche uses, particularly in the performance of experimental music pieces that call for them, such as Vision (1959) and Poem (1960) by La Monte Young.