9. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — С. 79 - 90. — 190 с.
10. Саломаа А. Криптография с открытым ключом / Пер. с англ. И.А. Вихлянцева. — М.: Мир, 1995. — С. 176 - 184. — 318 с.
11. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. - 616 с.
12. Черёмушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2002. — 104 с.
...
Биография Эратосфена Киренского
Эратосфе́н Кире́нский (Ἐρατοσθένης ὁ Κυρηναῖος; 276 год до н. э.—194 год до н. э.) — греческий математик, астроном,географ, филолог и поэт. Сын Эглаоса, уроженец Кирены.
Начальное образование Эратосфен получил в Александрии под руководством своего учёного земляка Каллимаха. Другим учителем Эратосфена в Александрии был философ Лизний. Перебравшись затем в Афины, он так тесно сблизился со школойПлатона, что обыкновенно называл себя платоником. Результатом изучения наук в этих двух центрах была энциклопедическая эрудиция Эратосфена; кроме сочинений по математическим наукам, он писал ещё трактаты «о добре и зле», о комедии и др. Из всех своих сочинений Эратосфен придавал особенное значение литературным и грамматическим, как это можно заключить из того, что он любил называть себя филологом.
В 245 году до н.э.
...
Алгоритм. Понятие и свойства лгоритма. Вида алгоритмов
Слово алгоритм происходит от имени великого среднеазиатского ученого 8–9 вв. Абу Абдуллах Мухаммеда ибн Мусса аль-Хорезми. Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки. Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам.
...
Свойства алгоритмов
Первое свойство дискретность (прерывность, раздельность) - алгоритм должен представлять процесс решения задачи как последовательное выполнение простейших (или ранее определенных) шагов. Каждое действие исполняется только тогда, когда закончилось исполнение предыдущего.
Второе свойство определенность - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Третье свойство результативность (конечность) - алгоритм должен приводить к решению задачи за определенное число шагов.
Четвертое свойство массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, который различается только исходными данными.
...
Виды алгоритмов
Виды алгоритмов как логико-математических средств отображают указанные составляющие человеческой деятельности и тенденции, а сами алгоритмы исходя из цели, изначальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
Словесная или вербальная форма отображения алгоритмов. Чаще всего сначала алгоритм мы описываем словами, пытаемся выразить идею, описывая каждый шаг действий.
Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);
Гибкие алгоритмы это когда механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, и обеспечивает тем самым единственный требуемый или искомый результат, если выполняются те условия данной задачи, для которых разработан данный алгоритм.
Вероятностный алгоритм дает программу решения задачи несколькими возможными способами, которые приводят к вероятному достижению результата.
...
Проверка числа на простоту
Для начала рассмотрим реализацию алгоритма проверки числа на простоту. Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.
...
Последовательный алгоритм "Решето Эратосфена"
Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.
Оптимизация алгоритма Эратосфена
1. Просеивание по нечетным числам
Первую оптимизацию решета предложил сам Эратосфен. Среди четных чисел только одно является простым – это 2. Значит для экономии времени и памяти (в 2 раза!) рациональнее выписывать и высеивать только нечетные числа.
2.
...
Решето Аткина
В математике решето́ А́ткина — быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде ax²+by²). Алгоритм был создан А. О. Л. Аткином и Д. Ю. Бернштайном.
Описание алгоритма:
1. Выписываются все натуральные числа из диапазона от 1 до n.
2. Перебираются все возможные пары чисел x, y, где x<=sqrt(n) и y<=sqrt(n). Т.е. (1,1), (1,2),…, (1,sqrt(n)), (2,1), (2,2),…, (sqrt(n),sqrt(n)).
3. Для каждой пары чисел вычисляются значения следующих трех уравнений:
a) 4*x^2+y^2;
b) 3*x^2+y^2;
c) 3*x^2-y^2, значение вычисляется только при x>y.
4. Для каждого вычисленного значения уравнений вычисляются остатки от деления на 12, причем
a) если остаток равен 1 или 5 для значения первого уравнения;
b) если остаток равен 7 для значения второго уравнения;
с) если остаток равен 11 для значения третьего уравнения.
...
2. Вероятностные алгоритмы
Простые числа, построенные случайным поиском с проверкой вероятностными тестами, используются в криптосистемах RSA, Рабина (и других криптосистемах, основанных на проблеме факторизации).
В 17 веке Ферма доказал утверждение, названное позже малой теоремой Ферма, служащее основой теста Ферма на простоту:
Если n — простое и a не делится на n, то .
Эта проверка для заданного n не требует больших вычислений, однако утверждение, обратное этому, неверно. Так, существуют числа Кармайкла, являющиеся составными, для которых утверждение, приведенное в малой теореме Ферма, выполняется для всех целых чисел взаимнопростых с заданным числом. В 1994 году было показано, что таких чисел бесконечно много. В связи с обнаруженным недостатком теста Ферма, актуальность приобрела задача увеличения достоверности вероятностных тестов. Первым тест, отсеивающий числа Кармайкла как составные, предложил Леманн.
...
Алгоритм частичного деления
Можно рассматривать алгоритм частичного деления как вероятностный тест. Пусть нам надо проверить простоту числа n. Мы проверяем, не делится ли оно на какое-то из чисел 2, 3,…,a. В этом случае a является параметром, а параметрическим множеством будет 2, 3,…,. Когда a пробегает все множество параметров, то тест становится детерминированным. Но в этом случае вряд ли можно говорить об эффективности этого теста, если мы планируем проверять с его помощью очень большие числа.
Перед проверкой данного числа на простоту с помощью малой теоремы Ферма и других методов целесообразно провести базовое исследование на наличие малых простых делителей. Это позволяет существенно сократить время поиска простого числа, в случае, когда нас интересует нахождение хотя бы одного такого числа (эта проблема возникает в кратковременных процедурах шифрования, когда время при кодировании-декодирования для нас играет большую роль, чем время, которое требуется для криптоанализа).
...
Тест Ферма.
Для выбираем , и вычисляем , если результат не равен 1, то n составное, если 1, то n — псевдопростое по основанию a или псевдопростое число Ферма.
Некоторые составные числа являются псевдопростыми по любым основаниям. Это так называемые абсолютно псевдопростые числа, их еще называют числами Кармайкла. Ситуация, когда исследуемое число окажется совершенно псевдопростым, очень мало вероятна, но формально мы не можем ее опускать. Эффективность теста Ферма для слабо псевдопростых чисел.
Исследуем насколько эффективен тест Ферма для чисел, которые не являются числами Кармайкла. Такие числа будем называть слабо псевдопростыми. Обозначим через W множество всех значений параметра a, для которых n проходит тест Ферма на простоту, а именно (2)
Поскольку, по нашему предположению, n не является абсолютно псевдопростым, то , т. е.W не может совпадать со всей мультипликативной группой вычетов, взаимнопростых с n. Легко понять, что W — подгруппа группы , поэтому .
...
Тест Соловея-Штрассена.
Рассмотрим тест, который строится на обобщении малой теоремы Ферма. Используем критерий Эйлера.
Утверждение 1. Для произвольного нечетного n следующие условия эквивалентны: 1. n — простое;
3. для произвольного выполняется сравнение: (3)
Этот критерий позволяет нам использовать следующий вероятностный тест.
1. Выбираем U — коэффициент точности (чем больше этот коэффициент, тем выше точность установки простоты n).
2.
3. Выбираем из упорядоченного по величине массива простых чисел k — непростое число.
4. Проверяем, выполняется ли сравнение (3).
5. Если сравнение не выполняется, то ответ «n — составное».
6. Если сравнение выполняется, то .
7. Если , то переходим к третьему шагу.
8. Если , то ответ: «n — псевдопростое с вероятностью ».
...
Алгоритм Миллера-Рабина
Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году
Алгоритм Рабина Миллера предлагает следующую схему генерации простого числа:
1. Выберите для проверки случайное число p. Вычислите b – число делений p – 1 на 2 (2b – это наибольшая степень числа 2, на которое делится p – 1). Затем вычислите m, такое что p = 1 + 2b * m.
2. Выберите случайное число a
3. Установите j = 0 и вычислить z = a×m mod p.
4. Если z = 1 или z = p – 1, то p проходит проверку и может быть простым числом.
5. Если j > 0 и z = 1, то p не является простым числом.
6. Установите j = j + 1. Если j < b и z p – 1, установите z = 2z mod p и вернитесь к пункту 4. Если z = p – 1, то p проходит проверку и может
быть простым числом.
7. Если j = b и z p – 1, то p не является простым числом.
Число окажется составным через t проверок с вероятностью не большей (1/4)t , где t – это число итераций.
...
Реализация алгоритма Миллера-рабина на псевдокоде
Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины , где n — проверяемое число.
Для данного n находятся такие целое число s и целое нечётное число t, что . Выбирается случайное число a, 1 < a < n. Если a не является свидетелем простоты числа n, то выдаётся ответ «n — составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдаётся ответ «n — вероятно простое», и алгоритм завершается.
Ввод: n > 2, нечётное натуральное число, которое необходимо проверить на простоту;
k — количество раундов.
Вывод: составное, означает, что n является составным числом;
вероятно простое, означает, что n с высокой вероятностью является простым числом.
Представить n − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением n - 1 на 2.
...
Тест Лемана
Вот последовательность действий при проверке простоты числа p:
1. Выбрать случайное число а, причем a
2. Вычислить k= a(p-1) div2mod p;
3. Если k ≠ 1 или k≠ (p-1), то рассматриваемое p не является простым.
4. Если k =1 или k= (p-1), то вероятность того, что p не является простым, не более 50 процентов.
5. Попытку (1) – (4) повторить т раз с различными случайными значениями a.
Если результат вычислений равен 1 или (p–1), но не всегда равен 1, то p является простым числом с вероятностью ошибки 1/2m.
Пример реализации алгоритма теста Лемана
Разберем пример с , тогда для , где , проверяем является ли число делителем числа . Не трудно убедится, что таких нет, тогда переходим к следующему пункту.
Для всех и всех проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие и , что выражение является полным квадратом и равно . Следовательно и . Тогда , удовлетворяет неравенству и является делителем числа .
...
Заключение
В настоящее время простые числа широко применяются в области защиты информации. Прежде всего, это вызвано изобретением криптографии с открытым ключом, которая используется при шифровании информации и в алгоритмах электронной цифровой подписи. На данный момент по стандартам размер простых чисел используемых при формировании цифровой подписи с использованием эллиптических кривых составляет: в соответствии с ГОСТ Р 34.10-2012 не менее 254 бит. Для столь больших чисел вопрос определения простоты числа является крайне сложным. Простые методы, такие, как метод перебора, непригодны для использования из-за того, что требуют чрезвычайно много вычислительных ресурсов и большого времени работы.
Также определение простоты числа необходимо при взломе информации, зашифрованной или подписанной с использованием алгоритма RSA. Для вскрытия такого сообщения необходимо уметь разлагать число на два простых сомножителя, что при больших размерах чисел является нетривиальной задачей.
...
Литература
1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. – М.: Гелиос АРВ, 2002. – 480 с
2. Андреева Е.В. Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
3. Дагене В.А., Григас Г.К., Аугутис А.Ф.100 задач по программированию. – М.: Просвещение, 1993. - 255 с.
4. Дикарев С. С., Рябухо Е. Н., Турка Т. В. Исследование алгоритмов генерации простых чисел // Молодой ученый. — 2015. — №10. — С. 6-9.
5. Дитмар А.Б. Родосская параллель: Жизнь и деятельность Эратосфена. — М.: Мысль, 1965. — 72 с.
6. Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2000.
7. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149 - 160. — 254 с.
8. Кордемский Б.А. Математическая смекалка. — М.: ГИФМЛ, 1958.
9. Нестеренко А. Введение в современную криптографию.
...
1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. – М.: Гелиос АРВ, 2002. – 480 с
2. Андреева Е.В. Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
3. Дагене В.А., Григас Г.К., Аугутис А.Ф.100 задач по программированию. – М.: Просвещение, 1993. - 255 с.
4. Дикарев С. С., Рябухо Е. Н., Турка Т. В. Исследование алгоритмов генерации простых чисел // Молодой ученый. — 2015. — №10. — С. 6-9.
5. Дитмар А.Б. Родосская параллель: Жизнь и деятельность Эратосфена. — М.: Мысль, 1965. — 72 с.
6. Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2000.
7. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149 - 160. — 254 с.
8. Кордемский Б.А. Математическая смекалка. — М.: ГИФМЛ, 1958.
9. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — С. 79 - 90. — 190 с.
10. Саломаа А. Криптография с открытым ключом / Пер. с англ. И.А. Вихлянцева. — М.: Мир, 1995. — С. 176 - 184. — 318 с.
11. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. - 616 с.
12. Черёмушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2002. — 104 с.