Математические основы асимметричной криптографии

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

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

Целое положительно число р называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицу. Примеры простых чисел — 11, 23; составных — 10, 22, 27.

Основная теорема арифметики. Любое целое число может быть представлено в виде произведения простых чисел, причем единственным способом. Примеры разложения составных чисел на простые сомножители: 10 = = 2-5,22 = 2-11,27 = 3-3-3.

Два числа называются взаимно простыми, если они не имеют ни одного общего делителя, кроме единицы. Примеры: числа 27 и 28 — взаимно просты, числа 27 и 33 имеют общий делитель 3, отличный от единицы, и не являются взаимно простыми.

Наибольший общий делитель (НОД). Пусть а и b — два целых положительных числа. НОД чисел а и b есть наибольшее число с, которое делит и а, и Ь. Обозначения: с = (а, Ь), с = НОД(л, Ь). Можно сказать, что два числа aub — взаимно просты, если их НОД равен единице: НОД(я, b) = 1.

Числа, дающие при делении на т одинаковые остатки, называются сравнимыми по модулю т. Обозначение: а = b (mod m). Два целых числа сравнимы по модулю т тогда и только тогда, когда их разность делится на т (а = h (mod т) <=> а - b = тк).

Свойства сравнений. 1. Общие свойства:

  • • рефлексивность — а = л (mod/и);
  • • симметричность — если а = b (mod m), то и b = a (modm);
  • • транзитивность — если а = b (modm), b = с (mod/я), то а = с (modm).
  • 2. Сравнения по одному и тому же модулю можно почленно складывать. Если а = b (modm) и с = d (modm), то а + с = b + d (modm).
  • 3. Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого. Если а = b (mod m) и с = d (mod m), то а - с = b - d (mod m).
  • 4. К обеим частям сравнения можно прибавлять одно и то же целое число. Если а = b (mod m), то а + k = b + k (mod m). Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
  • 5. Сравнения по одному и тому же модулю можно почленно перемножать. Если а = b (mod т), с = d (mod т), то ас = bd (mod т). Как следствие, обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а = b (mod т) и к — целое неотрицательное число, то ak = bk (modm).
  • 6. Обе части сравнения можно умножать на одно и то же целое число.
  • 7. Если а = b (mod т) и т делится нацело на п, то а = b (mod п).
  • 8. Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
  • 9. Если ak = bk (mod т) и НОД(&, т) = d, то а = b (mod m/d). Если ak = bk (mod 777) и НОД(?, т) = k, то а = b (mod m/k). Это значит, что если т делится на k нацело, то обе части сравнения и модуль можно разделить на любой их общий делитель. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем. Если ak = bk (mod т) и НОД(&, т) = 1, то а = b (modm).

Пример 3.2

  • 60 = 9 (mod 17). Поскольку НОД(3, 17) = 1, то после деления обеих частей сравнения па 3 получим 20 = 3 (mod 17).
  • 8 = 4 (mod 4), но НОД(4, 4) ** 1 и 2 = 1 (mod 4).
  • 10. Если сравнение а = b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному (НОК) этих модулей.
  • 11. Как следствие всех перечисленных свойств получаем: если а = b (mod т), то и Р(а) = P(b) (mod m), где Р(х) — многочлен с целыми коэффициентами. Таким образом, в сравнении по модулю т отдельные слагаемые и множители (но не показатели степени) можно заменять числами, сравнимыми по тому же модулю т. В частности, все числа, кратные модулю, можно заменять нулями.

Пример 3.3

Найти (37,6+ 16) mod 7.

Поскольку 37 = 2 (mod 7), 16 = 2 (mod 7), то (3716 + 16) = (2,G + 2) (mod 7) и задача сведена к вычислению (216 + 2) mod 7.

Поскольку 8 = 23 = 1 (mod 7), то и 215 = (23)5 = 1 (mod 7).

Значит, (2,6+ 2) mod 7 = (2 + 2) mod 7 = 4.

Ответ: (3716 + 16) mod 7 = 4.

Пример 3.4

Найти (96746 + 28)15 mod 39.

Поскольку 9674 = 2 (mod 39), то 96746 = 26 (mod 39) = 64 (mod 39) = 25 (mod 39). Далее, 25 + 28 = 53 = 14 (mod 39). Следовательно, (9674е + 28)15 = 1415 (mod 39). Задача теперь сведена к следующей: найти 1415 mod 39.

Воспользуемся сравнениями: 14 = -l(mod 3) и 14 = l(mod 13). Из 14 = = -1 (mod 3) следует: 1414 = l(mod 3). Из сравнения 14 = 1 (mod 13) следует: 14й = 1 (mod 13). Поскольку сравнение имеет место по модулям 3 и 13, то оно имеет место и по модулю 39, являющемуся НОК чисел 3 и 13. Итак, 1414 = = 1 (mod 39). Однако в таком случае 1415 = 14 (mod 39).

Ответ: (96746+28)15 mod 39 =14.

Функция Эйлера. Пусть дано положительное целое число N > 1. Значение функции Эшера (N) равно количеству чисел в ряду 1, 2,N - 1, взаимно простых с N.

Пример 3.5

Определить значения функции Эйлера (рис. 3.4) — зачеркнуты числа, не являющиеся взаимно простыми с аргументом функции.

Определение значения функции Эйлера

Рис. 3.4. Определение значения функции Эйлера

Утверждение 1. Если р — простое число, то ср(/?) = р - 1.

Утверждение 2. Пусть р и q — два простых числа, р * q. Тогда <р(j)q) = ~(Р ~ 1 )(

Малая теорема Ферма. Пусть р — простое число и 0 < а < р. Тогда а1 1 mod р = 1.

Пример 3.6

р = 13, а = 2. 212 mod 13 = 4096 mod 13 = 1.

р= 11, а = 10. 1010 mod 11 = 102- |(102)2|2mod 11 = 11 = 1.

Пример 3.7

Найти 32fi mod 7.

7 — простое число, ф(7) = 7-1, согласно теореме Ферма 3s = 1 (mod 7), тогда З24 = 1 (mod 7). Кроме того, З4 = 81 = 4 (mod 7). Тогда 3 = З24 • З4 (mod 7) = 4.

Теорема Эйлера. Пусть а и b — взаимно простые числа. Тогда й9^ mod ft = 1. Теорема Ферма является частным случаем теоремы Эйлера, когда ft - простое число.

Пример 3.8

а = 5, ft = 12, ср( 12) = 4. 54 mod 12 = 625 mod 12 = 1.

Пример 3.9

Найти З9 mod 10.

НОД(3, 10) = 1; согласно теореме Эйлера, 39(W) mod 10 = 1. 10 = 5 2, 5 и 2 — простые числа, следовательно ср(Ю) = (5 - 1)(2 - 1) = 4, З4 mod 10 = 1.

З9 mod 10 = 3(34)2 mod 10 = 3.

Теорема. Если р и q — простые числа, р * q и ft — произвольное целое число, то a*f(w>+1 mod pq = а.

Пример 3.10

Найти 2381 mod 34.

34 = 17-2, 17, 2 — простые числа, <р(34) = <р( 17-2) = (17 - 1)(2 - 1) = 16. 81 = = 1 + 80 =1 + 16-5, k = 5, применяя теорему, получаем: 233ф<34)^1 mod 34 = 23.

Решение сравнений первой степени. Для многих криптографических систем с открытым ключом актуально вычисление числа, обратного по модулю данному. Иными словами, ставится задача для заданных чисел а, р определить значение х < р, такое, что: ах mod р = 1. Сравнение ах mod р = ft называют сравнением первой степени с одним неизвестным. Решение данного сравнения сводится к отысканию целых значений х, удовлетворяющих уравнению ах = ру + ft. Сравнение может быть и неразрешимо в целых значениях х.

Теорема. Для того чтобы сравнение ах mod р = Ь имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на II ОД (я, р).

Теорема. Пусть сравнение ах mod p = h разрешимо и НОД(я, р) = d. Тогда множество решений сравнения состоит из d классов по модулю р, а именно, если х0 одно из решений, то все другие решения — это х0 + т, х0 + 2т, ..., х0 + (d - 1 )т, где т = p/d.

Пример 3.11

Сравнение 9х = 6 (mod 12) имеет ровно три решения, так как НОД(9,12) = 3. Эти решения: х0 = 2, х0 + 4 = 6, х0 + 2 • 4 = 10.

Сравнение 11х = 2 (mod 15) имеет единственное решение х0 = 7, так как НОД(11, 15) = 1.

Сравнение ах mod р = 1 разрешимо тогда и только тогда, когда НОД(я, р) = 1, т.е. числа аир — взаимно просты. В этом случае существуют единственные значения х и у, такие, что ах + ру= 1.

Число х < р, удовлетворяющее равенству ах mod р= 1, называется инверсией (числом, обратным) а по модулю р и часто обозначается как а 1 mod р. Для отыскания числа, обратного по модулю данному, используется расширенный (обобщенный) алгоритм Евклида.

Теорема. Пусть а и b два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа х и у, такие что ах + by = = НОД(я, Ь). Числа а и Ь, удовлетворяющие этому условию, могут быть найдены с помощью расширенного алгоритма Евклида.

Вычисление числа, обратного по модулю заданному. Расширенный алгоритм Евклида. Расширенный алгоритм Евклида служит для отыскания НОД(й, Ь) и х, у, удовлетворяющих равенству ах + by = НОД(а, Ь). Входом алгоритма служат числа а, Ь, а > Ь. Выходом алгоритма являются НОД(«, Ь) и х, у, такие, что ах + by = НОД(«, Ь).

Расширенный алгоритм Евклида на псевдоязыке:

Алгоритм является итерационным, первоначально формируются входные строки U, V и вычисляется строка Т. На следующем шаге мы как бы сдвигаемся вниз на одну строку, поэтому входными данными уже будут значения строк V и Т, полученных на предыдущем шаге. Вычисления продолжаются до тех пор, пока в качестве первого элемента строки не будет получен нуль. Искомые значения содержатся строкой выше.

Пример 3.12

Найти d = 1/19 mod 28 = 19 1 mod 28.

а = 28, b = 19 (а > b).

Пошаговые вычисления в соответствии с расширенным алгоритмом Евклида приведены в табл. 3.1.

Таблица 3.1

Пример нахождения числа, обратного но модулю, с помощью расширенного алгоритма Евклида

Шаг

1

2

3

Элементы строк

Я

и

28

1

0

V

и

19

0

1

1

Т

V

и

9

1

-1

1

2

Т

V

1

-2

3

2

3

Т

0

19

-28

9

Результат: НОД(19, 28) = 1,х= -2, у = 3, следовательно 19у mod 28 = 1, d = 3. В самом деле, 19 • 3 = 57 = 1 (mod 28).

Ответ: d = 3.

Пример 3.13

Вычислить 5-2 mod 11. Для решения этой задачи можно действовать двумя способами (число, обратное заданному по модулю, получается с помощью расширенного алгоритма Евклида):

  • 1) 5-2 mod 11 = (52 mod 11 )_| mod 11=3’ mod 11=4;
  • 2) 5 2 mod 11 = (5 1 mod 11 )2 mod 11 = 92 mod 11=4.

Ответ: 5 2 mod 11=4.

Пример 3.14

Вычислить 2/3 mod 7.

2/3 mod 7 = 3 1 mod 7 = -2 mod 7 = 5; 2 • 5 mod 7 = 3.

Ответ: 2/3 mod 7 = 3.

При нахождении числа, обратного по модулю, вообще говоря, элементы второго столбца нас не интересуют, поэтому вторые элементы строк 2, v2, t2) можно не вычислять. Если полученное число, обратное заданному по модулю, оказалось отрицательным, его надо взять по модулю (т.е. сложить со значением модуля).

Если необходимо получить только НОД чисел, то можно не вычислять элементы второго и третьего столбцов в расширенном алгоритме Евклида (элементы и2, и3, v3, t2, t3). Данный случай эквивалентен обычному алгоритму Евклида.

Китайская теорема об остатках. Рассмотрим систему сравнений первой степени:

где числа тv т.}1..., тг попарно взаимно просты. Требуется найти целое значение xQy удовлетворяющее всем /'сравнениям.

Теорема (китайская теорема об остатках). Пусть mv т2,..., тг попарно взаимно просты, и числа av а2,..., аг произвольные целые. Тогда существует такое целое числох0, что 0 < х0 < т{т2•... • тг их0 = a, (mod тЛ),х0 = а2 (mod т2), ..., х0 = ar (mod m3):

где Му = хг и Ni = M._1(modm,).

Пример 3.15

Требуется решить систему сравнений:

Найти М, = 6 • 7 = 42, М2 = 5 • 7 = 35, М3 = 5 • 6 = 30. С помощью расширенного алгоритма Евклида можно найти числа, обратные по модулю:

Тогда, по китайской теореме об остатках

Проверка: 207 mod 5 = 2; 207 mod 6 = 3; 207 mod 7 = 4.

Универсальные алгоритмы вычисления степени по модулю. Алгоритм повторного умножения по модулю. Рассмотрим возведение целого числа в целую степень по модулю р. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю р, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами сравнений:

аЪmod/? = [(яmod/?) • /?]mod/? = [(«mod/?) • (Amod/?)]mod/?.

Таким образом, можно рассмотреть промежуточные результаты по модулю /?. Это делает вычисления практически выполнимыми.

Например, для вычисления 883mod 23 можно выполнить следующее преобразование, которое может быть реализовано как итерационный алгоритм:

Алгоритм повторного возведения в квадрат по модулю. Существует более эффективный алгоритм вычисления большой степени числа, основанный на возведении в квадрат но модулю /?. Степень х при вычислении значения ах представляется в виде последовательности операций умножения на 2 и сложения с единицей. Пусть, например, требуется вычислить ат mod/?. Представим степень как 100 = 2-2[ 1+2-2 -2(1+ 2)].

Разложение степени на слагаемые и множители может быть описано следующим итерационным алгоритмом: пока показатель степени не стал равным единице, если показатель четный — следует записать 2 • (или сокращенно 2(), если же показатель степени нечетный — следует записать 1 +, в обоих случаях затем над показателем степени следует произвести операцию, обратную записанной (разделить на 2 или вычесть 1 соответственно). Затем описанные шаги повторяются. В конце процедуры разложения степени следует корректно закрыть скобки. Пошаговое разложение степени 100 приведено в табл. 3.2.

Степень 100 может быть представлена в виде скобочной записи

Таблица 3.2

Пример разложения показателя степени

Степень до

100

50

25

24

12

6

Запись

2(

2(2(

2(2(1 +

2(2(1 +2(

2(2(1 +2(2(

2(2(1 + 2(2(2(

Степень после

50

25

24

12

6

3

Степень до

3

2

1

Запись

2(2(1 + 2(2(2(1 +

2(2(1 + 2(2(2(1 +2(

2(2(1+2(2(2(1+2)))))

Степень после

2

1

или, чтобы сократить число скобок, в виде эквивалентной записи Тоща возведение в степень

Пример 3.16

Вычислить 7™ mod 23, результат — 16 (табл. 3.3).

Пример быстрою возведения в степень

Таблица 3.3

Номер шага

1

2

3

4

Вычисления

72 mod 23

х-1 mod 23

х2 mod 23

x2 mod 23

X

3

21

4

16

Номер шага

5

6

7

8

Вычисления

х2 mod 23

х-1 mod 23

х2 mod 23

x2 mod 23

X

3

21

4

16

Таким образом, возведение в степень 100 производится путем двух умножений и шести возведений в квадрат но модулю (всего восемь операций умножения).

Количество операций умножения при вычислении ах методом повторного возведения в квадрат не превосходит 2 log х.

Приведенный алгоритм прост для восприятия человеком, однако не очень удобен для компьютерной реализации. Описания алгоритма для компьютерной реализации используют представление показателя степени х в двоичной системе счисления: х = (.г,, х, ,,..., х,, х0)2. Тогда число у = a' mod р может быть вычислено как

где t — номер старшего значащего бита в двоичной записи числах.

Пример 3.17

Вычислить 7'00 mod 23, 100ш = 1100100;,. Шаги и промежуточные результаты вычислений представлены в табл. 3.4.

Таблица 3.4

Пример вычисления степени но модулю методом повторного возведения в квадрат

Степень а

а

а2

а4

а8

а16

а32

аи

Числа ряда a2' (mod р)

7

3

9

12

6

13

8

Двоичные разряды х (начиная с младшего)

0

0

1

0

0

1

1

Множители

1

1

9

1

1

13

8

В ряду а2 каждое число получается путем умножения предыдущего числа на само себя но модулю р. Всего потребовалось восемь операций умножения: шесть — для вычисления чисел ряда а2 и две — для их перемножения.

Данный алгоритм может быть реализован без хранения в памяти ряда а2'. Входом алгоритма являются числа а, х = (х,, х,_,,xv х0), и р. Выходом является число у = a*modр. Двоичное представление степени х просматривается слева направо (от старшего бита к младшему).

Алгоритм повторного возведения в квадрат на псевдоязыке:

Значения переменной у после каждой итерации цикла для х = 100 представлены в табл. 3.5.

Таблица 3.5

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

Номер шага i

6

5

4

3

2

1

0

х,

1

1

0

0

1

0

0

У

а

а3

а6

а12

а[1]

а50

а100

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

С теоретической точки зрения большие простые числа встречаются достаточно часто1, а именно: число простых чисел, меньших N, может быть оценено как IV/ln N при N —> сю. Указанная оценка обладает хорошей точностью даже для сравнительно небольших А. Так, для N = 109 она дает погрешность всего в 6% (для криптографических задач используют простые числа порядка 2160 = (210)16 ~ (103)16 ~ 1048 и более). Таким образом, вероятность угадывания большого простого числа порядка N составляет около 1/1пЛг. Кроме того, простые числа распределены вполне равномерно. Так, для N>6 справедливо неравенство A In A < р < N( N + Inin А), где р — А-е простое число. Следовательно, на практике для нахождения простого числа потребуется перебрать в среднем In N чисел, близких к N. Например, для нахождения простого числа, имеющего 100 десятичных разрядов, в среднем потребуется перебрать 1п10100~ 230 чисел этой разрядности (или в два раза меньше, т.е. около 115, если рассматривать только нечетные числа). Для каждого числа требуется проверить его простоту.

Самым очевидным тестом проверки простоты числа является проверка его делимости на все простые числа г, меньшие J~N (т.е. вычисление с помощью алгоритма Евклида НОД (А, г) и проверка условия НОД (А, г) = 1). Однако полный перебор возможных делителей для больших чисел является неэффективным.

Существуют две разновидности тестов для проверки простоты числа - детерминированные и вероятностные. Детерминированные (истинные) тесты простоты позволяют точно определить, является число простым или составным, однако они достаточно медленны. В 2002 г. предложен детерминированный тест простоты с полиномиальной сложностью, названный AKS по именам разработчиков (Agrawal, Kayal и Saxena), однако на практике и он уступает вероятностным тестам. Вероятностные тесты позволяют отбраковать составные числа, однако прошедшее тест число может считаться простым лишь с некоторой вероятностью.

Вероятностные тесты опираются на проверку равенств, которые выполняются для простых чисел. Если хотя бы одно такое равенство не выполняется, это доказывает, что число является составным.

Наиболее удобным (простым и эффективным) является вероятностный тест Миллера — Рабина, имеющий полиномиальную сложность. Тест Миллера — Рабина опирается на проверку следующего факта.

Пусть N — нечетное число, представим число N - 1 в виде N - 1 = 2st, где t — нечетное, и пусть а — целое число, 1 < а < N. Если число А является простым, то выполняется одно из условий: либо а1 = 1 (mod А), либо существует такое целое число г, 0 < г < s - 1, что art = -1 (mod N).

Если для числа N и некоторого а указанный факт подтверждается, то число N — вероятно простое. При этом вероятность того, что число А окажется составным, нс превышает 1/4. Если же для числа А найдется а, опровергающее указанный факт, то число А является составным. Поэтому при повторении теста с k различными числами а вероятность неотбраковки составного числа (т.е. вероятность того, что число составное число А пройдет все к тестов и будет ошибочно принято за простое) составит (1/4)* или 2 .

Тест простоты Миллера — Рабина для проверки нечетного числа N выглядит следующим образом.

  • 1. Пока число итераций не достигло к:
  • 2. Выбрать случайное число ау 1 < а < N.
  • 3. Вычислить х = a1 mod А Если х = 1, то перейти к шагу 1, в противном случае перейти к следующему шагу.
  • 4. Пока число итераций нс достигло s - 1:
  • 5. Вычислить х = х2 mod N (вычисление чисел a2'[2] mod N). Если х = = -1, перейти к шагу 1, в противном случае перейти к шагу 4.
  • 6. Если пройдены всех - 1 итераций, ответ «N — составное».
  • 7. Если пройдены все k итераций, ответ «N вероятно простое».

Число итераций к выбирается исходя из допустимой вероятности ошибки. Сложность теста Миллера — Рабина составляет О(sN).

Пример 3.18

Проверить простоту числа 91с помощью теста Миллера — Рабина (91 является составным числом 91=7-13).

Представим 91 - 1 = 90 = 2 • 45, s = 1, t = 45.

Пусть а = 2. Проверим г = 0. Вычислим х = a' mod N = 245 mod 91 = 57 * ±1. Поскольку s - 1 = 1 - 1 =0, ответ «91 — составное».

Пример 3.19[2]

Проверить простоту числа 561 с помощью теста Миллера — Рабина (число 561 — составное: 561 = 3- 11 • 17).

Представим 561 - 1 = 560 = 24 • 35, 5 = 4, t = 35.

Пусть а = 2. Проверим г = 0. Вычислим* = a' mod N = 235 mod 561 = 263 * ±1. s - 1 = 3.

Шаг 1 — проверим r= l.x = x2 mod N= 2632 mod 561 = 166^-1; шаг 2 — проверим г = 2. х = х2 mod N= 1662 mod 561 = 67 * -1; шаг 3 — проверим r=3 = 5- .х = х2 mod N = 672 mod 561 = 1 * -1. Поскольку пройдены все итерации до 5 - 1, ответ — «561 — составное».

Пример 3.20

Проверить простоту числа 61 с помощью теста Миллера — Рабина с вероятностью 99% (число 61 — простое).

Представим 61 - 1 = 60 = 22 • 15, s = 2, t = 15.

Заданная вероятность ошибки теста не должна превышать 1% (100% - 99%), т.е. 0,01. Для этого достаточно выполнить четыре итерации (к = 4) теста Миллера — Рабина, в этом случае вероятность ошибки не превышает 2 ~ 0,004 < 0,01 (при k = 3 вероятность ошибки 0,016 > 0,01).

k= 1, пусть а = 2. Проверим г= 0. Вычислим* = a' mod N = 215 mod 61 = 11 *±1. 5-1 = 1.

Проверим r= 1. Вычислим* = х2 mod N= ll2 mod 61 = 60 mod 61 = -1, N — вероятно простое по основанию 2.

к = 2, пусть а = 3. Проверим г = 0. Вычислим * = a' mod N = З15 mod 61 = = 60 mod 61 = -1, N — вероятно простое по основанию 3.

к = 3, пусть а = 5. Проверим г = 0. Вычислим х = a' mod N = 515 mod 61 = = 60 mod 61 —1, N — вероятно простое по основанию 5.

к = 4, пусть о = 7. Проверим г = 0. Вычислим* = d mod iV= 715 mod 61 = 11 * ±1. Проверим г — 1. Вычислим * = jc2 mod N = 112 mod 61 = 60 mod 61 = -1, N — вероятно простое по основанию 7.

Ответ: 61 — вероятно простое (с вероятностью 99%).

Эффективность проверки на простоту при выборе большого простого числа можно существенно повысить, если сначала провести проверку наличия небольших делителей. Так, проверка того, что случайное нечетное число не делится на 3, 5 и 7, позволяет сразу отбраковать 54% чисел, проверяемых на простоту. Проверка делимости на все простые числа, меньшие 100, позволяет отбраковать как составные 76% нечетных чисел, а проверка делимости на все простые числа, меньшие 256, — 80%. В общем случае, доля нечетных чисел, которые не делятся ни на одно простое число, меньшее z, равна 1,12/ln z.

Таким образом, тест Миллера — Рабина может быть улучшен, если в качестве чисел а выбирать не любые случайные, а только простые числа, начиная с 2, 3, 5, 7,....

  • [1] ' Терехов А. А. Криптографическая защита информации : конспект лекций. СПб.: СПбГУ,кафедра системного программирования, 1999. URL: http://vvvv.ict.edu.ni/ft/002384/crypto.pdf
  • [2] Фороузан Б. Л. Криптография и безопасность сетей. М. : Бином. Лаборатория знаний,2010.
  • [3] Фороузан Б. Л. Криптография и безопасность сетей. М. : Бином. Лаборатория знаний,2010.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >