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

Алгоритмы поиска простых чисел

Время на прочтение
6 мин

Количество просмотров 134K

«Самое большое простое число 232582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.

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

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно

$leqslant sqrt{n}$, алгоритм можно останавливать, после вычеркивания чисел делящихся на

$sqrt{n}$.

Иллюстрация работы алгоритма из Википедии:

image

Сложность алгоритма составляет

$O(n loglog n)$, при этом, для хранения информации о том, какие числа были вычеркнуты требуется

$O(n)$ памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до

$sqrt{log n}$. Это позволяет снизить сложность алгоритма в

$loglog n$ раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером

$leqslant sqrt{n}$ и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до

$O(sqrt{n})$.

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.

Свойство 1

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 4)$. То n — простое, тогда и только тогда, когда число корней уравнения

$4x^2+y^2=n$ нечетно.

Свойство 2

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 1(mod 6)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2+y^2=n$ нечетно.

Свойство 3

Если n — положительное число, не кратное квадрату простого числа и такое, что

$n equiv 11(mod 12)$. То n — простое, тогда и только тогда, когда число корней уравнения

$3x^2-y^2=n$ нечетно.

Доказательства этих свойств приводятся в этой статье.

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все

$x, y < sqrt n$. Для каждой такой пары вычисляется

$4x^2+y^2$,

$3x^2+y^2$,

$3x^2-y^2$ и значение элементов массива

$A[4x^2+y^2]$,

$A[3x^2+y^2]$,

$A[3x^2-y^2]$ увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют

$O(n)$. При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до

$O(n / loglog n)$, а потребление памяти до

$O(sqrt{n})$.

Числа Мерсенна и тест Люка-Лемера

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

Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида

$2^p-1$, где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна

$M_p=2^p-1$ простое тогда и только тогда, когда p — простое и

$M_p$ делит нацело

$(p-1)$-й член последовательности

$S_k$ задаваемой рекуррентно:

$S_1=4, S_k=S_{k-1}^2-2$ для

$k > 1$.

Для числа

$M_p$ длиной p бит вычислительная сложность алгоритма составляет

${displaystyle O(p^{3})}$.

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня —

$2^{82,589,933}-1$, его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство

$a^{n-1}equiv 1{pmod {n}}$. Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство

$a^{n-1} notequiv 1 pmod n$, то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение

$a^{n-1}equiv 1{pmod {n}}$ выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

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

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения

$x^2 equiv 1 pmod p$, кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и

$p-1=2^sd$, тогда для любого a справедливо хотя бы одно из условий:

  1. $a^{d}equiv pm1{pmod {p}}$
  2. Существует целое число r < s такое, что $a^{2^{r}d}equiv -1{pmod {p}}$

По теореме Ферма

$a^{p-1}equiv1pmod p$, а так как

$p-1=2^sd$ из свойства о корнях уравнения

$x^2 equiv 1 pmod p$ следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно

$1/4$.

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое

$approx(1/4)^k$.

Сложность работы алгоритма

$O(klog^3p)$, где k — количество проверок.

Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе , этого не всегда оказывается достаточно.

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до

$2^{64}$ и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше

$2^{64}$ тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей

${U_{n}(P,Q)}, {V_{n}(P,Q)}$, описываемые выражениями:

${displaystyle U_{0}(P,Q)=0,quad U_{1}(P,Q)=1,quad U_{n+2}(P,Q)=Pcdot U_{n+1}(P,Q)-Qcdot U_{n}(P,Q),,ngeq 0}$

${displaystyle V_{0}(P,Q)=2,quad V_{1}(P,Q)=P,quad V_{n+2}(P,Q)=Pcdot V_{n+1}(P,Q)-Qcdot V_{n}(P,Q),,ngeq 0}$

Пусть

$U_n(P,Q)$ и

$V_n(P,Q)$ — последовательности Люка, где целые числа P и Q удовлетворяют условию

${displaystyle D=P^{2}-4Qneq 0}$

Вычислим символ Якоби:

$left({frac {D}{p}}right)=varepsilon$.

Найдем такие r, s для которых выполняется равенство

$n-ε=2^rs$

Для простого числа n выполняется одно из следующих условий:

  1. n делит $U_s$
  2. n делит $V_{2^js}$ для некоторого j < r

В противном случае n — составное.

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет

$(4/15)^k$.

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до

$10^8$. Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется

$M_p=2^p-1$.

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен

${frac {1}{ln n}}$. Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub.

Источник

Список простых чисел

Список всех простых чисел — сколько простых чисел в диапазоне

Калькулятор «Список простых чисел»

О калькуляторе «Список простых чисел»

Данный калькулятор покажет список простых чисел между заданными числами. Например, он может помочь узнать какие простые числа между 20 и 30? Выберите начальное число (например ’20’) и конечное число (например ’30’). После чего нажмите кнопку ‘Посчитать’.

Простые числа - это положительные целые числа, имеющие только два делителя - 1 и само себя.

Последние расчеты

Источник

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

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

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число. 

  var  
  n,i: longint;
  flag: boolean;
  begin  writeln('vvod n');
  read(n);  
  if n = 2 then flag := true
         else if not odd (n) then flag :=  false           
         else  begin                 
              flag := true;                 
              for i := 2 to n-1 do                 
              if n mod i = 0 then flag  := false                 
              end;
  if flag then writeln('Yes') else writeln('No'); 
  readln;
  end.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

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

Будем использовать следующие приемы оптимизации алгоритма:

  1. рассматривать только нечетные числа;
  2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
  3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

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

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

 var
 m,n,i,k: longint;
 flag: boolean;
 begin
 writeln('vvod m>3');
 readln(m);
 write('      2      3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag :=  false;
                    break
                end;
   if flag then begin
                write(n:7);
                k := k+1;
                if k mod 10 = 0 then writeln
                end;
 n := n+2
 end;
 writeln;
 writeln('kol-vo = ',k);
 readln
 end.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

 var
 m,n,n1,n2,i,k: longint;
 flag: boolean;
 begin
 m :=1000;
 n1 := 2; n2 := 3; n := n2+2; k:=0;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin  n1 := n2; n2 := n;
                 if (n2 -n1) = 2 then  begin
                               k := k+1;
                               write(n1:4,n2:4,' ');
                               if k mod 5 = 0 then writeln
                               end
             end;
 n := n+2
 end;
 writeln;
 writeln('kol -vo par =',k);
 readln
 end.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

 var
 m,n,i,k: longint;
 flag: boolean;
 f:text;
 begin
 assign(f,'output.txt'); rewrite(f);
 writeln('vvod m > 3');
 readln(m);
 write(f,'  2  3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin
            write(f,n:7);
            k := k+1;
            if k mod 10 = 0 then  writeln(f)
            end;
 n := n+2
 end;
 writeln(f);
 writeln(f,'kol-vo = ',k);
 close(f)
 end.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

  1. Вводим правую границу диапазона – m;
  2. Записываем двойку и тройку в файл;
  3. Пока очередное нечетное число i <= m :
    1. проверять очередное нечетное число на наличие делителей из данного файла;
    2. если есть делители, рассматривать очередное нечетное число, если нет — производить дозапись в “хвост” файла.
  4. По окончании просмотра диапазона ( i > m ), вывести в файл количество простых чисел.
{Простые  до m}
   label n1;
   var 
   m,i,j,k,q : longint;
   f : text;
   begin
      assign(f,'output.txt');
      rewrite(f);
      Writeln('vvod  m');  {m – правая граница диапазона чисел}
      readln(m);
      k := 0;             {k – счетчик количества  простых чисел}
      if  m >= 2 then begin
                   write(f,'  ':6,'2',' ':6);
                   k:=k+1
                 end;
      if m >= 3 then begin
                  write(f,'3');
                  k:=k+1
                end;
      close(f);
      i:=5;                {В i находится текущее  нечетное число}
      while  i <= m do
       begin  
        reset(f);
         {проверка делимости i на простые числа  q из файла}
         for j:=1  to k do
           begin
            read(f,q);
            if (q*q>i) then break;
            if (i mod q=0) then goto n1
           end;
        close(f); 
             {дозапись в ‘хвост’ файла простых  чисел}
        append(f);
            k:=k+1;
            Write (f,i:7);
            if k mod 10 = 0 then  writeln(f);
            close(f);
        {следующее нечетное число I  <= m}
        n1: i:=i+2
        end;
       {дозапись в конец файла количества простых  чисел} 
        append(f);
   writeln(f);
   writeln(f,'     kol -vo = ',k);
   close(f)
   end.

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

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод. 

Пусть написаны числа от 2 до n:

2 3 4 5 6 7 8 9 10 11 12 . . .

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

2 3 4 5 6 7 8 9 10 11 12 . . .

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

2 3 4 5 6 7 8 9 10 11 12 . . .

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

  1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
  2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
  3. Затем циклически повторим действия:
    1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
    2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

{Выделение всех простых чисел из первых n целых}
 const
 n = 255; {Количество элементов исходного множества}
 type
 SetOfNumber = set of 1..n;
 var
 n1, next, i: word;                    {Вспомогательные  переменные}
 BeginSet,                             {Исходное  множество}
 PrimerSet: SetOfNumber;               {Множество простых чисел}
 begin
   BeginSet := [2..n];                 {Создаем исходное множество}
   PrimerSet  :=[2];                 {Поместить в PrimerSet  первое число из BeginSet}
   next := 2;                          {Первое простое  число}
    while BeginSet  <> [] do            {Начало  основного цикла}
          begin
           n1 := next;   {n1 –число, кратное  очередному простому (next)}
            {Цикл удаления из исходного  множества непростых чисел:} 
           while n1  <= n do
  begin
  Exclude(BeginSet,n1);
  n1 := n1+next         {Следующее кратное}
  end;        {Конец цикла  удаления}
  Include(PrimerSet,next);
  {Получение следующего простого, которое  есть первое невычеркнутое
  из исходного множества}

  repeat
  Inc(next);
  until  (next in BeginSet) or (next > n)
  end;  {Конец основного цикла}
  {Вывод результатов:}

  for  i := 1 to n do
  if i in PrimerSet then write(i:5);
  readln
  end.

Литература:

  1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
  2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. — 255 с.
  3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. — 616 с.
Источник

Красивые аномалии встречаются в каждом предмете, но если есть одна область красоты, с которой согласится большинство математиков, то это простое число.

Эти числа занимают уникальный пьедестал в математике, особенно в области теории чисел. Великие умы потратили бесчисленные часы для расследования этой проблемы, в том числе такие великие умы, как Пол Эрдос, Г.Х. Харди и Сриниваса Рамануджан, и это лишь некоторые из них. Теперь, прежде чем мы углубимся в различные алгоритмы, чтобы найти простые числа, давайте сначала установим предварительное понимание простых чисел.

Что такое простые числа?

Самое техническое определение простых чисел состоит в том, что это натуральное число больше 1 и может быть получено только путем умножения 1 и самого себя. Если бы понимание натуральных чисел было более интуитивным, то можно было бы сказать, что это числа, которые мы используем для подсчета.

Чтобы понять это более точно, давайте выберем два числа — 5 и 6. Теперь 5 — это число, которое можно получить только умножением на 1 и 5 (само число). Однако, когда мы берем число 6, то замечаем, что его можно получить другим способом, кроме умножения 1 и 6 (само число). Его также можно получить умножением чисел 2 и 3, что означает, что это не простое число. Число, которое не является простым, известно как составное число.

Метод Марена Мерсенна

Метод простого числа Мерсенна — это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна — это те, которые сводимы к виду 2n-1, где n-простое число. Первые несколько чисел в этом методе являются 2, 3, 5, 7, 13, 17, 19, 31, 61, и 89. Долгое время метод простых чисел Мерсенна представлял собой тяжёлую работу, так как при переходе к более высоким простым числам он был очень трудоемким.

Марен Мерсенн Французский математик

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

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

В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!

Метод простых чисел Ферма

Число Ферма, как и число Мерсенна, представляет собой особый вид простого числа. Название происходит от математика 17-го века и юриста Пьера де Ферма. Число Ферма похоже на число Мерсенна… с одной маленькой поправкой. Давайте возьмем число Ферма Fm, где мы можем определить Fm как 2m +1. Здесь m снова равно 2, возведенному в степень n или 2n.

Пьер де Ферма (фр. Pierre de Fermat, 17 августа 1601 — 12 января 1665) — французский математик-самоучка, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел.

Фермат был твердо убежден в том, что все числа вышеуказанной формы — это простые числа. В дальнейшем он сказал, что он будет производить простые числа для всех целочисленных значений m. Что делает эти числа уникальными и красивыми, но очень хитрыми, так это то, что простые числа становятся чрезвычайно большими очень быстро, даже в пределах первых четырех итераций. Чтобы доказать это, возьмем n в качестве следующих значений, n=0, 1, 2, 3 и 4.

Когда n = 0, m = 20 = 1; поэтому F0 = 2 1 + 1 = 2 + 1 = 3, что является простым. Когда n = 1, m = 21 = 2; поэтому F1 = 22 + 1 = 4 + 1 = 5, что является простым. Когда n = 2, m = 22 = 4; следовательно, F2 = 24 + 1 = 16 + 1 = 17, что является простым. Когда n = 3, m = 23 = 8; следовательно, F3 = 28 + 1 = 256 + 1 = 257, что является простым. Когда n = 4, m = 24 = 16; следовательно, F4 = 216 + 1 = 65536 + 1 = 65537, что является простым числом. Теперь, как вы можете заметить, к тому времени, когда мы достигнем F5, значение достигает 4 294 967 297.

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

Источник

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

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

12.1. Простые числа

Асимметрично-ключевая криптография широко использует простые числа. Тема простых чисел — большая часть любой книги по теории чисел. Эта лекция обсуждает только несколько понятий и фактов, чтобы открыть путь к лекциях 14-15.

Определение

Положительные целые числа могут быть разделены на три группы: число 1, простые числа и составные объекты, как это показано на рис. 12.1.

Три группы положительных целых чисел

Рис.
12.1.
 Три группы положительных целых чисел

Положительное целое число — простое число тогда и только тогда, когда оно точно делимо без остатка на два целых числа — на 1 и на само себя. Составной объект — положительное целое число больше с чем двумя делителями.

Простое число делимо без остатка только на себя и 1.

Пример 12.1

Какое наименьшее простое число?

Решение

Наименьшее простое число — 2, оно делится без остатка на 2 (само на себя) и 1. Обратите внимание, что целое число 1 — не простое число согласно определению, потому что простое число должно быть делимо без остатка двумя различными целыми числами, не больше и не меньше. Целое число 1 делимо без остатка только на себя; поэтому 1 — это не простое число.

Пример 12.2

Перечислите простые числа, меньшие, чем 10.

Решение

Есть четыре простых числа меньше чем 10: 2, 3 5 и 7. Интересно, что процент простых чисел в диапазоне 1-10 — 40%. С увеличением диапазона процент уменьшается.

Взаимно простые числа

Два положительных целых числа a и b являются взаимно простыми (coprime), если НОД (a, b) = 1, потому что число 1 является взаимно простым с любым целым числом. Если p — простое число, тогда все числа от 1 до p–1 являются взаимно простыми к p. В
«Модульная арифметика»
мы обсуждали множество Zn*, чьи элементы — все числа, взаимно простые с n. Множество Z * является тем же самым, за исключением того, что модуль (p) — простое число.

Количество простых чисел

После того как понятие простых чисел было определено, естественно возникает вопрос: число простых чисел конечно или бесконечно? Возьмем число n. Сколько есть простых чисел меньших, чем это число, или равных n?

Число простых чисел

Число простых чисел бесконечно. Приведем нестрогое доказательство: предположим, что множество простых чисел конечно (ограничено), и пусть p — наибольшее простое число. Перемножим все простые числа, входящие в это множество, и получим результат P = 2 times 3 times cdots times p. Целое число (P + 1) не может иметь простого делителя q leqslant p (p – наибольшее простое число). Тогда этот делитель должен быть одним из множителей, входящих в P. Это значит, что q делит P. Если q также делит (P + 1), то q делит (P + 1) – P = 1. Единственное число, которое делит 1, — это сама 1, которая не является простым числом. Поэтому q должно быть большим, чем p, и ряд простых чисел не исчерпывается принятым конечным множеством.

Число простых чисел бесконечно.

Пример 12.3

Как тривиальный пример, предположим, что единственные простые числа находятся в множестве {2, 3, 5, 7, 11, 13, 17}. Здесь P = 510510 и P + 1 = 510511. Однако 510511 состоит из следующих простых чисел 510511 = 19 times 97 times 277; ни одно из этих простых чисел не было в первоначальном списке. Эти три простых числа больше, чем 17.

Число простых чисел, меньших n

Чтобы рассмотреть вторую возможность, введем функцию pi (n), которая определяет число простых чисел, меньших или равных n. Ниже показаны значения этой функции для различного pi (n).

ttparindent0pt pi (1) = 0 pi (2) = 1 pi (3) = 2 pi (10) = 4 pi (20) = 8 pi (50) = 15 pi (100) = 25

Но если n является очень большим, как мы можем вычислить pi (n)? Для ответа мы можем использовать только приближение, которое показано ниже:

left[ {n/(ln n)} right] < pi (n) < [n/(ln n-1.08366)]

Гаусс обнаружил верхний предел; Лагранж обнаружил нижний предел.

Пример 12.4

Найдите количество простых чисел, меньших, чем 1 000 000.

Решение

Приближение дает диапазон от 72 383 до 78 543. Фактическое число простых чисел — 78 498.

Проверка на простое число

Следующий вопрос, который приходит на ум: как мы можем определить для данного числа n, является ли оно простым числом? Мы должны проверить, делимо ли без остатка это число всеми простыми числами, меньшими, чем sqrt n . Мы знаем, что этот метод неэффективен, но он хорош для начала.

Пример 12.5

Действительно ли 97 — простое число?

Решение

Наибольшее ближайшее целое число — sqrt n = 9. Простые числа меньше чем 9 — 2, 3, 5 и 7. Проверим, делимо ли без остатка 97 любым из этих номеров. Ответ: не делимо, так что 97 — простое число.

Пример 12.6

Действительно ли 301 — простое число?

Решение

Наибольшее ближайшее целое числоsqrt 301 = 17. Мы должны проверить 2, 3, 5, 7, 11, 13 и 17. Числа 2, 3 и 5 не делят 301, но 7 — делит. Поэтому 301 — не простое число.

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

Греческий математик Эратосфен изобрел метод, как найти все простые числа, меньшие, чем n.

Метод назван решетом Эратосфена. Предположим, что мы хотим найти все числа, меньшие, чем 100. Мы записываем все числа между 2 и 100. Поскольку sqrt 100 = 10, мы должны видеть, делим ли без остатка любой номер меньше чем 100 на числа 2, 3, 5 и 7. Таблица 12.1 показывает результат.

Таблица
12.1.
Решето Эратосфена

2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Процесс состоит в следующем:

  1. Вычеркнуть все числа, делимые без остатка на 2 (кроме самого 2).
  2. Вычеркнуть все числа, делимые без остатка на 3 (кроме самого 3).
  3. Вычеркнуть все числа, делимые без остатка на 5 (кроме самого 5).
  4. Вычеркнуть все числа, делимые без остатка на 7 (кроме самого 7).
  5. Оставшиеся числа – простые.
Источник

Понравилась статья? Поделить с друзьями:
  • Как исправить баг на телефоне
  • Нашел айрподсы как подключить
  • Как найти дело по номеру судебного приказа
  • Как найти катет если известна медиана
  • Как найти фильтр по фотографии