Вы наверняка слышали о числах Фибоначчи. Сегодня мы поговорим об их родственниках — числах Люка (Lucas Numbers). Они подчиняются тем же законам, но их ряд начинается с двойки: 2, 1, 3, 4, 7… каждое следующее число равно сумме двух предыдущих.

Своё название эти числа получили в честь французского математика Франсуа Люка, который открыл их в конце XIX века. Он изучал числовые ряды и пришёл к выводу, что числа Фибоначчи — частный случай целого класса последовательностей с уникальными свойствами.

Сейчас мы знаем их как линейные рекуррентные последовательности второго порядка. К этому же семейству относятся числа Пелля, Джейкобсталя и другие. Их общий вид: xₙ = a xₙ₋₁ + b xₙ₋₂, где a и b — константы.

Такие последовательности используются в комбинаторике, в задачах нахождения центра масс, при генерации псевдослучайных чисел, для анализа сложности алгоритмов и при проверке чисел Мерсенна на простоту (тест Люка-Лемера).

В 1990-е годы была разработана криптосистема LUC, основанная на сложности вычисления некоторых элементов последовательности Люка по модулю большого простого числа.

Однако конкурирующие криптосистемы на других математических задачах оказались эффективнее. В итоге LUC не была стандартизирована NIST и осталась в истории.