Квантовый генератор случайных чисел

Изобретение относится к области вычислительной техники. Технический результат заключается в повышении скорости генерирования последовательности случайных чисел и обеспечении непрерывности выдаваемой последовательности случайных чисел. Технический результат достигается за счет задания тактового сигнала; разбиения непрерывного сигнала, представляющего собой последовательность тактов, состоящую из тактов, содержащих срабатывание средства детектирования, и тактов, в которых отсутствует срабатывание средства детектирования, на блоки одинаковой временной длительности; группировки полученных блоков по содержанию в них срабатываний средства детектирования; преобразования блоков в номера блоков в группе блоков, содержащих одинаковое количество срабатываний; преобразования номера блока в случайную последовательность 0 и 1; и вывода полученной непрерывной случайной последовательности на выход квантового генератора случайных чисел. 1 ил.

 

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

Генераторы случайных чисел, основанные на регистрации отдельных элементарных частиц, например фотонов, привлекают большой интерес со стороны исследователей, так как квантовая природа явлений, заложенная в их основу, не позволяет предсказывать получаемую последовательность чисел даже после сколь угодно точных измерений системы. Квантовые генераторы случайных чисел на данный момент являются наиболее приближенными к идеальным.

Известен квантовый генератор случайных чисел (см. патент РФ RU 2613027, МПК G06F 7/58, G06N 99/00, опубл. 14.03.2017), содержащий источник фотонов, однофотонный детектор, реагирующий на отдельные фотоны, создаваемые источником фотонов, и схему оцифровки и последующей обработки сигнала детектора. В данном квантовом генераторе используется одиночный лавинный фотодетектор, что ограничивает скорость генерации случайных чисел, т.к. главная проблема при фотодетектировании однофотонных сигналов одиночными лавинными фотодетекторами состоит в учете мертвого времени последних, что ограничивает тактовую частоту и темп срабатываний фотодетектора. При этом тактовая частота не может превышать обратное время рассасывания лавины в детекторе.

Кроме того, в данном квантовом генераторе случайных чисел используется метод измерения временных интервалов между событиями регистрации фотонов, излучаемых постоянным источником фотонов, подходящим однофотонным детектором. Интервал времени между последовательными срабатываниями фотодетектора является случайной величиной, которая имеет экспоненциальное вероятностное распределение от длительности интервала. Недостаток данного метода группировки срабатываний фотодетектора заключается в том, что он не позволяет извлечь всю случайность, которая имеется в процессе измерений над квантовой системой при фотодетектировании. Предельное значение случайности - количество случайных бит (0 и 1), которые могут быт получены из последовательности срабатываний фотодетектора данной длины ограничено энтропией Шеннона, которая является функцией от плотности вероятности исходной случайной величины - временных интервалов между последовательными срабатываниями фотодетектора. Как известно, чем более равномерным является распределение исходной случайной величины, тем больше энтропия Шеннона, и тем большее количество случайных бит можно получить. Максимум достигается при равномерной функции распределения исходной случайной величины. А в случае известного квантового генератора случайных чисел функция распределения временных интервалов между последовательными срабатываниями фотодетектора является экспоненциальной от длины интервала, т.е. далека от равномерной функции распределения. Поэтому группировка срабатываний фотодетектора во временные интервалы не позволяет извлечь максимально возможное число случайных бит, содержащихся в физическом процессе квантового фотодетектирования, и как следствие не позволяет достичь больших скоростей генерации случайных чисел.

Т.к. функция распределения срабатываний фотодетектора не является равномерной по времени, то требуется постобработка для получения случайной последовательности 0 и 1. В известном квантовом генераторе случайных чисел используется прямой табличный способ нумерации последовательностей срабатываний фотодетектора при извлечении случайной последовательности 0 и 1. Скорость генерации случайных чисел при таком способе нумерации при постобработке технически ограничена размером таблицы, размер которой растет экспоненциально с длиной блока.

Техническая проблема, на разрешение которой направлено изобретение, заключается в создании квантового генератора случайных чисел, который позволяет получать истинно случайную последовательность 0 и 1 с максимально возможной скоростью.

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

Технический результат достигается за счет того, что квантовый генератор случайных чисел содержит источник фотонов, средство детектирования фотонов, создаваемых источником фотонов, и средство обработки сигнала средства детектирования, причем в качестве средства детектирования фотонов используется матрица лавинных фотодетекторов, в качестве средства обработки сигнала используется программируемая логическая интегральная схема, а источник фотонов выполнен с возможностью работы в непрерывном режиме, при этом средство обработки сигнала выполнено с возможностью без прекращения принятия сигнала от средства детектирования фотонов осуществлять обработку сигнала, включающую этапы: задания тактового сигнала; разбиения непрерывного сигнала, представляющего собой последовательность тактов, состоящую из тактов, содержащих срабатывание средства детектирования, и тактов, в которых отсутствует срабатывание средства детектирования, на блоки одинаковой временной длительности; группировки полученных блоков по содержанию в них срабатываний средства детектирования; преобразования блоков в номера блоков в группе блоков, содержащих одинаковое количество срабатываний; преобразования номера блока в случайную последовательность 0 и 1; и вывода полученной непрерывной случайной последовательности на выход квантового генератора случайных чисел.

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

Сущность изобретения поясняется чертежом, на котором изображена функциональная блок-схема генератора случайных чисел.

Квантовый генератор случайных чисел содержит источник фотонов 1, выполненный с возможностью работы в непрерывном режиме, матрицу лавинных фотодетекторов 2 в качестве средства детектирования фотонов, создаваемых источником фотонов 1, и ПЛИС 3 в качестве средства обработки сигнала средства детектирования 2. ПЛИС 3 выполнено с возможностью без прекращения принятия сигнала от средства детектирования фотонов 2 осуществлять обработку сигнала. Обработка включает в себя следующие этапы: 4 - задание тактового сигнала; 5 - разбиение непрерывного сигнала, представляющего собой последовательность тактов, на блоки одинаковой временной длительности и группировку полученных блоков по содержанию в них срабатываний средства детектирования 2; 6 - преобразование блоков в номера блоков в группе блоков, содержащих одинаковое количество срабатываний; 7 - преобразование номера блока в случайную последовательность 0 и 1, и вывод полученной непрерывной случайной последовательности на выход квантового генератора случайных чисел.

Квантовый генератор случайных чисел работает следующим образом. Источник фотонов 1, например лазер или светодиод, излучает непрерывный свет. Интенсивность его излучения при помощи тока накачки источника фотонов подбирается таким образом, чтобы на отдельный пиксел матрицы лавинных фотодетекторов 2, которая используется в качестве средства детектирования фотонов, поступало квазиоднофотонное излучение со средним числом фотонов за единицу времени меньшим единицы. Сигнал с выхода матрицы лавинных фотодетекторов 2 поступает на ПЛИС 3, где осуществляется его обработка. На выходе матрицы лавинных фотодетекторов 2 формируется случайная последовательность срабатываний фотодетекторов матрицы во временных окнах, заданных генератором тактового сигнала (поз. 4), которая регистрируется как импульсы тока или напряжения на выходе матрицы лавинных фото детекторов 2. Интенсивность излучения источника фотонов 1 подбирается таким образом, чтобы квазиоднофотонный сигнал обеспечивал пуассоновскую статистику срабатываний фотодетекторов матрицы. На этапе 5 непрерывный сигнал, представляющий собой последовательность тактов, состоящую из тактов, содержащих срабатывание детекторов матрицы, и тактов, в которых отсутствует срабатывание детекторов матрицы, на блоки одинаковой временной длительности, например, в n тактов. Количество тактов - временных окон, задается и фиксируется тактовым генератором (поз. 4). Также на этапе 5 осуществляется группировка полученных блоков по содержанию в них срабатываний средства детектирования. На этапе 6 осуществляется нумерация блоков в группе блоков, содержащих одинаковое количество срабатываний, происходящая «на ходу» по мере появления срабатываний фотодетекторов матрицы в каждом обрабатываемом блоке из n тактов. Нумерация происходит при помощи таблицы, в клетках которой стоят биномиальные коэффициенты, которые вычисляются один раз и зависят только от числа тактов n в блоках. Число n является неизменным для данного устройства. Таблица хранится в памяти ПЛИС 3. Далее на этапе 7 номера блоков, полученные при помощи таблицы, преобразуются в случайную последовательность 0 и 1. После этого случайная последовательность 0 и 1 поступает на выход квантового генератора случайных чисел, например, по интерфейсу USB 2.0 или любому другому интерфейсу связи с внешними устройствами.

Работа ПЛИС 3 квантового генератора случайных чисел дополнительно поясняется примером.

Для примера выбрана временная длительность блоков последовательностей в 6 тактов. Выходной последовательности срабатываний фотодетекторов матрицы (j₁, j₂, … j_n) (где j_i - номера временных тактов в блоке, где происходит срабатывание) сопоставляется номер. Пусть в блоке имеется N срабатываний (обозначим срабатывания фотодетекторов «*»). Имеется взаимно однозначное соответствие между последовательностью срабатываний (j₁, j₂, … j_n) и ее номером

Num(j₁, j₂, … j_n) (где номера находятся в интервале

0≤Num(j₁,j₂, … j_n)≤C^k_n-1)

, при m≤n,

n!=n(n-1)(n-2) … 1, m!=m(m-1) … 1, (n-m)!=(n-m)(n-m-1) … 1,

при m>n.

Биномиальные коэффициенты вычисляются заранее и помещаются в таблицу размером n² в память ПЛИС 3. Положение биномиального коэффициента и он сам в таблице определяется его индексами, j - индекс строки, k - индекс столбца, и выбирается «на ходу» по мере появления последовательности срабатываний. При появлении первого срабатывания (k=1) в позиции j₁ выбирается биномиальный коэффициент на пересечении строки с номером j₁-1 и первого столбца таблицы. Номер столбца (k=1) отвечает порядковому номеру срабатывания - первое срабатывание. При появлении второго срабатывания (k=2) берется биномиальный коэффициент в таблице на пересечении j₂-1 строки и второго столбца, и т.д. В итоге получается номер последовательности Num(j₁, j₂, … j_n).

Далее, из номера последовательности, определенного при помощи таблицы, извлекается случайная последовательность 0 и 1. Пусть номер текущей последовательности Num.

Бинарное представление числа последовательностей в группе

Если номер текущей последовательности Num находится в интервале

где i≤i_max,

тогда выходной случайной последовательностью будет k_i младших разрядов бинарного представления Num. Число номеров последовательностей в этом диапазоне равно .

Например, N_k=6=(110)₂ - число элементов в группе. Пусть номер последовательности в группе из 6 элементов (N_k=6=(110)₂) равен Num=3=(011)₂, тогда на выход выдается (11). Например, при Num=5=(101)₂, на выходе будет (01).

После полученная случайная последовательность 0 и 1 поступает на выход квантового генератора случайных чисел.

Квантовый генератор случайных чисел, содержащий источник фотонов, средство детектирования фотонов, создаваемых источником фотонов, и средство обработки сигнала средства детектирования,

отличающийся тем, что

в качестве средства детектирования фотонов используется матрица лавинных фотодетекторов,

в качестве средства обработки сигнала используется программируемая логическая интегральная схема, а

источник фотонов выполнен с возможностью работы в непрерывном режиме,

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

- задания тактового сигнала;

- разбиения непрерывного сигнала, представляющего собой последовательность тактов, состоящую из тактов, содержащих срабатывание средства детектирования, и тактов, в которых отсутствует срабатывание средства детектирования, на блоки одинаковой временной длительности;

- группировки полученных блоков по содержанию в них срабатываний средства детектирования;

- преобразования блоков в номера блоков в группе блоков, содержащих одинаковое количество срабатываний;

- преобразования номера блока в случайную последовательность 0 и 1; и

- вывода полученной непрерывной случайной последовательности на выход квантового генератора случайных чисел.