Рубрика «ГПСЧ»

image

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

Представьте такую ситуацию:

В качестве домашнего задания Хуан и Саша реализуют одинаковый рандомизированный алгоритм на C++, который будет выполняться на одном университетском компьютере и с одним набором данных. Их код почти идентичен и отличается только в генерации случайных чисел. Хуан торопится на свои занятия по музыке, поэтому просто выбрал вихрь Мерсенна. Саша, с другой стороны, потратил несколько лишних часов на исследования. Саша провёл бенчмарки нескольких самых быстрых ГПСЧ, о которых недавно узнал из соцсетей, и выбрал наиболее быстрый. При встрече Саше не терпелось похвастаться, и он спросил Хуана: «Какой ГПСЧ ты использовал?»

«Лично я просто взял вихрь Мерсенна — он встроен в язык и вроде неплохо работает».

«Ха!», — ответил Саша. «Я использовал jsf32. Он намного быстрее, чем старый и медленный вихрь Мерсенна! Моя программа выполняется за 3 минуты 15 секунд!».

«Хм, неплохо, а моя справляется меньше, чем за минуту», — говорит Хуан и пожимает плечами. «Ну ладно, мне пора на концерт. Пойдёшь со мной?»

«Нет», — отвечает Саша. «Мне… эээ… нужно снова взглянуть на свой код».

Эта неловкая вымышленная ситуация не особо и вымышлена; она основана на реальных результатах. Если ваш рандомизированный алгоритм выполняется не так быстро, как хотелось бы, и узким местом похоже является генерация случайных чисел, то, как это ни странно, проблема может быть и не в генераторе случайных чисел!
Читать полностью »

Канадский эксперт по ГПСЧ критикует власти за использование древних алгоритмов Excel для розыгрыша виз - 1

Программа воссоединения семей (Family Reunification Program или Family sponsorship) — одна из трёх основных канадских программ помощи мигрантам. Она позволяет как недавно прибывшим иммигрантам, так и давно устоявшимся канадцам воссоединиться с членами своих семей. В соответствии с положениями об иммиграции и защите беженцев (Immigration and Refugee Protection Regulations), проживающие за рубежом семьи получают финансовую помощь, также как проживающие в Канаде родственники мигранта. На финансовую помощь могут рассчитывать супруги, дети, родители, внуки, усыновлённые дети и т. д.

Проблема в том, что Канада не может сразу предоставить гражданство всем родственникам всех мигрантов. Раньше их ставили в очередь, а рассмотрения заявки приходилось ожидать годами. Чтобы ускорить процесс, либералы предложили проводить лотерею. Так что с 2017 года в Канаде разыгрывается лотерея по типу американской Green Card. Среди примерно 100 000 заявок случайным образом выбирают 10 000. Благодаря официальному ответу на запрос по Закону доступа к информации канадскому изданию The Globe an Mail стали известны некоторые технические детали, как проводится лотерея.
Читать полностью »

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

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

Случайные числа и детерминистичная симуляция
Иногда самый надёжный способ получить случайное число — взять его из справочника. Источник изображения: www.flickr.com/photos/nothingpersonal/337684768/
Читать полностью »

Компания Apple недавно допустила крупную ошибку, забыв удалить лишнюю строчку с оператором безусловного перехода goto посередине функции SSLVerifySignedServerKeyExchange для проверки серверной подписи при установке SSL-соединения. В результате, функция успешно завершала работу, независимо от результата проверки подписи.

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

X Server

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

--- hw/xfree86/common/xf86Init.c
+++ hw/xfree86/common/xf86Init.c
@@ -1677,7 +1677,7 @@
   }
   if (!strcmp(argv[i], "-configure"))
   {
-    if (getuid() != 0 && geteuid == 0) {
+    if (getuid() != 0 && geteuid() == 0) {
        ErrorF("The '-configure' option can only be used by root.n");
        exit(1);
     }

Читать полностью »

Fortuna: генератор случайных чисел для параноиков
Все знают, что лучший генератор случайных чисел — это устройство, оцифровывающее выход с очень чувствительного микрофона, стоящего на солнечном берегу моря где-нибудь в районе диких пляжей Бали.

Если у вас такого устройства нет, то прошу под кат.
Читать полностью »

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.
image
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js