Алгоритм Блюм — Блюма — Шуба (англ. Algorithm Blum — Blum — Shub, BBS) — генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом.
BBS выглядит так:
где является произведением двух больших простых и . На каждом шаге алгоритма выходные данные получаются из путём взятия либо бита чётности, либо одного или больше наименее значимых бит .
Два простых числа, и , должны быть оба сравнимы с 3 по модулю 4 (это гарантирует, что каждый квадратичный вычет имеет один квадратный корень, который также является квадратичным вычетом) и наибольший общий делитель НОД должен быть мал (это увеличивает длину цикла).
Интересной особенностью этого алгоритма является то, что для получения необязательно вычислять все предыдущих чисел, если известно начальное состояние генератора и числа и . -ное значение может быть вычислено «напрямую» используя формулу:
где — функция Кармайкла: в данном случае — наименьшее общее кратное чисел и .
Этот генератор подходит для криптографии, но не для моделирования, потому что он недостаточно быстр. Однако, он имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел. Когда простые числа выбраны осторожно, и бит каждого являются выходными данными, тогда предел взятый как быстро растёт, и вычисление выходных бит будет настолько же трудно, как и факторизация .
Если факторизация целых чисел так трудна (как предполагается), тогда BBS с большим будет иметь выход, свободный от любых неслучайных шаблонов, которые могут быть выявлены при достаточном объёме вычислений. Однако, возможно появление быстрого алгоритма для факторизации, и вследствие этого BBS не является гарантированно надёжным.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .