SICP, Ферма Тест Выпуск

Question

Section 1.2.6 из SICP описывает алгоритм Ферма простого тестирования следующим образом (мои слова):

Для того, чтобы проверить, является ли n простое:

1. Выберите случайное число a между 1 и n-1включительно.
2. Если a^n %n = a, то n, вероятно, является простым.

Часть я застрять на тот факт, что мы позволяем a = 1, потому что в этом случае, независимо от выбора n (простое или нет), тест всегда будет проходить.

Answer 1

Вы правы; нет причин выбирать a = 1. При этом статистическое расстояние между равномерным распределением на [1, n-1] и равномерное распределение на [2, n-1] равно O (1/n), поэтому, когда n очень большой (достаточно большой, чтобы вы просто не хотели делать пробное разделение), практическое воздействие очень мало (помните, что это уже вероятностный тест, поэтому большое количество других вариантов a не будет работать ни).

Answer 2

Текст ссылка на самом деле говорит (курсив мой):

Маленькая теорема Ферма: Если п простого числа и любое положительное целое число меньше п, то поднятый до энной власти конгруэнтно по модулю n.

(Два числа называются конгруэнтными по модулю n, если оба они имеют одинаковый остаток при делении на n. Остальная часть числа a при делении на n также упоминается как остальная часть по модулю n или просто как modulo.)

Если n не является простым, то, вообще говоря, большинство чисел a < n не удовлетворяет приведенному выше соотношению. Это приводит к следующему алгоритму для проверки первостепенности: если задано число n, выберите случайное число a < n и вычислите остаток от nn n по модулю n. Если результат не равен a, то n, конечно, не является простым. Если это a, то шансы хорошие, что n является простым. Теперь выберите другое случайное число a и протестируйте его одним и тем же методом. Если он также удовлетворяет уравнению, то мы можем быть еще более уверенными, что n является простым. Попытавшись все больше и больше значений a, мы можем увеличить нашу уверенность в результате. Этот алгоритм известен как тест Ферма.

До сих пор он никогда не говорит, чтобы на самом деле выбрать 1. Это происходит позже. Я думаю, что это ошибка, хотя и не большая. Даже если это верно для заданного значения, вы должны проверить несколько значений.

pseudocode on Wikipedia использует [2, n - 1] как диапазон, например. Вероятно, вы должны использовать этот диапазон на практике (хотя тест Fermat на практике не используется, так как лучше Miller-Rabin).