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

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