Этот метод так же, как и предыдущие,  является вероятностным, но другого типа: простоту числа он устанавливает абсолютно точно, а вот ответ «составное» может быть неверным с некоторой ненулевой вероятностью. В основе метода лежит следующий критерий.

Критерий Люка. Число n является простым, если и только если существует элемент, принадлежащий показателю n – 1 по модулю n.

Доказательство.

Необходимость следует из общеизвестного факта теории чисел – существования первообразных корней по простому модулю.

Достаточность. Если существует элемент, принадлежащий показателю n – 1 по модулю n, то по свойствам показателей выполняется n – 1 | φ(n), что ввиду неравенства φ(n) ≤ n – 1 означает φ(n) = n – 1. Последнее равносильно простоте числа n.

Метод Люка состоит в отыскании элемента, принадлежащего показателю n – 1 по модулю n, т. е. элемента a, удовлетворяющего условиям:

1)      a ^n – 1 = 1 (mod n)      и

2)      a^{( n – 1 ) / p} ≠ 1 (mod n) для всех простых p, делящих n – 1.

Если такой элемент будет найден, то простота числа n будет достоверно установлена; в противном случае утверждаем, но не гарантируем, что n есть число составное. Для проверки условия 2 нужно знать разложение n – 1 на простые множители, и это является, конечно, самым слабым местом алгоритма. Реально метод Люка применим только для чисел специального вида (например, чисел Ферма) или специальным образом (с известным разложением n – 1) сгенерированных чисел.