Хабрахабр

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

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

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

  • Шаг 1. Бюро по иммиграции, защите беженцев и гражданству (Immigration, Refugees and Citizenship Canada, IRCC) с помощью Microsoft Excel присваивает каждому заявлению номер по порядку.
  • Шаг 2. Каждому заявлению с порядковым номером присваивается случайный номер от 100 000 до 9 999 999 с помощью функции RANDOMBETWEEN в программе Microsoft Excel.
  • Шаг 3. Таблица Excel сортируется по колонке со случайными номерами от меньшего к большему — и выбирается 10 000 первых записей в качестве победителей лотереи.

Такая схема вызвала критику у некоторых специалистов. Известнейший эксперт по генерации случайных чисел профессор Пьер Л'Экюйе (Pierre L’Ecuyer), из Монреальского университета, автор множества научных работ по ГСЧ, называет этот подход очень плохим: «Это очень старый генератор, его действительно нельзя назвать современным», — говорит он. Исследование профессора Л'Экюйе показало, что генератор псевдослучайных чисел Excel не проходит определённые статистические тесты. Хотя для данного применения его вполне достаточно, но ничего не мешает IRCC просто взять и использовать нормальный современный ГПСЧ.

В случае Excel это начальное значение создается автоматически приложением. Excel использует в качестве ГПСЧ математические алгоритмы с детерминированным результатом, которые зависят от одного начального числа (seed). И нечто подобное случалось ранее, пишет канадская газета. Если знаете одно число на первом шаге, можно вычислить все остальные числа в последовательности. CAD за один вечер в монреальском игорном заведении Casino de Montréal. В 1994 году IT-консультант Даниэль Корриво (Daniel Corriveau) обнаружил такой шаблон в игре Keno — и выиграл 600 тыс. Он трижды подряд угадал 19 из 20 выигрышных чисел.

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

Тогда же в 1994 году профессор Л'Экюйе предложил для детерминированных ГПСЧ структуру $(\mathcal, \mu, f, \mathcal{U}, g)$, где $\mathcal{S}$ — это конечный набор состояний, $\mu$ — вероятностное распределение в пространстве состояний $\mathcal{S}$, используемое для выбора начального состояния $\mathcal{s_{0}}$(seed), $f:\mathcal{S}\rightarrow \mathcal{S}$ — функция перехода, $\mathcal{U}$ — пространство выходных значений, $g:\mathcal{S}\rightarrow \mathcal{U}$.

Выходное значение генератора $u_{i} = g \ (s_{i}) \in \mathcal{U}$; $u_{0}, \ u_{1}, \ u_{2} \ ...$ — последовательность псевдослучайных чисел. Обычно $\mathcal{U} = (0,1)$, а состояние генератора задается рекуррентной формулой $s_{i} = f \ (s_{i-1})$ для $i \geq 1$. Это периодическая последовательность, а «периодом» называется минимальное положительное $j$.

Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Среди ГПСЧ наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, регистр сдвига с обобщённой обратной связью. Его достоинствами являются колоссальный период (219937−1) и равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в пяти измерениях), а также быстрая генерация случайных чисел.

Они есть в интернете, — сказал профессор. Профессор Л'Экюйе считает, что власти поступают очень глупо, используя ГПСЧ из Excel, ведь надёжные криптографические ГПСЧ легко доступны и ничего не стоят: «Криптографические генераторы бесплатны. Это совсем не сложно». — Просто выберите один и всё.

В заявлении по электронной почте пресс-секретарь Шеннон Кер (Shannon Ker) написала: «Мы поддерживаем этот рандомизированный процесс отбора как достаточное средство равных возможностей для всех, кто хочет выразить заинтересованность в спонсировании своих родителей, бабушек и дедушек». Однако государственная комиссия IRCC, кажется, удовлетворена использованием Excel.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть