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

Канадский эксперт по ГПСЧ критикует власти за использование древних алгоритмов 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 нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Всемирная организация здравоохранения официально признала существование игровой зависимости

В новую версию Международной классификации болезней, которую разрабатывает Всемирная организация здравоохранения, наряду с зависимостью от азартных игр вошла зависимость от онлайн- и офлайн-видеоигр как психическое расстройство. Отдельный идентификатор получили «опасные игры», которые увеличивают риск нанесения физического или психического вреда пациенту ...

[Перевод] Конструкция async/await в JavaScript: сильные стороны, подводные камни и особенности использования

Конструкция async/await появилась в стандарте ES7. Её можно считать замечательным улучшением в сфере асинхронного программирования на JavaScript. Она позволяет писать код, который выглядит как синхронный, но используется для решения асинхронных задач и не блокирует главный поток. Несмотря на то, что ...