Тести на простоту, Детальна інформація

Твердження. Нехай n – непарне складене число. Тоді якщо n \xF0B9 9, то кількість його сильних брехунців не більша за \xF06A(n) / 4.

Твердження. Нехай n = p * q – добуток двох простих чисел, d = НСД(p - 1, q - 1). Тоді кількість брехунців числа n дорівнює

sl(n) = r2 * (2 + (4t – 4) / 3),

де d = 2t * r, r – непарне.

Приклад. n = 221 = 13 * 17. d = НСД(12, 16) = 4 = 22 * 1, r = 1, t = 2.

sl(221) = 12 * (2 + (42 – 4) / 3) = 2 + 4 = 6.

Твердження. Нехай n = p * q – добуток двох простих чисел, p = 2 * r + 1, q = 4 * r + 1, r – непарне. Тоді кількість брехунців досягає своєї верхньої межі:

sl(n) = \xF06A(n) / 4

Приклад. При r = 1 маємо: p = 3, q = 5, n = p * q = 15.

sl(15) = \xF06A(n) / 4 = (3 – 1) * (5 – 1) / 4 = 2 * 4 / 4 = 2.

Число 15 дійсно має двох сильних брехунців.

Істині тести

Означення. Тест на простоту називається істиним, якщо в результаті його застосування можна однозначно встановити, чи є задане число простим чи ні.

Решето Ератосфена

Найпростіший метод встановлення як простоти так і складеності числа був відомий ще у давнину і називається він решетом Ератосфена:

. Числа, що залишаться в ряду після операцій викреслення, є простими.

Цей метод є ефективним коли число n невелике (n < 10.000.000.000). При цьому його можна використовувати не тільки для тестування на простоту, а й для пошуку простих чисел у вказаному інтервалі та для розв’язку задачі факторизації.