Размещено на http://www.allbest.ru

Оглавление

• Введение
• Глава 1. Временные оценки сложности арифметических операций
• Глава 2. Делимость и алгоритм Евклида
• Глава 3. Сравнения
• Глава 4. Проверка чисел на простоту
• Глава 5. Практика
• Использованная литература


Введение

Выделение простых чисел является сложной задачей математики. Ученые на протяжении многих веков пытаются найти закон по которому можно определить n-ое простое число. Первый, кто занимался этой задачей, был великий математик древности Эратосфен.

Первую известную нам таблицу простых чисел составил итальянский математик Пьетро Антонио Катальди в 1603 г. Она захватывала все простые числа от 2 до 743.

В 1770 г. Немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102000 и не делящихся на 2, 3, 5. Первым значительным успехом в определении простоты целых чисел явились теорема Вильсона и теорема Ферма, которые являются центральными в данной проблеме по сей день.

В данной курсовой работе будут представлены основные алгоритмы проверки чисел на простоту. Цель данной курсовой работы познакомить читателя с основными алгоритмами проверки чисел на простоту. Почему же так важно знать простое число или нет? Поиск больших простых чисел имеет важное значение для математики и не только. Например, в криптографии большие простые числа используются в алгоритмах шифрования с открытым ключом. простой число алгоритм делимость

Работа состоит из пяти глав. Первые три главы напомнят читателю основные понятия из алгебры и теории чисел. В первой главе вводится и анализируется понятие одной из основных характеристик работы алгоритмов - время исполнения алгоритма. Во второй главе определяется понятие делимости целых чисел, приводятся свойства делимости, определяется понятие НОД и НОК для двух целых чисел и приводится алгоритм Евклида. В третье главе представлены основные свойства и теоремы из теории сравнений. Здесь же доказываются теоремы основные критерии простоты целых чисел: теорема Вильсона, теорема Ферма. В четвёртой главе приведены основные алгоритмы проверки на простоту: пробное деление, решето Эратосфена, тест на основе малой теоремы ферма. Пятая глава является практической частью работы. В первом пункте этой главы решены практические задачи. Во втором пункте реализованы алгоритмы на языке С++.



Глава 1. Временные оценки сложности арифметических операций

Числа в разных базах. Разложение неотрицательного целого числа n по основанию (базе) b представляет собой обозначение для ), где - цифры, т.е. символы целых чисел от 0 до . Эта запись означает, что . Если цифра первого разряда отлична от нуля, то число n называют k-разрядным b-ичным числом. Любое целое число от до является k-разрядным по основанию b. Дробные числа также можно разлагать по любому основанию, т.е. представлять в виде

.

При b > 10 принято использовать буквы для выражения цифр, больших девяти.

Пример:

· .

· При будем использовать буквы латинского алфавита А-Z для записи цифр 0-25 соответственно. Тогда , тогда как

Число разрядов. Как было упомянуто выше, целое число, удовлетворяющее неравенствам , имеет k разрядов по основанию b. С помощью логарифмов это можно переписать в следующем виде (здесь и всюду далее log понимается как натуральный логарифм log_e.

Двоичные операции. Одним из понятий, используемых для сравнения эффективности алгоритмов, является их сложность. Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом.

Предположим, что оба числа имеют длину в k бит. Если запись одного из чисел короче, ее можно дополнить нужным числом нулей слева. Однократное выполнение побитового сложения называется двоичной (битовой) операцией. Сложение двух k - разрядных двоичных чисел требует k двоичных операций. Время, которое расходует компьютер на решение задачи, по сути дела пропорционально числу двоичных операций. Конечно, константа пропорциональности -- число наносекунд, расходуемых на одну двоичную операцию, -- зависит от вида компьютера. (Сказанное является упрощением, так как это время может зависеть также от «технических» факторов, например, времени доступа к памяти.) Когда мы говорим об оценке времени работы, подразумевается оценка числа двоичных операций. В этих оценках мы будем пренебрегать временем, расходуемым на запись информации или на логические шаги, отличные от двоичных операций. На практике основное время занимает выполнение именно двоичных операций. Теперь рассмотрим процесс умножения k-разрядного двоичного числа на l-разрядное двоичное число.

Предположим, что мы пользуемся обычным способом умножения k - разрядного двоичного числа n- и l-разрядного двоичного числа m. Мы получаем самое большее l строк (каждый нулевой бит числа m уменьшает это количество на единицу), где каждая строка содержит копию числа n, сдвинутую влево на некоторое расстояние, т.е. копию, дополненную нулями справа. Пусть имеется строк. Поскольку мы ограничиваемся двоичными операциями, мы не можем сложить все строки сразу. Правильнее будет двигаться от второй строки к -й, складывая каждую строку с накопившейся суммой верхних строк. На каждом этапе сначала отмечаем, как далеко сдвинуто влево число n в рассматриваемой строке. Сносим вниз крайние правые разряды накопленной суммы верхних строк, а остальную часть записи накопленной суммы складываем с числом n, что требует k двоичных операций. Это описание показывает, что задача умножения может быть разложена на - 1 сложений, по k двоичных операций каждое. Так как , то получаем простую оценку Time (умножение k - разрядного и l - разрядного двоичных чисел) < . Здесь и далее Time(A) обозначает число двоичных операций, необходимых для выполнения процедуры А.

Наконец, наша оценка может быть выражена в терминах n и m, если вспомнить приведенную выше формулу для числа разрядов, из которой следует, что

и .

O большое. Пусть f(n) и g(n) -- функции положительного целочисленного аргумента, принимающие положительные (не обязательно целые) значения при всех n. Скажем, что f(n) = 0(g(n)) (или просто f = O(g) ), если существует такая константа С, что f(n) всегда меньше С * g(n).

Определение. Пусть -- две функции, определенные на наборах из r положительных целых чисел. Предположим, что существуют такие константы В и С, что, когда все n_j больше В, обе функции положительны . В этом случае говорим, что функция f ограничена функцией g, и пишем f = О(g).



Глава 2. Делимость и алгоритм Евклида

Делители и делимость. Для данных целых чисел a и b говорят, что a делит b (или b делится на a), и используют обозначение a|b, если существует такое целое число d, что b = a*d. В этом случае a называют делителем b. Любое целое число b > 1 имеет, по крайней мере, два положительных делителя: 1 и b. Под собственным делителем b подразумевают любой положительный делитель, не равный b, а под нетривиальным делителем b -- любой положительный делитель, не равный 1 или b. Простым числом, по определению, является целое число, большее 1, которое не имеет положительных делителей, отличных от 1 и самого себя; число называется составным, если оно имеет, по крайней мере, один нетривиальный делитель. Следующие свойства делимости выводятся непосредственно из определений:

1. Если a|b и с -- любое целое число, то а|(b*c)

2. Если a|b и b|c, то a|c

3. Если a|b и a|c, то a|(b ± с)

4. Если простое число p делит a*b, то p|a или p|b.

5. Если m|a и n|a и если m и n не имеют общих делителей, больших 1, то m*n|a.

Наибольший общий делитель. Наибольшим общим делителем двух данных целых чисел a и b (обозначаемым НОД (a, b) или просто (a, b)) , не равных одновременно нулю, называется наибольшее целое число d, делящее и a, и b. Приведенное выше определение эквивалентно следующему: НОД (a, b) -- это единственное положительное число, которое делит a и b и делится на любой другой их общий делитель.

Если имеются разложения на простые множители двух чисел a и b, следует взять все простые числа, входящие в оба разложения, и каждое возвести в степень, равную минимуму из двух соответствующих показателей. Наименьшее общее кратное чисел a и b обозначается НОК (а, b) и по определению является наименьшим целым положительным числом, делящимся как на a, так и на b. Имея разложение на простые множители чисел a и b, можно получить НОК (a, b), взяв все простые числа, входящие хотя бы в одно из разложений, и каждое возвести в степень, равную максимуму из двух показателей. НОК (a, b) = |a*b| / НОД (a, b).

Алгоритм Евклида. При работе с большими числами часто случается, что их разложение на простые множители неизвестно. В частности, важным направлением исследований в теории чисел является отыскание быстрых методов разложения больших чисел на простые множители. К счастью, существует сравнительно быстрый способ нахождения НОД (a, b) даже в том случае, когда неизвестны простые делители a или b. Он называется алгоритмом Евклида. Алгоритм Евклида работает следующим образом. Чтобы найти НОД (a, b), где a > b, сначала делят a на b и записывают частное q-₁ и остаток r₁: a = q₁ * b + r₁ . Затем производят второе деление, в котором b играет роль a, а r₁ - роль b: b = q₂ * r₁ + r₂. Затем делят r₁ на r₂. Деление продолжают, каждый раз деля предпоследний остаток на последний, получая новые частное и остаток. Когда в конце концов получается остаток, который является делителем предыдущего остатка, то этот последний ненулевой остаток и есть наибольший общий делитель чисел a и b.



Глава 3. Сравнения

Основные понятия. Для дальнейшего изложения нам понадобятся основные понятия и факты теории сравнения целых чисел.

Пусть даны три целых числа a, b и m; говорят, что a сравнимо с b по модулю m, если разность a - b делится на m. Записывают это так: . Число m называется модулем сравнения. Из определения легко выводятся следующие свойства:

1. (i) ; (ii) тогда и только тогда, когда ; (iii) если и , то . Для фиксированного m свойства (i)-(iii) означают, что сравнимость по модулю m есть абстрактное отношение эквивалентности (т.е. является рефлексивным, транзитивным и симметричным).

2. Для фиксированного m каждый класс эквивалентности по этому отношению обладает в точности одним представителем в множестве чисел от 0 до m - 1. (Другими словами, любое целое число сравнимо по модулю ровно с одним целым числом в промежутке от 0 до m - 1). Множество классов эквивалентности (они называются классами вычетов) будет обозначаться Z/mZ. Любое множество представителей называется полной системой вычетов по модулю m.

3. Если и , то и . Другими словами, сравнения (по одному и тому же модулю) можно складывать, вычитать и перемножать. Таким образом, множество Z/mZ является коммутативным кольцом, т.е. классы вычетов можно складывать, вычитать и перемножать (причем результат не зависит от того, какие представители классов эквивалентности используются), и эти операции удовлетворяют обычным аксиомам ассоциативности, коммутативности, существования противоположного элемента и т. д.

4. Если , то для любого делителя d|m.

5. Если , и если m и n взаимно просты, то .

Решение линейного сравнения. Пусть требуется решить линейное сравнение ; не теряя общности, можно считать, что . Тогда если НОД (a, m) = 1, то сравнение имеет решение x₀, и любое решение имеет вид , где n -- некоторое целое число. Если же НОД (а, m) = d, то сравнение имеет решение тогда и только тогда, когда d|b, и в этом случае данное сравнение эквивалентно (в смысле совпадения множества решении) сравнению , где , , .

Приведем один из критериев проверки чисел на простоту.

Теорема (Вильсона). Для любого простого числа выполняется сравнение .

Доказательство

Для утверждение очевидно выполняется, поэтому далее будем считать, что нечетно. Пусть -- некоторое целое число из промежутка . Так как (а, р) = 1, то существует целое число , удовлетворяющее сравнению . При этом можно считать, что b есть наименьший неотрицательный вычет в своем классе. Ясно, что , т. е. . Кроме того, число b определяется единственным образом. Ведь если ; , то p | a * (b₁ - b₂) и р | (b₁ - b₂), что при различных b_1, b₂ из промежутка невозможно.

Если , то и . Так как p -- простое число, это возможно лишь в случае или . Из доказанного следует, что множество целых чисел а из промежутка может быть разбито на пары различных целых чисел a, b, удовлетворяющих сравнению . Следовательно,

Умножив это сравнение на , получим Для составных чисел теорема Вильсона, конечно, нарушается. Ведь если целое число N имеет делитель d, , то (N -- 1)! делится на d. Значит, (N -- 1)! + 1 на d не делится, а потому не делится и на N.

Замечание: Для составных чисел теорема Вильсона, конечно, нарушается. Ведь если целое число имеет делитель , , то делится на . Значит, на не делится, а потому не делится и на .

Функция Эйлера.

Определение. Для любого натурального функция Эйлера определяется как число неотрицательных целых b, меньших n и взаимно простых с n:

.

Теорема Эйлера. Для каждого целого числа a, взаимно простого с модулем m, выполняется сравнение

Доказательство

Пусть -- какая-нибудь приведенная система вычетов по модулю m. Тогда . Множество чисел также составляет приведенную систему вычетов. Это значит, что каждое число второй системы лежит в одном классе с каким-либо единственным числом первой системы вычетов. Поэтому справедливы сравнения



(1)

Так как каждое из чисел взаимно просто с модулем, то сравнение (1) можно сократить на каждое из . В результате получаем сравнение или .

Лемма. Пусть d -- показатель числа a по модулю m. Натуральное число k удовлетворяет сравнению в том и только том случае, когда d|k. В частности, d|.

Доказательство

Для каждого имеем

Докажем утверждение в обратную сторону. Пусть . Разделив k на d с остатком, получим , .

Тогда .

Учитывая, что d -- наименьший натуральный показатель с условием и , заключаем, что . Следовательно, d| k.

Рассмотрим частный случай теоремы Эйлера, в котором есть простое число. Тогда и получается следующее утверждение.

Малая теорема Ферма. Если целое число a не делится на простое число p, то .



Глава 4. Проверка чисел на простоту

Пусть - натуральное число, вообще говоря, большое. Оно может быть либо составным, либо простым. Как определить, к какому из этих двух классов относится данное число? Можно попробовать разделить на простые числа из таблицы, составленной с помощью решета Эратосфена и содержащей все простые числа до некоторой границы , определяемой нашими возможностями. Если у есть малые простые делители, то их можно найти таким способом и доказать, что N -- составное число.

Алгоритмы, в которых количество арифметических операций может быть оценено некоторой степенью числа цифр, необходимых для записи данных, называются полиномиальными.

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

Пробное деление. Один из самых простых способов проверки числа на простоту состоит в последовательном делении числа на все нечетные числа, которые содержатся в интервале . Если в процессе деления получим целый результат, то число - составное. Если же при переборе всех нечетных чисел из интервала разделить число на эти числа нацело нельзя, то число - простое. Данный метод называется пробным делением. Этот метод трудоемок по числу арифметических операций, и он используется в основном для проверки небольших простых чисел. Данный алгоритм работает за время .

Решето Эратосфена. Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).

2. Пусть переменная p изначально равна двум -- первому простому числу. Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …).

3. Найти первое не зачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.

4. Повторять шаги 3 и 4, пока возможно. Теперь все не зачёркнутые числа в списке -- простые.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3, числа можно зачеркивать, начиная сразу с числа , потому что все составные числа меньше его уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда станет больше, чем .

Тест на основе малой теоремы Ферма. На основании этой теоремы можно построить вероятностный алгоритм проверки на простоту числа . Если для некоторого целого из интервала соотношение не выполняется, то число - составное. Если же теорема выполняется, то вывод, что число простое, сделать нельзя, так как теорема дает лишь необходимое условие. Поэтому, если для некоторого имеет место соотношение , то говорят, что число является псевдопростым по основанию . Существует бесконечно много пар чисел и , где - составное и псевдопростое. Вообще для любого существуют бесконечно много псевдопростых чисел по основанию .

Определение. Составные числа , для которых при всех основаниях выполняется сравнение , называются числами Кармайкла.



Схема данного алгоритма выглядит следующим образом:

Дано число и параметр = 1 для идентификации результата проверки.

1) делается случайный выбор целого числа из интервала

2) используя алгоритм Евклида, вычисляется НОД для чисел и

3) если НОД больше 1, то выполняется шаг 7

4) для числа проверяется сравнение

5) если сравнение не выполняется, то определяется параметр (число составное) переход на шаг 7.

6) если сравнение выполнено, то можно повторить тест;

7) выдать результат проверки ( - число составное). При завершении работы алгоритма возможны следующие выводы:

· число n - составное ()

· если , то число является либо простым, либо составным и числом Кармайкла.



Глава 5. Практика

Задачи

Задача 1. Оценить время, требующееся для перевода числа из бит в десятичную систему счисления.

Решение

Пусть -- целое из бит, записанное в двоичной системе счисления. Алгоритм перевода следующий. Разделим на 10 = . Остаток от деления -- который является одним из чисел 0, 1, 10, 11, 100, 101, 110, 111, 1000 или 1001 -- даст содержи- содержимое разряда единиц. Частное от деления возьмем вместо , поделим на и возьмем остаток от этого деления в качестве , a частное -- в качестве делимого при следующем делении на . Этот процесс должен повторяться столько раз, сколько десятичных разрядов содержится в числе , т.е.

раз.

Тогда процесс будет завершен.

Задача 2. Решить

Решение



Задача 3. Найти НОД (1547, 560).

Решение

1547 = 2 * 560 + 427

560 = 1 * 427 + 133

427 = 3 * 133 + 28

133 = 4 * 28 + 21

28 = 1 * 21 + 7.

Так как 7|21, то НОД (1547, 560) = 7

Задача 4. Найти последнюю цифру в семеричной записи числа

Решение

Пусть . Так как 1000000 при делении на даёт остаток 4, получаем , и, значит последняя цифра равна 2.

Задача 5. Решить линейные сравнения:

·

·

Достаточно найти одно решение , тогда множество решений будет выражаться по формуле {.

· Ответ для первого сравнения }

· Второе сравнение не имеет решений т.к. НОД(3, 12) = 3 не делит 4.



Коды алгоритмов на языке С++

Перебор делителей до корня

#include <iostream>

using namespace std;

void algo () {

int n;

cin >> n;

bool prime = true;

for (int i = 2; i * i <= n; i++)

if (n % i == 0) {

prime = false;

break;

}

if (n == 1)

cout << "This is not prime number";

else

if (prime)

cout << "This is prime number";

else

cout << "This is not prime number";

}

int main () {

algo();

return 0;

}

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

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

#include <iostream>

#include <vector>

using namespace std;

void algo () {

int n;

cin >> n;

vector<bool> prime (n+1, true);

prime[0] = prime[1] = false;

for (int i = 2; i <= n; ++i)

if (prime[i])

if (i * i <= n)

for (int j = i * i; j <= n; j += i)

prime[j] = false;

}

int main () {

algo();

return 0;

}

Тест на основе малой теоремы ферма

#include <iostream>

#include <vector>

#include <ctime>

#include <math.h>

using namespace std;

int gcd (int a, int b) {

return b ? gcd (b, a % b) : a;

}

void algo () {

int n, p = 1;

cin >> n;

srand(time(NULL));

while (true) {

p = 1;

srand(time(NULL));

int a = rand() % (n - 1) + 2;

if (gcd(a, n) > 1) {

p = 0;

break;

}

else {

int ch = pow((double)a, n - 1);

if (ch % n != 1) {

p = 0;

break;

}

}

}

if (p == 1)

cout << "prime";

else

cout << "not prime";

}

int main () {

algo();

return 0;

}



Результаты работы программ

Перебор делителей

Входные данные	Выходные данные
1	This is not prime number
37	This is prime number
214	This is not prime number
113	This is prime number

Тест на основе малой теоремы ферма

Входные данные	Выходные данные
3	Prime
12	not prime
5	Prime
100	not prime



Использованная литература

1. Акритас А. Основы компьютерной алгебры с приложениями: Пер. англ. - М., Мир, 1994

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. М.: Мир, 1986

3. З. И. Боревич, И. Р. Шафаревич. Теория чисел. -- М.: Наука, 1972

4. С. В. Сизый. Лекции по теории чисел. -- Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999

5. Коблиц Н. Курс теории чисел в криптографии. Москва: Научное изд-во ТВП, 2001

6. Арнольд В. И. Группы Эйлера и арифметика геометрических прогрессий. -- М.: МЦНМО, 2003

7. Виноградов И. М. Основы теории чисел. -- 5-е изд. -- М.-Л.: Гостехиздат, 1952

Размещено на Allbest.ru

...