Введение
Генерация случайных чисел окружает нас везде. Любой шаг, дыхание, дуновение ветра, шум кулера, частота мяуканья кошки и т.п. уже может рассматриваться как некая генерация случайности. Так например, на сколько вы контролируете вашу ходьбу? Можете ли вы с точностью до нанометра определить точку опоры? Если не можете, то сама погрешность в неопределённости расстояния начинает становиться для вас генератором случайности.
Тем не менее, генерация случайных чисел на практике является не такой тривиальной задачей, когда начинает существовать ряд ограничений. Из таковых - скорость генерации, стоимость генерации, уровень случайности. В подобных ограничениях возникает масса вопросов.
Скорость генерации. Наверное является самым явным ограничением в применении. Чем быстрее генерируются случайные числа - тем лучше. И действительно, если само событие генерации будет происходить раз в год, то такой генератор будет являться неприменимым на практике. Например, попытаемся взять первое число июля в следующем году (в определённом регионе) и если на это время выпадут осадки - то сгенерируется бит = 1, иначе бит = 0.
Стоимость генерации. Некоторые генераторы могут производить случайную последовательность более быстро, чем другие и иногда за это приходится переплачивать. Так например, мяуканье кошки стоит символические пять рублей (за приобретение) с последующим кормлением (уже зависит от привередливости самой кошки). За счёт этого, вы получаете пушистый генератор случайных чисел, который раз в определённый промежуток времени может мяукать, мурчать, кусать, кушать и т.д. Если записывать каждое действие и ставить в голове некие ставки, что будет происходить дальше, то будут генерироваться случайные числа. Тем не менее, существуют генераторы случайных чисел ещё дороже (и значительно дороже), например, АЭС (атомная электростанция), которая благодаря распаду атомов урана может генерировать очень эффективно случайные числа. Но для этого понадобится +- 22 миллиарда долларов без учёта последующего обслуживания.
Уровень случайности. Является самым сложным ограничением в плане своего описания. Существует множество видов генераторов случайных чисел - ГСЧ (генератор случайных чисел), ГПСЧ (генератора псевдо-случайных чисел), КСГПСЧ (криптографически стойкий генератор псевдо-случайных чисел). Последние два являются генераторами псевдослучайных чисел, иными словами генерируемая ими последовательность лишь выглядит как случайная, но на деле является следствием алгоритма. За счёт алгоритмизации, у псевдослучайных генераторов существует три качества: 1) ГПСЧ и КСГПСЧ имеют периоды генерации при достижении которых вся ранее генерируемая последовательность начнёт повторяться; 2) При необходимости можно повторить всю ранее сгенерированную последовательность, если имеется seed/ключ - начальное значение из которого происходит вся последующая генерация; 3) ГПСЧ и КСГПСЧ работают в разы эффективнее большинства представителей ГСЧ, требуя при этом меньше ресурсов. Тем не менее, если говорить о качестве генераторов, то таковое можно изобразить в неравенстве ГСЧ > КСГПСЧ > ГПСЧ.
Разобрав основные ограничения, настало время разобрать тонкости различия ГСЧ и ГПСЧ.
ГСЧ и ГПСЧ
Как было определено ранее, основным отличием ГСЧ от ГПСЧ (в том числе и от КСГПСЧ) является фактор алгоритмизации. Если существует алгоритм, который способен повторить всю генерируемую последовательность, то это значит, что никакой на деле случайности не существует, существует лишь псевдослучайность. Но так ли всё однозначно на первый взгляд?
Вернёмся к примеру с кошкой. Если вы живёте с кошкой достаточно длительное количество времени, то рано или поздно вы начнёте предугадывать большинство её действий/событий, что-то будет являться фактором/причиной её последующих действий/следствий. Ровно такие же условия будут действовать с ураном и распадом атомов, если нам будут известны все возможные неизвестные переменные - местоположение атомов, частиц, их скорости, столкновения и т.д. Чисто теоретически, если это всё станет возможным, то ГСЧ регрессирует до ГПСЧ, где вместо входных бит, на вход будут подаваться факторы/причины всех последующих действий.
Тем не менее, ГСЧ с истинной случайностью вполне может существовать, но лишь при условии, что не будет существовать причинно-следственных связей. Науке уже известны квантовые явления, которые могут приводить к неопределённости состояния частиц, что может становиться прототипом хороших и качественных ГСЧ. Но эта тема выходит далеко за рамки данной статьи.
Рассмотрев возможный регресс ГСЧ до ГПСЧ, становится логичным последующий вопрос, а возможен ли прогресс ГПСЧ до ГСЧ? Чтобы ответить на данный вопрос, необходимо решить противоречивую задачу, при которой сам алгоритм должен стать неоднозначным. При этом алгоритм не должен задействовать сторонние способы генерации случайных и псевдо-случайных чисел, иначе таковой алгоритм станет нечистым и приведёт лишь к композиции. Иными словами, если рассматривать алгоритм как A, то само A должно стать ГСЧ => A=ГСЧ, а не быть выражением A+ГСЧ.
Неопределённые поведения и состояние гонки
Компьютер представляет собой выражение алгоритма. Действие компьютера - есть действие алгоритма. Со стороны математической модели не может существовать такого алгоритма, который бы стал выражением самой случайности. Тем не менее, компьютер != математическая модель, хоть с одной стороны он действительно детерминирован, но с другой стороны, противоречиво он становится также выражением хаотичности собственных процессов.
Неопределённые поведения (UB - undefined behaviour) алгоритмов - это задачи, на базе которых алгоритм может становиться случайным. Тем не менее, одно неопределённое поведение неравно другому, ровно также одно неопределённое поведение может быть бесполезным для ГСЧ, в то время как другое может становиться его основой.
Так например, существуют неопределённые поведения некоторых языков программирования со стороны стандартов, в которых не указывается единственно верное действие, например язык С и выражение i = i++ + ++i;
. Решением такого неопределённого поведения становится порядок вычисления со стороны самих компиляторов. Данное UB крайне проблематично применять в ГСЧ, т.к. единожды установив компилятор, все дальнейшие действия уже будут определены.
Но существуют также UB, которые очень сложно или невозможно определить каким-либо стандартом или спецификацией из-за собственной своей особенности. К таким неопределённым поведениям относится состояние гонки. Состояние гонки - ситуация, при которой несколько параллельных процессов обращаются одновременно к одной области памяти. Так например, если запущено два параллельных процесса, один из которых будет писать в область памяти число = 0, а другой число = 1, то какое число запишется в эту область памяти? С уверенностью на данный вопрос ответить крайне проблематично, потому что в данном контексте не существует никаких документаций, стандартов, реализаций. Если процессы действительно параллельны и обращаются единовременно к участку памяти, то события равновероятны. На основе данной концепции становится возможным построение ГСЧ. Параллельность можно организовывать разными способами. В моём случае, я буду реализовывать генерацию случайных чисел на двух языках - CUDA C (под GPU) и Golang (под CPU). Разные механизмы языков программирования также могут дать понимание, насколько непредсказуемым остаётся состояние гонки.
Тестирование ГСЧ
При тестировании случайных чисел (случайной последовательности - гаммы) будет использоваться программа rngtest. Но стоит помнить, что таковые тесты способны давать хороший результат только в определении неслучайной последовательности. Тем не менее, доказать, что последовательность случайная - они не могут. Поэтому даже если давать таким тестам псевдослучайную последовательность, то она с большей долей вероятности пройдёт тест, потому как внешние характеристики будут указывать на хорошее распределение.
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main() {
srand(5);
const int n = 4096;
uint8_t gamma[n];
for (int i = 0; i < n; ++i) {
gamma[i] = rand()%256;
}
fwrite(gamma, sizeof(uint8_t), n, stdout);
}
Результат программы rngtest.
rngtest < gamma.txt ✔
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=6.209; avg=6.209; max=6.209)Gibits/s
rngtest: FIPS tests speed: (min=196.634; avg=196.634; max=196.634)Mibits/s
rngtest: Program run time: 9965 microseconds
Тогда встаёт логичный вопрос - для чего тогда вообще нужен этот инструмент, если он говорит о том, что псевдослучайная последовательность проходит тест на случайность? Это нужно для того, чтобы быть уверенным в правильном распределении бит, чтобы разрабатываемый ГСЧ не оказался слишком слабым. У некоторых ГСЧ существуют недостатки подобия малого диапазона генерации, частых повторений одних и тех же блоков и т.д. На это может rngtest поругаться, а нам это и будет нужно.
Также можно воспользоваться онлайн тестером. Он принимает битовое представление гаммы в символьном виде, поэтому необходимо перевести сырые байты в строковые биты. Можно воспользоваться такой программой.
#include <stdio.h>
#include <stdint.h>
void print_bin(uint8_t num);
int main(int argc, char *argv[]) {
if (argc != 2) {
return 1;
}
FILE *input = fopen(argv[1], "rb");
if (input == NULL) {
return 2;
}
int ch;
while((ch=fgetc(input))!= EOF) {
print_bin(ch);
}
fclose(input);
printf("\n");
return 0;
}
void print_bin(uint8_t num) {
for (int bit = 0x80; bit > 0; bit /= 2) {
printf("%d",(num&bit)?1:0);
}
}
GTX 1650 и CUDA C
Первое что делаем - готовим шаблон самой генерации. Здесь всё крайне легко, мы подаём в качестве аргумента указатель на переменную, куда будет записываться случайное число. В качестве случайного числа мы берём ID блока, который смог перезаписать число и "выиграть" в гонке. Константа MODULE_N равна 2. Будем генерировать бинарные числа. Константу можно изменить на другое число, алгоритм также продолжит функционировать. Тем не менее, MODULE_N должен быть степенью двойки, то-есть равен 2 или 4 или 8 или 16 и т.д. Это необходимо для более равномерного распределения итоговых чисел по битовому пространству.
__global__ void rand_uintN(uint8_t *r) {
*r = blockIdx.x % MODULE_N;
}
Функция вызова rand_uintNs
будет выглядить следующим образом. Визуально её можно поделить на две части: 1) генерация сырой гаммы, 2) сжатие сырой гаммы посредством суммирования. Второй пункт приводит к лучшему выравниванию частот встречаемости. Так например, без второго пункта количество нулей часто привышало количество единиц (при MODULE_N=2). Второй пункт приводит к хорошему выравниванию частот встречаемости, в том числе и для разных MODULE_N.
Константа CUDA_BLOCK_N = 4096
. В ходе экспериментов, данная константа привела к положительным результатам в тестировании. Связано это с тем, что чем больше будет задействовано параллельности, тем больше будет конечная неопределённость. Тем не менее, тут всё также упирается во время (чем больше CUDA_BLOCK_N
, тем дольше ждать). Под каждый блок выделяется только один поток. При экспериментах, потоки ведут себя более конкурентным образом, чем параллельным.
void rand_uintNs(uint8_t *gamma, int n) {
int num_count = n * MODULE_N;
uint8_t raw_rand[num_count];
uint8_t *dev_r;
memset(raw_rand, 0, sizeof(raw_rand));
cudaMalloc(&dev_r, sizeof(uint8_t));
for (int i = 0; i < num_count; i++) {
rand_uintN<<<CUDA_BLOCK_N, 1>>>(dev_r);
cudaMemcpy(raw_rand + i, dev_r, sizeof(uint8_t), cudaMemcpyDeviceToHost);
}
cudaFree(dev_r);
for (int i = 0; i < num_count; i += MODULE_N) {
int sum = 0;
for (int j = 0; j < MODULE_2; ++j) {
sum += raw_rand[i + j];
}
gamma[i / MODULE_N] = sum % MODULE_N;
}
}
Вызов всего этого кода происходит так.
int main(int argc, char *argv[]) {
const int n = 1024;
uint1_t gamma[n];
rand_uintNs(gamma, n);
print_uintNs(gamma, n);
print_uintNs_count(gamma, n);
return 0;
}
Остальные функции
Функция print_uintNs
void print_uintNs(uint1_t *gamma, int n) {
for (int i = 0; i < n; ++i) {
printf("%d", gamma[i]);
}
printf("\n");
}
Функция print_uintNs_count
void print_uintNs_count(uint1_t *gamma, int n) {
int count[MODULE_N];
memset(count, 0, sizeof(count));
for (int i = 0; i < n; ++i) {
count[gamma[i]]++;
}
for (int i = 0; i < MODULE_N; ++i) {
printf("[%d] = %d\n", i, count[i]);
}
}
Результаты
1110110011110010100101000110001110110010100111001110101111000111011001101011110001000101100010001110001111001001111011010000001100001111000011110111101111100010100111011110110111101100001101101000011001111100000000111111010000011100111101100000110000101111010111101001111100111011101000111100110001111100011111001010010110101011011000011010110110000111111000010010111000010100101011101000001110010000011001111000101100011010100001000110010011001011010111011010111111001001110101101000010101101101111100100101001111101100101010011011101011001101111111111011110100000001110111000101010100101100111111110011101001011101110010001100111101110001011010000010011001111110111011100110100101110010011100110011100101000010010011100101000010101001100001101101100001101100011001111100110001010001100101011001101010111011101000110100011001101100100001011000000011000011001010101001000101001000110001011011011101111011010000101100101101100100011011000010011011001000101001001001101101100100111011101000000100111000000010111100010110010110
[0] = 498
[1] = 526
0100100010111010100110100001011101101001010111010101011001011110101011110001000001000110000111001000100010000011111001010010011001100101101010101000111011001010100000000100010100101001010110111101010110111011011001110101010110101011110010100010010110101111000010010001000010000010111100000101011100101010010111010010100011111000101100111011100100011100001011101110000110010011000111010000001100101011001000101010011110011101101001110010110010001011101101111000010100011001111010000010111010100111010101110001101111011010010110111001101110101000001101010101110111100111101011111001011101100110110010000110111011100100011110111101110001110110010111100000100100001100000110111111000101110111001111010100101101011101100010010111110111011010001010001010111110111010111000011110111011111110110111001011011010110001101011111011110100100110101001011100010100100010001110110000001001111100010001110000010101000011101011000001110101000010011010001001110011110100010001111000110001000101001100100101111011000011001000111010111001111001
[0] = 503
[1] = 521
1000001110010010100011110010100001100001011010011101111111011101010000100100100111000000011001111011001110000010000101001011001001110010001100000011110101011000100110111000110111111001010100010000010001010010010000110011101111101000110011001001000001011111111110000100011101011010110111001010110010010110000100101110111011100100010101110001110110101101111100011010001000101111011010000001111111101000100111100101111000111010101100000110110000110000011110010110101100001100111011110110111011110111000101000101100100101001111100011100101101110011111000000111010110110100111001101000111001000110000110111001011001110111111001001010111001001001000100011001010110001000100101011000111001001101100011011101011010011010000110100011100001111111010001101010011101000010010100011000100011010010101100110110011011000010101000000010111111011111110101001111010001100111101100100101000100100010000111100001001011111010101010111001000011101011110010100011010011111111000010100101011001100100010010000010110111000001110010000001010010011101
[0] = 519
[1] = 505
0100011110011010110000000100101110001100110110110101001011110000100011011101111101001001000011101000101011001011010000110110110001111111111011000010110010010110011010010110111001001101100001010100010001110110111000101010011110100010111000100001110011001011011110010110010101111100000000011101100011111100011101001111100010111110001110001000000110101111110101101001110000101101000100101011011101001100100000110000011101100111111000010011111010111000101100000111001100101010001101111111100100111011101001111001000000101100011001001100010111001110101010010001101001111100011111010010111100110000101010010011100100100110000000010001001111000110001110011010000101011010011101000110100000111111101011001000111011110101100000100010001100110100101101110011011100110101001111110110111111000010111010110111001100110010010111100000110111010111100010000110101010110101101100010010011011110110100110011100111110110110111101111011100000011010111000111000010010000001010111101000100100001001010001000010101110010011001000011100101111111110
[0] = 504
[1] = 520
0011001010100110111110000000100011101101010010101001000110010100101011101110000100000100000011110100110111101110111011010000000000001010000000011111101011101101001110001110101101111110000111001110101011000011101101011001100101101101001010100100001001100010100010101100001111100000100000111111100000110110110011010110101010001011011111110111000011100001010110101101010010110101011001001000001000101011011110011010100111000010110001000100110000100111010110001010100111111001111010010111100011010111101101101110001001011001101101100000000010010011101101110011111001110100000000000111010111100101110011010100001011010010110011100110000110101100100010001111001001011010100010111010001111101001111000101010010011110001110001001000100011011011101111101101000111010001001101001100011100110100010011010001100011111111011001000001101001101000000100011111011000000101111110001110000110000010110100111100000110110011000111110010100011111000010011000010100001011100110100101010101101010100100010000101011101110011010100001101010000010110
[0] = 528
[1] = 496
Тесты
Программа rngtest смотрит не на символьное представление случайности, а на битовое. Поэтому нужно изменить выдачу результата, иначе rngtest всегда будет говорить о непрохождении теста. Также, чтобы rngtest мог правильно проанализировать данные, ему на вход нужно подать достаточно большую последовательность бит.
Таким образом, меняем константу MODULE_N
с 2 на 256, чтобы генерировались конкретно байты. Далее, нужно поменять константу n
в функции main
с 1024 на 4096, т.к. 1024 будет недостаточно для rngtest. После этого, надо написать функцию, которая сохраняет байты, а не числа в виде строки.
void write_uintNs(uint8_t *gamma, int n) {
fwrite(gamma, sizeof(uint8_t), n, stdout);
}
Запускаем ГСЧ.
$ ./main > gamma.txt
Гамма генерировалась 3 минуты, 10 секунд для CUDA_BLOCK_N=65535
(максимальное количество) и 26 секунд для CUDA_BLOCK_N=4096
(оба значения прошли тест, но если имеется возможность, то лучше использовать конечно консервативный вариант). Относительно неплохое время для ГСЧ, генерирующего в одного 4096 байт. Тем не менее, видеокарта нехило так работала (при 65535), значения в 100%, а ноутбук (на котором все эти вычисления я производил) нагрелся быстро. Ощущение словно биткоин майнил...
И запускаем теперь rngtest, получаем результаты.
$ rngtest < gamma.txt ✔ 3m 10s
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=18.626; avg=18.626; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=110.892; avg=110.892; max=110.892)Mibits/s
rngtest: Program run time: 232 microseconds
Intel CORE I7 и Golang
Теперь настало время потестировать CPU. В данном примере, у нас будет Intel CORE I7 с 12 ядрами. На Golang'e я постарался запрограммировать примерно такой же код с такими же функциями.
Функции генерации случайного числа на основе состояния гонки. Функция randUintN
- эквивалент rand_uintN
в CUDA C, функция runRandUintN
подобие параллельному запуску функции с видеокарты в несколько блоков.
Константа moduleN = 256, blockN = 256. Последнее значение проходит тесты. Такое число было взято по причине полного покрытия диапазона модуля.
func randUintN(r *uint8, i int) {
*r = uint8(i % moduleN)
}
func runRandUintN() uint8 {
x := uint8(0)
for i := 0; i < blockN; i++ {
go randUintN(&x, i)
}
return x
}
Функция randUintNs
- эквивалент функции rand_uintNs
в CUDA C примере.
func randUintNs(n int) []uint8 {
numCount := n * moduleN
gamma := make([]uint8, n)
slice := make([]uint8, numCount)
for i := 0; i < numCount; i++ {
slice[i] = runRandUintN()
}
for i := 0; i < numCount; i += moduleN {
sum := 0
for j := 0; j < moduleN; j++ {
sum += int(slice[i+j])
}
gamma[i/moduleN] = uint8(sum % moduleN)
}
return gamma
}
Основная функция. В ней я устанавливаю максимальное количество процессоров.
func main() {
runtime.GOMAXPROCS(runtime.NumCPU())
const n = 4096
gamma := randUintNs(n)
os.Stdout.Write(gamma)
}
Тесты
Запускаем ГСЧ. Генерация гаммы заняло 1 минуту, 6 секунд.
go run ./main.go > gamma.txt
И запускаем теперь rngtest, получаем результаты.
rngtest < gamma.txt ✔ 1m 8s
rngtest 6.16
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 32768
rngtest: FIPS 140-2 successes: 1
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=0.000; avg=inf; max=0.000)bits/s
rngtest: FIPS tests speed: (min=123.854; avg=123.854; max=123.854)Mibits/s
rngtest: Program run time: 209 microseconds
В Go потребовалось всего blockN=256 (тесты проходили и с меньшим числом), в то время как в CUDA C потребовалось CUDA_BLOCK_N=4096 для прохождения тестов. Связано всё это с тем, что чем меньше загружены ядра/блоки, тем менее эффективно будет исполняться состояние гонки. Поэтому CUDA C требует большее количество блоков, чтобы происходило неопределённое поведение.
Заключение
Тема выдалась достаточно интересная, тем не менее, я не рекомендую применять данные генераторы в чистом виде. Это может быть опасно, потому как ГСЧ на базе состояния гонки, по моим предположениям, хуже ГСЧ считывающего шум кулера, а потому лучше применять вышеописанное UB исключительно как составную деталь пула энтропии.
Также, моя работа не является какой-то основополагающей. Предположения на счёт того, что UB можно применять в генерации случайных чисел также существовали. Таковые работы я привожу в разделе Литература.
Помимо прочего, использование только одного инструмента тестирования на случайность также может быть недостаточным. В идеальном случае лучше всё это тестировать при помощи нескольких инструментов. Но тут уже можете привести в комментариях какие тесты проходят, какие не проходят. Если некоторые тесты не проходят, то могу посоветовать покрутить параметры CUDA_BLOCK_N (C) или blockN (Golang), не забывая также выставить MODULE_N и moduleN = 256 (если того требует инструмент тестирования).
Все исходные коды можно посмотреть тут.
Литература
GPUs and chaos: a new true random number generator https://www.researchgate.net/profile/Je-Sen-Teh/publication/282478044_GPUs_and_chaos_a_new_true_random_number_generator/links/5c05de93a6fdcc315f9ae0f1/GPUs-and-chaos-a-new-true-random-number-generator.pdf
GPUs as high-performance random sources https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/el.2013.4047
Комментарии (20)
kuza2000
00.00.0000 00:00+3Ровно такие же условия будут действовать с ураном и распадом атомов, если нам будут известны все возможные неизвестные переменные - местоположение атомов, частиц, их скорости, столкновения и т.д. Чисто теоретически, если это всё станет возможным, то ГСЧ регрессирует до ГПСЧ
Нет, там истинная случайность, обусловленная законами квантовой физики. Все известные нам данные говорят именно об этом.
Number571 Автор
00.00.0000 00:00Есть какая-нибудь ссылка на квантовые вычисления в процессорах настоящего времени? Я не исключаю, что такого не может быть, но если таковые присутствуют, то скорее всего они генерируют гамму крайне медленно. Иначе это шло бы в противоречие с существованием специализированных QRNG, которые выходят в свет несмотря на новшества процессоров. Нашёл такую статью с Intel'ом https://en.wikipedia.org/wiki/RDRAND, но о каких-либо квантовых вычислениях речи не идёт (сам источник конечно тоже не ахти).
kuza2000
00.00.0000 00:00Не понимаю вопрос. В процессорах настоящего времени никаких квантовых вычислений нет.
Если честно, я в точности не знаю, как устроены ГСЧ Intel, но они наверняка используют тепловой шум. В целом, это очень хороший источник случайности. Шум этот создают движения атомов, если начать закапываться еще глубже, пытаясь их просчитать то можно уперется и в квантовые явления, они есть в этом шуме.
Но, вообще, спектр этого шума может быть неравномерный, еще могут быть различные помехи. Это можно исправить, если использовать маленький кусочек спектра. Но тогда генератор получается медленным. В общем, есть куча проблем. Как-то эти проблемы инженеры Intel решили, наверняка с компромисами. Специализированный процессор сделает все намного лучше и быстрее, поэтому есть QRNG.
Number571 Автор
00.00.0000 00:00+1А извиняюсь, почему-то я подумал вообще про вопрос по поводу процессора. Тут уже я туплю. На счёт распада атомов урана я возможно также погорячился, потому как там также действительно присутствуют гамма-кванты при распаде. Тем не менее, вопрос скорее остаётся в том, что распад испускает гамма-кванты, но является ли сам распад квантовым явлением, полностью непредсказуемым, как это должно происходить со стороны квантовой механики (потому как существуют иные, неквантовые частицы)?
kuza2000
00.00.0000 00:00+1но является ли сам распад квантовым явлением, полностью непредсказуемым, как это должно происходить со стороны квантовой механики
Да, именно так утверждает современная наука.
kuza2000
00.00.0000 00:00+1По крайней мере, спонтанный распад радиоактивных изотопов. В атомном реакторе процессы более сложные, но там же все начинается со спонтанного распада...
puncher
00.00.0000 00:00+1Возникает очень интересный вопрос - исходя из ваших, что чем случайней генерируемое число,тем больше вычислений т.е. энергии надо затратить на генерацию этого числа, то получается при квантовой истинно случайном генерации на кажде истно случайное изменение состояния тратится бесконечное кол-во энергии?! И также вопрос выполнения закона сохранения информации - генератор псевдо случайной поледвательности фактически НЕ генерит новой инфмации, и закон выполняется, но вот квантовый генератор (например на тепловом шуме или распаде) уже другое дело - он привносит в систтему новую иформацю будь то компьютер или наша вселенная?
fk0
00.00.0000 00:00+2Часто используется, не знаю как это называется правильно, но ГСЧ на основе девиаций фазы генератора на основе кольца из нечётного числа инверторов. Три последовательно включенных инвертора, например, превращаются в генератор который работает с максимально возможной частотой, ограниченной скоростью переключения логических элементов. Схема асинхронная, разумеется, внешнего тактирования нет. Разумеется частота и фаза такого генератора постоянно меняется, в зависимости от всех возможных физических условий. И если через регулярные и достаточно большие (много большие периода генератора) интервалы времени снимать показания с выхода одного из инверторов, то это окажутся практически случайные значения. На деле всё сложней и выход такого генератора подмешивается к какому-либо ГПСЧ, например и потом получаются случайные числа считываемые уже программой исполняемой в процессоре, но это уже не существенные детали.
На самом деле такой ГСЧ вовсе не генератор случайных чисел, а скорей генератор хаоса (https://ru.wikipedia.org/wiki/Динамический_хаос). Такой генератор представляет из себя детерминированную систему с очень большим числом состояний и она лишь внешне выглядит случайной, но внутри есть свой очень сложный порядок. Хаотические системы отличаются тем, что малейшее внешнее воздействие, вроде вариаций температуры чипа или окружающих электромагных полей могут кардинально и практически не предсказуемо изменить состояние. Что в общем-то и происходит. Поэтому, условно, такой генератор можно считать генератором случайных чисел.
Генераторы на основе теплового или дробового шума же являются истинными генераторами случайных чисел, т.к. шум обусловлен квантовыми эффектами. Но эти шумы и на описанный выше генератор хаоса, кстати, оказывают значимый эффект. В чистом виде же генератор на основе шума внутри цифрового чипа реализовать сложно по ряду причин.
Есть опасность, что генератору случайных чисел можно навязать состояние внешними электромагнитными полями, флуктуациями на шине питания и т.п. Например, генераторы хаоса способны синхронизировать своё скрытое состояние: https://www.chuacircuits.com/synchronization.php
sci_nov
00.00.0000 00:00Мне кажется, что даже квантовые явления можно рассматривать как псевдо-случайный процесс, потому что там свои "ячейки" и базовые операции.
rafuck
00.00.0000 00:00Пока что все существующие опыты по проверке неравенства Белла говорят о том, что в квантовом мире процессы истинно случайны.
puncher
00.00.0000 00:00+1неравенства Белла про другое - оно о том, что существует дальнодействие и запутанность. Оно даже не доказывает, что дальнодествие быстрее света. Суть в том, что дальнодействие (нелокальность волновой ф-ии) вносит в измерения некоторых параметров на удаленых приборах запутанных частиц дополнительную корреляцию в измеряемые велчины, которая не может быть объяснена в классической механике.
АБСОЛЛЮТНАЯ Случайность квантовых процессов вроде бы постулируется изначально в КМ. И вроде по серьезному это никто не проверял. Так как генерация параметров чем случайней, тем больше надо энергии на вычисления (пусть даже эту энергию тратит Бог!), то абсолютная случайность требует бесконечной энергии - это выглядит как синглярность в черной дыре... но что делать - придется привыкать... если верить в верность КМ.
rafuck
00.00.0000 00:00Простите, пропустил комментарий. Запутанность в этой истории, безусловно, присутствует. Однако случайность vs предопределенность за счет скрытых параметров присутствует тоже. Потому как математика квантовой механики основана на предположении о случайности и предсказывает что совпадение других некоммутирующих (так сказать незапутанных) параметров у запутанных частиц будет с вероятностью 1/2, а теория скрытых параметров - не менее 5/9.
sci_nov
00.00.0000 00:00я не спец в квантовой механике, поэтому хз :) Истинно - видимо потому что там размеры большие и мы не можем угадать закономерности (взломать шифр).
puncher
00.00.0000 00:00да, например в случае разложения на простые числа или популярные элиптические кривые - возможно мы просто не знаем формулы. А возможно и абсолютная случайность (АС). Отличе имхо том, что в абсолютно случайно пследовательности обязтельно содержится целиком Война и Мир, а вот не в абсолютноее можети не быть вовсе. Т.е. АС генерит вннутрь нашей всселенной новую инфрмацию, а ГСПЧ - нет.
longclaps
Это ведь просто набор слов? От перестановки существительных хуже не становится:
Алгоритм представляет собой выражение компьютера.
Выражение представляет собой алгоритм компьютера.
...еще 3 варианта
То есть выясняем статистические свойства гаммы, а перед этим проводим с ней манипуляции типа суммирования по модулю, чтобы эти стат. свойства нормализовать? Логичный вопрос тут - какого черта?
И главное - зачем всё это? Есть потребность в могучем потоке случайных чисел - расскажите какая, интересно же. Производство случайных штука дорогостоящая? Так поясните насколько, вот только не приводите в пример цену атомной электростанции, нерелевантно. Как там обстоит со встроенными в процессоры физическими ГСЧ?
kuza2000
Согласен. Автор преувеличивает сложность получения случайных хисел. По крайней мере в нашем, теплом мире) Тепловой шум есть везде, и его оцифровать несложно.
Number571 Автор
Ну на самом деле хуже становится. Мысль заключается в том, что компьютер - это есть алгоритм в физическом своём представлении. Так что два и три последующих варианта будут являться бессмыслицей.
Да. В качестве примера те же датчики шума кулера, которые могут часто выдавать повторяющиеся блоки, что в чистом виде сводило бы на нет их практическое использование в качестве ГСЧ. Алгоритмы накладываемые на сырую гамму способны улучшить её посредством определённых этапов "сжатия". Также и в описываемом мной ГСЧ, происходит сжатие блоков посредством их суммирования.
Дорогостоящая. Чтобы получить хорошее качества гаммы, становится необходимым объединение сразу нескольких источников энтропии - нескольких ГСЧ. Так например, крайне рискованно использовать один генератор и надеяться на то, что он будет выполнять свою роль всегда и безотказно хорошо. Некоторые датчики могут со временем приходить в негодность, некоторые могут барахлить в зависимости от условий эксплуатации, среды выполнения, некоторые требуют активности самого человека и т.д.
Всё это становится следствием дороговизны качественных ГСЧ, подобия того же распада атомов урана, или квантовых вычислений, или анализа погодных явлений в реальном времени. Качественные ГСЧ чаще всего стабильны и автономны, а их композиция с другими ГСЧ чаще всего излишня.
Потребность в могучем потоке случайных чисел действительно имеется. Сейчас все компьютеры, а точнее операционные системы, имеют внутри себя реализацию/реализации КСГПСЧ, потому что ГСЧ работают крайне медленно для настоящего времени. Проблема необходимости в постоянной генерации случайных чисел заключается в большей мере криптографическими особенностями. Необходимость генерировать случайные Nonce, подписывать передаваемые сообщения, использовать случайные векторы инициализации, генерировать асимметричную пару ключей и т.д. Эти механизмы работают постоянно и автономно, но они требуют всегда хорошего качества случайности. Если бы существовали недорогие ГСЧ, которые генерировали бы гамму быстро и при этом она являлась ещё бы и качественной, то многие КСГПСЧ стали бы просто ненужны. А так, в конечном итоге, мы переводим проблему случайности на псевдослучайные генераторы. В некоторых случаях даже КСГПСЧ могут быть сомнительным решением, допустим при генерации тех же асимметричных ключей. Тем не менее, последнее работает почти везде.
Ровно также как с шумом кулеров или другими физическими "карманными" ГСЧ. Процессор не может взять вне рамок себя какие-то случайные явления кроме состояния регистров в определённый промежуток времени, уровень своей нагруженности и т.д. В этом и состоит сложность, что в конце концов любое случайное явление должно относиться к физическому представлению, а последнее в свою очередь должно пытаться генерировать качественную меру неопределённости. Не исключение и ГСЧ на базе состояния гонки, где таковой, исходя из алгоритма, всё равно перенаправляет основные свои действия на манипуляцию с аппаратурой, а именно с тем как поступит CPU или GPU при параллельной записи в одну область памяти.
fk0
Разные процессорные ядра могут тактироваться от своих, независимых, генераторов. И не синхронизированных. Такой генератор обычно представляет собой умножитель частоты с ФАПЧ (PLL), и соответственно фаза такого генератора может колебаться и зависеть от многих факторов. Как и скорость исполнения инструкций процессорными ядрами может различаться. Даже если формально умножитель частоты абсолютно одинаково настроен для двух ядер и цепь ФАПЧ тактируется одним общим системным генератором. Из этого можно что-то получить.
Впрочем, многоядерная система не обязательна. Достаточно любой системы где есть умножение частоты и доступен любой второй, другой, генератор. Или же просто есть два разных генератора.
Другое дело, что получить может там можно всего лишь единицы бит в секунду. Потому бессмысленно.
fk0
Статья написана с ипользованием ChatGPT, видимо.