Математика. Часть 1. Алгебра и аналитическая геометрия. Красильщик И.С - 92 стр.

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

§19. Кольцо целых чисел 91
Предложение 2. Пусть m и n — целые числа и n 6= 0. Тогда существует
единственная пара таких целых чисе л q и r, что
m = qn + r, 0 6 r < |n|. (2)
Число q называется (неполным) частным от деления m на n, а r — остат-
ком.
Если в равенстве (2) r = 0, то говорят, что m делится на n (или кратно n).
В этом случае n называется делителем числа m. В этом случае неполное
частное называется просто частным.
Определение 13. Целое число p > 1 называется простым, если оно де-
лится только на себя и на единицу.
Пример 27 (первые 10 простых чисел). Вот пе рвые 10 простых чисел: 2,
3, 5, 7, 11, 13, 17, 19, 23 , 29.
Теорема 1 (теорема Евклида). Множество простых чисел бесконечно.
Теорема 2 (основная теорема арифметики). Любое натуральное чис-
ло n > 1 единственным образом разлагается на простые множители. Точнее,
существует единственный набор таких простых чисел p
1
< p
2
< ··· < p
k
, что
n = p
i
1
1
p
i
2
2
. . . p
i
k
k
, 0 < i
1
, . . . , i
k
∈ N. (3)
Замечание. Числа вида pq, где p и q — различные прос т ые числа, исполь-
зуются для создания так называемых RSA-кодов (см. ниже пример 28), широ-
ко применяющихся в практике защиты данных. Чем больше p и q, тем слож-
нее расшифровать код. В свою очередь, «инструментом» получения больших
простых чисел служит одна из самых известных т еорем арифметики.
Теорема 3 (малая теорема Ферма). Пусть p — прост о е число и a — нату-
ральное число, не делящееся на p. Тогда a
p−1
− 1 делится на p.
Малая те о рема Ферма важна для теории чисел. Н а пример, с её помощью
можно найти признаки делимости на все простые числа, кроме 2 и 5.
Пример 28 (RSA-коды). Криптографическая система RSA (название со-
ставлено из первых букв фамилий её создателей — Rivest+Shamir+Adleman)
является классическим примером так называем ых с ис т ем с открыт ым и клю-
чами и основана на сле дующей схеме.
Каждый абонент строит свою пару открытых и се кретных ключей. Для
этого берутся два больших простых числа p и q и в ычисляются произведе-
ние n = pq и ϕ(n) = (p − 1)(q − 1). Затем наугад выбирается число e, не
имеющее общих делителей с ϕ(n), и строится число d, обладающе е свойством
остаток от деления ed на ϕ(n) равен 1.
§19. Кольцо целых чисел                                                     91

   Предложение 2. Пусть m и n — целые числа и n 6= 0. Тогда существует
единственная пара таких целых чисел q и r, что
                          m = qn + r,              0 6 r < |n|.             (2)
   Число q называется (неполным) частным от деления m на n, а r — остат-
ком.
   Если в равенстве (2) r = 0, то говорят, что m делится на n (или кратно n).
В этом случае n называется делителем числа m. В этом случае неполное
частное называется просто частным.
  Определение 13. Целое число p > 1 называется простым, если оно де-
лится только на себя и на единицу.
   Пример 27 (первые 10 простых чисел). Вот первые 10 простых чисел: 2,
3, 5, 7, 11, 13, 17, 19, 23, 29.
  Теорема 1 (теорема Евклида). Множество простых чисел бесконечно.
   Теорема 2 (основная теорема арифметики). Любое натуральное чис-
ло n > 1 единственным образом разлагается на простые множители. Точнее,
существует единственный набор таких простых чисел p1 < p2 < · · · < pk , что
                    n = pi11 pi22 . . . pikk ,   0 < i1 , . . . , ik ∈ N.   (3)
   Замечание. Числа вида pq, где p и q — различные простые числа, исполь-
зуются для создания так называемых RSA-кодов (см. ниже пример 28), широ-
ко применяющихся в практике защиты данных. Чем больше p и q, тем слож-
нее расшифровать код. В свою очередь, «инструментом» получения больших
простых чисел служит одна из самых известных теорем арифметики.
  Теорема 3 (малая теорема Ферма). Пусть p — простое число и a — нату-
ральное число, не делящееся на p. Тогда ap−1 − 1 делится на p.
  Малая теорема Ферма важна для теории чисел. Например, с её помощью
можно найти признаки делимости на все простые числа, кроме 2 и 5.
   Пример 28 (RSA-коды). Криптографическая система RSA (название со-
ставлено из первых букв фамилий её создателей — Rivest+Shamir+Adleman)
является классическим примером так называемых систем с открытыми клю-
чами и основана на следующей схеме.
   Каждый абонент строит свою пару открытых и секретных ключей. Для
этого берутся два больших простых числа p и q и вычисляются произведе-
ние n = pq и ϕ(n) = (p − 1)(q − 1). Затем наугад выбирается число e, не
имеющее общих делителей с ϕ(n), и строится число d, обладающее свойством
                  остаток от деления ed на ϕ(n) равен 1.

Страницы