Информатика и выч. техника \ Криптография

Застосування теорії чисел в криптографії, страница 2

1.3. Найменше спільне кратне (НСК).

Дані числа . Кожне з чисел, що є кратним кожному з даних чисел, носить назву їхнього спільного кратного. Найменше із усіх кратних називається найменшим спільним кратним даних чисел.

Нехай , тоді і (властивості НСД, 2.) Нехай - деяке кратне та , тобто і . Оскільки , то повинно ділитися на , тобто . Для СК буде вірна формула:

Найменше значення СК буде за умови, що , тобто для НСК виконується формула:

, тоді

Теореми:

1. Сукупність спільних кратних чисел та співпадає з сукупністю кратних для їх НСК.

2. НСК та дорівнює відношенню добутку цих чисел до їх НСД.

1.4 Прості числа.

Вислови:

1. Число 1 має тільки один додатній дільник – самого себе. Одиниця стоїть осторонь у ряду натуральних чисел.

2. Найменший дільник, що не дорівнює 1, для будь якого цілого числа є число просте. (Візьмемо число і його найменший дільник . Допускаємо, що . Тоді ділиться на і на , тобто має дільник, менший за , що є протиріччям вихідному посиланню.)

3. Найменший дільник, що не дорівнює 1, для будь якого складеного цілого числа не перевищує значення . (Нехай . Оскільки - найменший дільник, то . Отже , або .

4. Простих чисел безкінечно багато.

5. Решето Ератосфена для вибору простих чисел, які не перевищують даного числа N.

1) обираємо перше просте число – . Викреслюємо всі цілі числа з інтервалу , кратні 2.

2) обираємо наступне найменше просте число . Викреслюємо всі цілі числа з інтервалу , кратні 3.

3) Повторюємо процес з наступним .

4) Обираючи чергове , звертаємо увагу на те, що кандидатів на ви креслення слід розглядати з числа , бо до цього числа всі складені викреслені, як такі, що кратні простим числам, меншим за .

5) Викреслення можна зупинити, коли перевищить . Усі кратні числа на той час будуть викреслені.

1.5 Єдиність розкладання довільного цілого числа на прості множники.

Базові вислови для складених чисел:

· Довільне ціле або взаємо просте з даним простим числом , або ділиться на нього.

· Якщо добуток декількох множників ділиться на просте число , то хоча б один з множників теж ділиться на .

· Довільне ціле число можна розкласти на добуток простих множників єдиним способом. (враховуючи комутативність множення)

· У наведеному розкладанні деякі з множників можуть повторюватися не один раз. Позначивши через тільки різні множники, а через відповідні кратності входження множників до числа , запишемо канонічне розкладання довільного цілого числа на множники:

· Нехай - канонічне розкладання довільного цілого числа . Тоді усі дільники цього числа можна подати у канонічному вигляді:

, де

· У відповідності до вищенаведеної формули, кількість дільників довільного цілого числа можна знайти так:

· Розглянемо канонічне розкладання довільних цілих:

Тоді НСД цих чисел у канонічному вигляді прийме вигляд:

а НСК -

· Сукупність спільних дільників декількох цілих чисел співпадає з кількістю дільників їх НСД.

· НСК декількох взаємо простих чисел дорівнює їх добутку, а сукупність кратних декількох чисел співпадає з сукупністю кратних їх НСК.

Приклад:

Дані 2 числа 12348 та 867. Побудувати канонічну форму цих чисел, знайти їх НСД та НСК.

Розв’язання:

12348 за ознаками ділення ділиться на 4(2²) і на 9 (3²)

- канонічне розкладання першого числа. Дільників у першого числа буде

- канонічне розкладання другого числа. Дільників у другого числа буде - 17, 343 та 51

НСД -

НСК -

1.6 Неперервні дроби.

Будь яке дійсне число можна подати, як неперервний дріб. Нехай - найбільше ціле число, . Тоді довільне неціле число можна подати так: . Відповідно, , якщо вони не цілі, можна подати: