Алгоритм Блюм — Блюма — Шуба ( англ. Algorithm Blum — Blum — Shub , BBS) — генератор псевдослучайных чисел , предложенный в 1986 году Ленор Блюм , Мануэлем Блюмом и .

BBS выглядит так:

${\displaystyle x_{n+1}=x_{n}^{2}\;{\bmod {\;}}M,}$

где ${\displaystyle M=pq}$ является произведением двух больших простых ${\displaystyle p}$ и ${\displaystyle q}$ . На каждом шаге алгоритма выходные данные получаются из ${\displaystyle x_{n}}$ путём взятия либо бита чётности , либо одного или больше наименее значимых бит ${\displaystyle x_{n}}$ .

Два простых числа, ${\displaystyle p}$ и ${\displaystyle q}$ , должны быть оба сравнимы с 3 по модулю 4 (это гарантирует, что каждый квадратичный вычет имеет один квадратный корень , который также является квадратичным вычетом ) и наибольший общий делитель НОД ${\displaystyle (p-1,q-1)}$ должен быть мал (это увеличивает длину цикла).

Интересной особенностью этого алгоритма является то, что для получения ${\displaystyle x_{n}}$ необязательно вычислять все ${\displaystyle n-1}$ предыдущих чисел, если известно начальное состояние генератора ${\displaystyle x_{0}}$ и числа ${\displaystyle p}$ и ${\displaystyle q}$ . ${\displaystyle n}$ -ное значение может быть вычислено «напрямую» используя формулу:

${\displaystyle x_{n}=x_{0}^{2^{n}{\bmod {\lambda }}(M)}\;{\bmod {\;}}M}$ ,

где ${\displaystyle \lambda }$ — функция Кармайкла : в данном случае ${\displaystyle \lambda (M)=\lambda (pq)=lcm(p-1,q-1)}$ — наименьшее общее кратное чисел ${\displaystyle p-1}$ и ${\displaystyle q-1}$ .

Надёжность

Этот генератор подходит для криптографии , но не для моделирования, потому что он недостаточно быстр. Однако, он имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел. Когда простые числа выбраны осторожно, и ${\displaystyle O(\log \log M)}$ бит каждого ${\displaystyle x_{n}}$ являются выходными данными, тогда предел взятый как ${\displaystyle M}$ быстро растёт, и вычисление выходных бит будет настолько же трудно, как и факторизация ${\displaystyle M}$ .

Если факторизация целых чисел так трудна (как предполагается), тогда BBS с большим ${\displaystyle M}$ будет иметь выход, свободный от любых неслучайных шаблонов, которые могут быть выявлены при достаточном объёме вычислений. Однако, возможно появление быстрого алгоритма для факторизации, и вследствие этого BBS не является гарантированно надёжным.

Примечания

Литература

• Lenore Blum, Manuel Blum, and Michael Shub. «A Simple Unpredictable Pseudo-Random Number Generator», SIAM Journal on Computing , volume 15, pages 364—383, May 1986.
• Lenore Blum, Manuel Blum, and Michael Shub. «Comparison of two pseudo-random number generators», Advances in Cryptology: Proceedings of Crypto '82 . Available as .
• Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999.
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. «About Random Bits», December 2004. Available as and .
• Randomness Recommendations for Security — .