Алгоритм был предложен Лемером (англ. Derrick Henry Lehmer, [59, 60]) в 1949 году. Линейный конгруэнтный генератор основывается на вычислении последовательности $x_n, x_{n+1}, \dots$, такой что:
Числа $a, c, m$, $ 0 < a < m, 0 < c < m$, являются параметрами алгоритма.
Пример. Для параметров $a = 2, c = 3, m = 5$ и начального состояния $x_0 = 1$ получаем последовательность: $0, 3, 4, 1, 0, \dots$ Максимальный период ограничен значением $m$. Но максимум периода достигается тогда и только тогда, когда [124]:
Конкретная реализация алгоритма может использовать в качестве выхода либо внутреннее состояние целиком (число $x_n$), либо его отдельные биты. Линейный конгруэнтный генератор является простым (то есть «дешёвым») и быстрым генератором. Результат его работы – статистически качественная псевдослучайная последовательность. Линейный конгруэнтный генератор нашёл широкое применение в качестве стандартной реализации функции для получения псевдослучайных чисел в различных компиляторах и библиотеках времени исполнения (см. таблицу [table:lcg]). Забегая вперёд, предупредим читателя, что его использование в криптографии недопустимо. Зная два последовательных значения выхода генератора ($x_n$ и $x_{n+1}$) и единственный параметр схемы $m$, можно решить систему уравнений и найти $a$ и $c$, чего будет достаточно для нахождения всей дальнейшей (или предыдущей) части последовательности. Параметр $m$, в свою очередь, можно найти перебором, начиная с некоторого $\min(X): X \geq x_i$, где $x_i$ – наблюдаемые элементы последовательности.