Тести на простоту
Проблема належності заданого натурального числа до класу простих чи складених чисел є дуже цікавою не тільки в математиці, а й в комп'ютерних науках. Відрізнити просте число від складеного, а також розкласти останнє на прості множники є однією з найважливіших задач арифметики. Пошук великих простих чисел необхідний, наприклад, для забезпечення надійності систем кодування інформації з відкритим ключем. Безпека останніх базується на твердженні, що операція множення двох великих простих чисел є односторонньою функцією.

Для перевірки числа на простоту користуються ймовірносними (Ферма, Соловай – Штрасена, Мілера - Рабіна) та правдивими тестами.

Ймовірностні тести

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

Наведені нижче тести дають наступну інформацію про непарне ціле число n:

· Якщо тест визначає, що n є складним, то це дійсно так.

· Якщо тест визначає, що n є простим, то з ймовірністю, близькою до 1, можна вважати, що число є простим.

Тест Ферма

Тест базується на теоремі Ферма, яка стверджує, що якщо n – просте, то для довільного a, 1 £ a £ n - 1 має місце рівність an-1 º 1 (mod n). Якщо для заданого n знайдеться хоча б одне таке a, що an-1 ¹ 1 (mod n), то n не є простим.

Означення. Нехай n – непарне складене число. Число a, 1 £ a £ n – 1, таке що an-1 ¹ 1 (mod n), називається свідком Ферма (свідком складеності) для n.

Означення. Нехай n – непарне складене число, a – ціле число, 1 £ a £ n – 1. Число n називається псевдопростим за основою a, якщо an-1 º 1 (mod n). Число a називається брехунцем Ферма (брехунцем простоти) для n.

Очевидно, що для довільного складеного n число a = 1 завжди буде брехунцем Ферма, оскільки 1n-1 º 1 (mod n).

Алгоритм

Вхід: непарне ціле число n ³ 3, параметр t ³ 1.

Вихід: визначення, чи є чило n простим.

1. for i ¬ 1 to t do

1.1. Обрати довільне ціле a, 2 £ a £ n – 2.

1.2. Обчислити k ¬ an-1 mod n.

1.3. if k ¹ 1 then return ("складне”).

2. return ("просте”).

Якщо алгоритм дасть відповідь "складне”, то дійсно число є складним. Якщо відповідь буде "просте”, то або n є дійсно простим, або n є складним та має велику кількість брехунців. Чим більше значення параметра t, тим більше тестів буде зроблено і тим більша ймовірність того що n є простим.

Приклад. Розглянемо складене число n = 15 та знайдемо його свідки та брехунці Ферма. Для цього складемо наступну таблицю:

a

1

2

3

4

5

6

7

a14 mod 15

1

4

9

1

10

6

4

a

8

9

10

11

12

13

14

a14 mod 15

4

6

10

1

9

4

1

Свідками Ферма є числа 2, 3, 5, 6, 7, 8, 9, 10, 12, 13.

Брехунцями Ферма є числа 1, 4, 11, 14.

Тест Ферма зручно використовувати для перевірки числа n на складеність, оскільки для більшості натуральних чисел кількість свідків більша за кількість брехунців. Але існують складені числа, які є псевдопростими за довільною основою (взаємно простою з заданим числом). Такі числа називаються числами Кармайкла і найменше з них дорівнює 561 = 3 * 11 * 17.

Означення. Число n називається числом Кармайкла, якщо воно складене та для довільного a, 1 £ a £ n – 1, НСД(a, n) = 1, має місце рівність:

an-1 º 1 (mod n)

Критерій Корсельта. Для того щоб складене число n було числом Кармайкла, необхідно і достатньо виконання двох умов:

· n не ділиться на квадрат простого числа

· n – 1 ділиться на p – 1 для всякого простого дільника p числа n.

Приклад. Простими дільниками числа 561 є 3, 11, 17. При цьому жоден з них не входить до розкладу навіть двічі, а число 560 ділиться на 2, 10 та 16:

560 : 2 = 280, 560 : 10 = 56, 560 : 16 = 35

Твердження. Кожне число Кармайкла є добутком хоча б трьох простих чисел.

Приклад. Числа Кармайкла в межі до 100000:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

Теорема (Чернік, 1939). Якщо p = 6m + 1, q = 12m + 1, r = 18m + 1 є простими числами, то число pqr є числом Кармайкла.

Приклад. Якщо покласти m = 1, то отримаємо p = 7, q = 13, r = 19 – всі прості числа. Отже n = 7 * 13 * 19 = 1729 – число Кармайкла.

Річард Пінч, провівши велику кількість обчислень, виявив, що кількість чисел Кармайкла у натуральному ряді до 1012 дорівнює 8241, до 1013 – 19279, до 1014 – 44706, до 1015 – 105212. З іншого боку декількома авторами наводилася верхня межа для C(n) – кількість чисел Кармайкла від 1 до n. Одна з них (і яка на сьогодні вважається найбільш точною):

C(n) £ n1 – {1 + o(1)} log log log n / log log n

Теорема (Чіполла, 1904). Існує нескінченно багато складених псевдопростих чисел за основою b.

Доведення. Нехай yp = , де p – непарне просте число, НСД(p, b2 – 1) = 1. Тоді yp = – складене непарне ціле число. Враховуючи що b2p – 1 ділиться на , то b2p º 1 (mod yp).

yp – 1 = – 1 = = b2 = b2 .

Оскільки yp – 1 - парне, а також за теоремою Ферма bp-1 º 1 (mod p) (вираз bp-1 - 1 ділиться на p), то yp – 1 º 0 (mod 2p).

Отже = º 1 (mod yp).

Всі числа yp є псевдопростими за основою b.

Приклад. Нехай b = 2, p = 5. Тоді y5 = = 341 = 11 * 31.

Оскільки 2340 º 1 (mod 341), то складене число 341 є псевдопростим за основою 2.

Тест Соловай - Штрасена

Тест Соловай – Штрасена базується на критерії Ейлера: якщо n – просте, то

º (mod n)

для всіх значень a, для яких НСД(a, n) = 1.

Означення. Нехай n – непарне складене число, a – ціле число, 1 £ a £ n – 1.

1. Якщо НСД (a, n) > 1 або ¹ (mod n), то число a називається свідком Ейлера (свідком складеності) для n.

2. Якщо НСД (a, n) = 1 та º (mod n), то число n називається псевдопростим за основою a. Число a називається брехунцем Ейлера (брехунцем простоти) для n.

Алгоритм

Вхід: непарне ціле число n ³ 3, параметр t ³ 1.

Вихід: визначення, чи є чило n простим.

1. for i ¬ 1 to t do

1.1. Обрати довільне ціле a, 2 £ a £ n – 2.

1.2. Обчислити k ¬ a(n-1)/2 mod n.

1.3. if k ¹ 1 and k ¹ n – 1 then return ("складене”).

1.4. Обчислити символ Якобі j ¬ .

1.5. if k ¹ j (mod n) then return ("складене”).

2. return ("просте”).

Тест Мілера - Рабіна

Тест Мілера – Рабіна найбільш часто використовується на практиці та називається сильним тестом на простоту. Він базується на наступному факті:

Твердження. Нехай n – непарне просте число, при чому n – 1 = 2s * r, де r – непарне. Нехай а – таке натуральне число, що НСД(a, n) = 1. Тоді має місце одна із рівностей:

ar º 1 (mod n)

або

º -1 (mod n) для деякого j, 0 £ j £ s - 1

Означення. Нехай n – непарне складене число, n – 1 = 2s * r, де r – непарне, а – натуральне число, 1 £ а £ n - 1.

1. Якщо ar ¹ 1 (mod n) та ¹ -1 (mod n) для всіх j, 0 £ j £ s – 1, тоді а називається сильним свідком (свідком складеності) для n.

2. Якщо ar º 1 (mod n) або º -1 (mod n) для деякого j, 0 £ j £ s – 1, тоді а називається сильним брехунцем для n, а само число n – сильним псевдопростим за основою а. Кількість сильних брехунців числа n будемо позначати через sl(n) (strong liars).

Алгоритм

Вхід: непарне ціле число n ³ 3, параметр t ³ 1.

Вихід: визначення, чи є чило n простим.

1. Записати n – 1 = 2s * r, де r – непарне.

2. for i = 1 to t do

2.1. Обрати довільне ціле a, 2 £ a £ n – 2.

2.2. Обчислити y ¬ ar (mod n).

2.3. if y ¹ 1 and y ¹ n - 1 then

j ¬ 1

while j £ s – 1 and y ¹ n – 1 do

y ¬ y2 mod n

if y = 1 then return ("складене”).

j ¬ j + 1

if y ¹ n – 1 then return ("складене”).

3. return ("просте”).

Твердження. Якщо a – сильний брехунець числа n, то a буде брехунцем Ейлера для числа n.

Приклад. n = 29 – просте число. n – 1 = 28 = 22 * 7. s = 2, r = 7.

Нехай а = 10, НСД(10, 29) = 1.

ar (mod n) º 107 (mod 29) º 17 ¹ 1.

Вираз будемо обчислювати для j = 0, 1 (0 £ j £ 1) поки не отримаємо -1.

j = 0: ar (mod n) º 107 (mod 29) º 17 ¹ -1.

j = 1: a2r (mod n) º (107)2 (mod 29) º -1, 29 може бути простим.

Нехай а = 19, НСД(19, 29) = 1.

ar (mod n) º 197 (mod 29) º 12 ¹ 1.

j = 0: ar (mod n) º 197 (mod 29) º 12 ¹ -1.

j = 1: a2r (mod n) º (197)2 (mod 29) º -1, 29 може бути простим.

Приклад. n = 221 = 13 * 17 – складне число. n – 1 = 220 = 22 * 55. s = 2, r = 55.

Нехай а = 5, НСД(5, 221) = 1.

ar (mod n) º 555 (mod 221) º 112 ¹ 1.

Вираз будемо обчислювати для j = 0, 1 (0 £ j £ 1) поки не отримаємо -1.

j = 0: ar (mod n) º 555 (mod 221) º 112 ¹ -1.

j = 1: a2r (mod n) º (555)2 (mod 221) º 168 ¹ -1, що підтверджує складеність 221.

Число 5 є сильним свідком для 221.

Нехай а = 21, НСД(21, 221) = 1.

ar (mod n) º 2155 (mod 221) º 200 ¹ 1.

j = 0: ar (mod n) º 2155 (mod 221) º 200 ¹ -1.

j = 1: a2r (mod n) º (2155)2 (mod 221) º -1, 221 може бути простим.

Число 21 є сильним брехунцем для 221, а 221 є сильним псевдопростим за основою 21.

Якщо перебрати в якості а всі значення від 1 до 220, то можна побачити, що число 221 має 6 наступних сильних брехунців: 1, 21, 47, 174, 200, 220, а sl(221) = 6.

Твердження. Нехай n – непарне складене число. Тоді якщо n ¹ 9, то кількість його сильних брехунців не більша за j(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) = j(n) / 4

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

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

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

Істині тести

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

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

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

Виписати в ряд числа від 2 до n. Перше число в ряду є простим. Викреслити з ряду числа, які є кратними 2. Далі взяти друге число, що стоїть в ряду і викреслити всі числа, кратні йому. І так далі брати і-те число та викреслювати кратні йому числа поки i < . Числа, що залишаться в ряду після операцій викреслення, є простими.

Цей метод є ефективним коли число n невелике (n < 10.000.000.000). При цьому його можна використовувати не тільки для тестування на простоту, а й для пошуку простих чисел у вказаному інтервалі та для розв'язку задачі факторизації.
Случайные рефераты:
Реферати - Життя і творчість Дмитра Чуба
Реферати - Життя і творчість Олега Ольжича
Реферати - Іван Сенченко
Реферати - Життєвий і творчий шлях Олеся Гончара
Реферати - Життя та творчість Бориса Грінченка
Реферати - Микола Куліш
Реферати
  • Всі реферати
  • Архітектура
  • Астрономія, авіація
  • Аудит
  • Банківська справа
  • Безпека життєдіяльності
  • Біографія, автобіографія
  • Біологія
  • Бухгалтерський облік
  • Військова кафедра
  • Географія
  • Геологія
  • Гроші і кредит
  • Державне регулювання
  • Діловодство
  • Екологія
  • Економіка підприємства
  • Економічна теорія
  • Журналістика
  • Іноземні мови
  • Інформатика, програмування
  • Історія всесвітня
  • Історія України
  • Історія економічних вчень
  • Краєзнавство
  • Кулінарія
  • Культура
  • Література
  • Макроекономіка
  • Маркетинг
  • Математика
  • Медицина та здоров'я
  • Менеджмент
  • Міжнародні відносини
  • Мікроекономіка
  • Мовознавство
  • Педагогіка
  • Підприємництво
  • Політологія
  • Право
  • Релігієзнавство
  • Промисловість
  • Сільське господарство
  • Сочинения на русском
  • Соціологія
  • Литература на русском
  • Страхування
  • Твори
  • Фізика
  • Фізична культура
  • Філософія
  • Фінанси
  • Хімія
  • Цінні папери
  • Логіка
  • Туризм
  • Психологія