Псевдопростые числа Кармайкла

Бюджетное муниципальное общеобразовательное учреждение

«Школа № 31»

Школьная Академия Наук «Созвездие»

СЕКЦИЯ

математики, информатики, физики

Творческая работа

На тему «Псевдопростые числа Кармайкла»

Выполнила ученица 9 класса «А»

Кочергина Яна Андреевна

Руководитель Кряквина Л.Н.

г. Ростов-на-Дону

2015 г.

1. Аннотация

С глубокой древности простые числа привлекали внимание исследователей своими свойствами. Современником и другом Архимеда был Эратосфен. К числу изобретений Эратосфена относится так называемое «решето Эратосфена». Оно позволяет «просеивать» числа и отобрать из них простые. По сути дела, это был первый в мире алгоритм - свод правил, строго следуя которым непременно получишь верный результат.

Эратосфеново решето поработало на исследователей простых чисел - с древнейших времен до наших дней. Разработкой основ теории чисел занимались такие корифеи математики, как Эйлер, Гаусс, Лежандр, Ферма, Чебышев.

До XX века интерес к простым числам носил теоретический, а иногда даже мистический характер. В 1976 году публикуется работа Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии». Данная работа открыла новую область в криптографии, теперь известную как криптография с открытым ключом. Также в ней содержалось описание алгоритма Диффи — Хеллмана, позволявшего сторонам сгенерировать общий секретный ключ, используя только открытый канал. Кроме этого одним из результатов публикации стал значительный рост числа людей, занимающихся криптографией.

Следует отметить, что представленный в работе материал нетривиален и полезен для приложений. Он имеет большую практическую значимость, поскольку большие простые числа используются в области современной криптографии, применение которой стало неотъемлемой частью жизни современного общества. В XXI веке криптография становится все более необходимой во многих сферах жизнедеятельности. Кроме очевидных — собственно, для передачи информации, она используется в сотовой связи, платном цифровом телевидении при подключении к Wi-Fi и на транспорте для защиты билетов от подделок, в банковских операциях, и даже для защиты электронной почты от спама.

Работа посвящена псевдопростым числам Кармайкла и их свойствам. Описаны малая теорема Ферма и критерий Корсельта, которые позволяют отличить составные числа от простых, а также находить псевдопростые числа. Приведены примеры псевдопростых и строго псевдопростых чисел и некоторые алгоритмы их нахождения. Выше указанные методы достаточно наглядны, доступны и легко применимы на практике.

2. Результаты исследования.

Определение.

В теории чисел числом Кармайкла (кармайкловым числом) называется всякое составное число n, которое удовлетворяют сравнению для всех целых b, взаимно простых с n. Другими словами, числом Кармайкла называется составное число n, которое является псевдопростым Ферма по каждому основанию b, взаимно простому с n.

Своё название числа Кармайкла получили в честь известного математика Роберта Кармайкла.

Критерий Корсельта

Теорема (Корсельт, 1899): Составное число n является кармайкловым тогда и только тогда, когда n свободно от квадратов и для каждого простого делителя p числа n число p−1 делит число n−1. (1)

В частности, из теоремы Корсельта следует, что все числа Кармайкла нечётны, так как любое чётное составное число, свободное от квадратов, имеет по крайней мере один нечётный простой делитель, и поэтому из делимости p−1 | n−1 следует, что чётное делит нечётное, что невозможно.

Корсельт был первым, кто заметил это свойство, но он так и не смог найти какие-либо примеры. В 1910 году Кармайкл нашел первое и наименьшее такое число, 561.

Примеры

Последовательность чисел Кармайкла начинается так:

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

Разложения первых нескольких чисел Кармайкла на простые множители таковы:

Cвойства

Кармайкловы числа имеют по меньшей мере три простых положительных множителя.

k
3
4
5
6
7
8
9

Первые кармайкловы числа с четырьмя простыми множителями:

i
1
2
3
4
5
6
7
8
9
10

Интересные факты

• Второе кармайклово число (1105) может быть представлено как сумма двух квадратов большим количеством способов, чем любое меньшее число.

• Третье кармайклово число (1729) является числом Рамануджана — Харди (наименьшее число, представимое в виде суммы двух кубов двумя способами). И, действительно,  . .Меньшего числа, обладающего таким свойством, нет.

Имеется несколько способов выяснить, является ли данное число составным, не разлагая его на множители. Теоретически наиболее привлекателен способ, основанный на теореме Вильсона, которая утверждает, что число p является простым тогда и только тогда, когда выполнено сравнение (p-1)!  -1 (mod p). К сожалению, этот способ практически бесполезен, так как не существует алгоритма, который вычислял бы (p-1)! mod p за разумное время. Других приемлемых критериев простоты числа не существует, поэтому используются теоремы, дающие необходимые условия. Согласно малой теореме Ферма, если N простое, то для любого целого , не делящегося на N, имеет место сравнение ^N-1  1 (mod N) или ^N-1 = 1+kN, где kZ ,

то есть (^N-1 – 1) делится на N. (2)

Если же при каком-то  это сравнение нарушается, то N – составное число. Малая теорема Ферма является лишь необходимым условием простоты числа N. Исключения, т.е. составные числа, удовлетворяющие малой теореме Ферма, редки, однако они существуют. Такие числа называются псевдопростыми.

Для всех простых чисел малая теорема Ферма выполняется. Если же она выполняется для составного числа, то оно является псевдопростым.

Пример № 1.

Например, проверим с помощью малой теоремы Ферма, что число N =13 является простым. Действительно, N – 1 = 12 = 2² * 3;

2¹²  1 (mod 13), так как (2¹² – 1):13 = 315.

Пример № 2.

Число 341 = 11*31 – первое псевдопростое число по основанию 2.

2³⁴⁰ mod 341 =1. Но это число уже не будет псевдопростым по основанию 3, так как 3³⁴⁰  56 (mod 341). Наименьшим псевдопростым числом по основанию 3 будет число 91, так как 3⁹⁰  1 (mod 91), то есть (3⁹⁰ – 1) делится на 91.

Псевдопростые числа по основанию 2 образуют последовательность: 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033…

Псевдопростые числа по основанию 3 – это последовательность: 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821…

В теории чисел числом Кармайкла (кармайкловым числом) называется всякое составное число n, которое удовлетворяют сравнению ^n-1  1 (mod n) для всех целых , взаимно простых с n. Другими словами, числом Кармайкла называется составное число n, которое является псевдопростым Ферма по каждому основанию , взаимно простому с n.

Пример № 3.

Например, число N = 561 = 3*11*17 удовлетворяет сравнению (2) для любого , взаимно простого с N. Так как N-1 = 560 делится на каждое из чисел 2, 10, 16, то с помощью малой теоремы Ферма нетрудно показать, что 561 есть псевдопростое число. 561 – наименьшее из чисел Кармайкла. 1105 – второе кармайклово число. Чисел Кармайкла бесконечно много. Есть кармайкловы числа, имеющие три простых положительных множителя. Разложения первых таких чисел Кармайкла на простые множители таковы:

1105 = 5 * 13 * 17

1729 = 7 * 13 * 19

2465 = 5 * 17 * 29

2821 = 7 * 13 * * 31

6601 = 7 * 23 * 41

8911 = 7 * 19 * 67

Пример № 4

Рассмотрим число 126 217. Представим его в виде произведения простых множителей 126217 = 7 * 13 * 19 * 73. Проверим делимость числа 126216 на числа 6, 12, 18, 72.Действительно, 126216:6 = 21036, 126216:12=10518, 126216:18=7012, 126216:72=1753. Используя критерий Корсельта, делаем вывод, что это число Кармайкла.

3. Выводы

Представленный в работе материал нетривиален и полезен для приложений. Рассмотренные псевдопростые числа Кармайкла находятся современными алгоритмами нахождения простых чисел. Они доступны и позволяют достаточно быстро находить их. Подобные современные методы позволяют решать сложные задачи по нахождению больших простых чисел, что имеет большую практическую значимость в области современной криптографии, применение которой стало неотъемлемой частью жизни современного общества. Числа Кармайкла находятся быстрее современными эффективными алгоритмами. Практическое применение криптографии стало неотъемлемой частью жизни современного общества – ее используют в таких отраслях как электронная коммерция, электронный документооборот (включая цифровые подписи), телекоммуникации и других.

В XXI веке криптография становится все более необходимой во многих сферах жизнедеятельности. Кроме очевидных — собственно, для передачи информации, она используется в сотовой связи, платном цифровом телевидении при подключении к Wi-Fi и на транспорте для защиты билетов от подделок, в банковских операциях, и даже для защиты электронной почты от спама. В связи с этим поиск и рассмотрение алгоритмов, связанных с определением простых чисел остается актуальным.

4. Приложения

Числа Кармайкла

561 = 3 * 11 * 17 | 1.105 = 5 * 13 * 17 | 1.729 = 7 * 13 * 19 | M3(1) 2.465 = 5 * 17 * 29 | 2.821 = 7 * 13 * 31 | (1*6+1)*(2*6+1)*(5*6+1) 6.601 = 7 * 23 * 41 | 8.911 = 7 * 19 * 67 | 10.585 = 5 * 29 * 73 | 15.841 = 7 * 31 * 73 | 29.341 = 13 * 37 * 61 | 41.041 = 7 * 11 * 13 * 41 | 46.657 = 13 * 37 * 97 | 52.633 = 7 * 73 * 103 | 62.745 = 3 * 5 * 47 * 89 | 63.973 = 7 * 13 * 19 * 37 | M4(1) 75.361 = 11 * 13 * 17 * 31 | 101.101 = 7 * 11 * 13 * 101 | 115.921 = 13 * 37 * 241 | 126.217 = 7 * 13 * 19 * 73 | 162.401 = 17 * 41 * 233 | 172.081 = 7 * 13 * 31 * 61 | M3(5) 188.461 = 7 * 13 * 19 * 109 | 252.601 = 41 * 61 * 101 | 278.545 = 5 * 17 * 29 * 113 | 294.409 = 37 * 73 * 109 | M3(6) 314.821 = 13 * 61 * 397 | 334.153 = 19 * 43 * 409 | 340.561 = 13 * 17 * 23 * 67 | 399.001 = 31 * 61 * 211 | 410.041 = 41 * 73 * 137 | 449.065 = 5 * 19 * 29 * 163 | 488.881 = 37 * 73 * 181 | (1*36+1)*(2*36+1)*(5*36+1) 512.461 = 31 * 61 * 271 | 530.881 = 13 * 97 * 421 | 552.721 = 13 * 17 * 41 * 61 | 656.601 = 3 * 11 * 101 * 197 | 658.801 = 11 * 13 * 17 * 271 | 670.033 = 7 * 13 * 37 * 199 | 748.657 = 7 * 13 * 19 * 433 | 825.265 = 5 * 7 * 17 * 19 * 73 | 838.201 = 7 * 13 * 61 * 151 | 852.841 = 11 * 31 * 41 * 61 | 997.633 = 7 * 13 * 19 * 577 | 1.024.651 = 19 * 199 * 271 | 1.033.669 = 7 * 13 * 37 * 307 | 1.050.985 = 5 * 13 * 19 * 23 * 37 | 1.082.809 = 7 * 13 * 73 * 163 | 1.152.271 = 43 * 127 * 211 | 1.193.221 = 31 * 61 * 631 | 1.461.241 = 37 * 73 * 541 | 1.569.457 = 17 * 19 * 43 * 113 | 1.615.681 = 23 * 199 * 353 | 1.773.289 = 7 * 19 * 67 * 199 | M3(11) 1.857.241 = 31 * 181 * 331 | 1.909.001 = 41 * 101 * 461 | 2.100.901 = 11 * 31 * 61 * 101 | 2.113.921 = 19 * 31 * 37 * 97 | 2.433.601 = 17 * 37 * 53 * 73 | 2.455.921 = 13 * 19 * 61 * 163 | 2.508.013 = 53 * 79 * 599 | 2.531.845 = 5 * 19 * 29 * 919 | 2.628.073 = 7 * 37 * 73 * 139 | 2.704.801 = 11 * 29 * 61 * 139 | 3.057.601 = 43 * 211 * 337 | 3.146.221 = 13 * 31 * 37 * 211 | 3.224.065 = 5 * 13 * 193 * 257 | 3.581.761 = 29 * 113 * 1093 | 3.664.585 = 5 * 29 * 127 * 199 | 3.828.001 = 101 * 151 * 251 | 4.335.241 = 53 * 157 * 521 | 4.463.641 = 7 * 13 * 181 * 271 | M3(15) 4.767.841 = 13 * 19 * 97 * 199 | 4.903.921 = 11 * 31 * 73 * 197 | 4.909.177 = 7 * 13 * 73 * 739 | 5.031.181 = 19 * 23 * 29 * 397 | 5.049.001 = 31 * 271 * 601 | 5.148.001 = 41 * 241 * 521 | 5.310.721 = 13 * 37 * 61 * 181 | 5.444.489 = 29 * 197 * 953 | 5.481.451 = 31 * 151 * 1171 | 5.632.705 = 5 * 13 * 193 * 449 | 5.968.873 = 43 * 127 * 1093 | 6.049.681 = 11 * 31 * 113 * 157 | 6.054.985 = 5 * 53 * 73 * 313 | 6.189.121 = 61 * 241 * 421 | 6.313.681 = 11 * 17 * 19 * 1777 | 6.733.693 = 109 * 163 * 379 | 6.840.001 = 7 * 17 * 229 * 251 | 6.868.261 = 43 * 211 * 757 | 7.207.201 = 17 * 353 * 1201 | 7.519.441 = 41 * 241 * 761 | 7.995.169 = 7 * 13 * 103 * 853 | 8.134.561 = 37 * 109 * 2017 | 8.341.201 = 11 * 31 * 61 * 401 | 8.355.841 = 13 * 41 * 61 * 257 | 8.719.309 = 19 * 37 * 79 * 157 | 8.719.921 = 7 * 23 * 41 * 1321 | 8.830.801 = 7 * 19 * 67 * 991 | 8.927.101 = 31 * 37 * 43 * 181 | 9.439.201 = 61 * 271 * 571 | 9.494.101 = 23 * 61 * 67 * 101 | 9.582.145 = 5 * 23 * 97 * 859 | 9.585.541 = 7 * 31 * 163 * 271 | 9.613.297 = 19 * 29 * 73 * 239 | 9.890.881 = 7 * 11 * 13 * 41 * 241 | 10.024.561 = 71 * 271 * 521 | 10.267.951 = 67 * 331 * 463

5. Литература

1. Василенко О.Н., Теоретико-числовые алгоритмы в криптографии. Москва - М.: МЦНМО, 2003, 328 стр.

2. Соловьев Ю.П., Садовничий В.А., Шавгулидзе Е.Т., Белокуров В.В., Эллиптические кривые и современные алгоритмы теории чисел. Москва – Ижевск: Институт компьютерных исследований, 2003, 192 стр.

3. http://www.etudes.ru/utils/swf.php?id=022

4. http://ru.wikipedia.org/wiki/Решето_Эратосфена

5. http://ru.wikipedia.org/wiki/Число_Кармайкла