Алгоритм Блюм — Блюма — Шуба

Алгоритм Блюм — Блюма — Шуба (англ. 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}$.