Свойства делимости целых чисел

 

Два числа a и b называются взаимно простыми если их НОД = 1

 

(a1,a2,….,an)= НОД

 

(a1,a2) = d1

 

(a3,d1) = d2

 

…………..

 

(dn-3,dn-1) = dn

 

a1*a2= k*d

 

Теорема разложения целых чисел (главная теорема арифметики)Любое составное число m можно однозначно представить в виде произведения простых сомножителей p, m = p1*p2*…..*pk

Эта теорема имеет большое прикладное значение в криптографии.

 

Обозначения:

 

m – составное число

 

p - простое

 

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

1)когда все сомножители разные

 

2) когда есть кратные сомножители

 

Пример: m= 720


 

Применим школьный алгоритм разложения – последовательное деление на возрастающие простые сомножители

720 2

 

360 2

 

180 2

 

90 2

 

45 3

 

15 3

 

5 5

 

Кратность указывается с помощью верхнего индекса 720 = 24*32*5 -

такая форма носит название – каноническое разложение на простые сомножители.

 

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

С помощью такого «школьного» алгоритма число с большим

 

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

 

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


 

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

Применение этой теоремы это – например для нахождение НОД. Т.е зная разложение, два числа, допустим a и b такие что:

 

 

 

Примечание: При получение разного числа сомножителей можно дописать так называемые «фиктивные» сомножители. н-р:

мы можем найти НОД по формуле:

 

От каждого разложение берется пара сомножителей, выбирается по показателям.

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

 

 

Пример

 

 

 

Т.е. 720= 24*32*5,

 

а 90= 2*32*5

 

Берем минимальные показатели :

 

- т.е. число 90 является НОД(d) чисел 90 и

 


720.

 

Аналогично НОК :


 

- т.е. число 720 является НОК(k) чисел 90 и 720.


 

 

Другая сфера приложения это н-р: Имеем некоторое большое число и имеем его разложение и на основе этого надо найти все его делители .

Если кратность в разложение есть то удобно использовать определенный способ нахождения всех делителей.

В общем случае когда составное число раскладывается по канонической формуле все делители можно найти по такой формуле (эта формула тоже обосновывается теоремой)

- мы имеем разложение

 

 

 

…………….

 

В нашем случае (про 720)

 

 

 

 

 

 

и подставляя всевозможные вариации этих значений мы и получим все делители.

т.е. d = 1,2,4,8,16…………

 

в нашем случае будет 30 делителей

 

Еще один вариант приложения разложения. По разложения можно найти сумму всех делителей ()

Принято обозначать сумму всех делителей нашего числа акак

 

 

 

 

Для нашего примера это будет выглядеть так: