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

Алгоритм Блум - Блум - Шуба (англ. 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 по ${\displaystyle mod}$ ${\displaystyle 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}$).