Файл: Теорія чисел в криптографії.pdf

Питання 3. Приклади мультиплікативних функцій.

входять до канонічного розкладу числа, збільшених на 1. Позначимо функцію визначення кількості дільників числа, як t(a) . Тоді:

t(a) = (1 + a1 )(1 + a2 )...(1 + ak )

t(a) - мультиплікативна функція, для якої кількість дільників числа a = pα , за умови, що α > 0 , p - просте число, дорівнює

t(pα )= (a +1)

Приклад.

Знайти кількість дільників числа 1. a = 24 ×5 ×73 ×19 ; 2. a = 84 = 22 ×3 × 7

Розв’язання: 1. t(a) = 5 × 2 × 4 × 2 = 80 ; 2. t(a) = 3 × 2 ××2 = 12 ,

Приклад 2.

Сума додатних дільників числа a = p1α1 × p2 α2 ×...× pk αk .

Введемо мультиплікативну функцію f (a) = a і підставимо її у властивість 3. Будемо

мати:

∑ d = (1+ p1 + p12 + ...+ p1α1 )(1+ p2 + p2 2 + ...+ p2α2 )× ...× (1+ pk + pk 2 + ...+ pk αk )

D|a

Ліворуч у формулі стоїть сума усіх додатніх дільників числа a . Позначимо цю суму S (a) . Праворуч у дужках маємо суми геометричних прогресій із знаменниками

S (pα )= pα+1 -1 p -1

21

Сума власних додатних дільників числа a може бути:

1.менша, ніж саме число a , число a в цьому разі носить назву „ недостатнє” число;

2.більша, ніж саме число a , тоді a - „ надлишкове” число;

3.в окремих випадках – рівна самому числу a .

З самим числом a повна сума додатних дільників числа a буде в цьому випадку дорівнювати 2a .

Числа, для яких S (a) = 2a носять назву „ досконалі” числа. Для досконалих чисел вірна теорема:

Число a буде досконалим тоді і тільки тоді, коли воно має вигляд a = 2k −1 (2k -1); k ³ 2;

(2k -1) - просте число.

В теорії чисел доводиться, що число (2k -1) буде простим тільки, коли k є простим число. Числа (2k -1) в теорії чисел носять назву прості числа Мерсенна.

Кожне число Мерсенна відповідає новому досконалому парному числу. Приклад.

Візьмемо k = 7 P = 27 -1 =127 - просте число Мерсенна. a = 26 (27 -1)= 26 ×127 = 8128

Кількість додатних дільників числа обчислимо за формулою:

a = 2, j(2) =1 - перед 2 є одне просте число – 1.

22

a = 3, j(3) = 2 - взаємно прості з 3 – 1,2 a = 4, j(4) = 2 - взаємно прості з 4 – 1,3

a = 5, ϕ (5) = 4 - взаємно прості з 5 – 1,2,3,4

a =13, j(13) =12 - оскільки 13 – просте, то увесь ряд чисел до цього числа є взаємно

простий з ним.

Функція Ейлера для простого числа та для числа, яке є степенем простого числа:

Кожний дільник є цілим числом, до якого можна застосувати функцію Ейлера:

j(di ); i =1,t(a)

Вірною є така теорема:

∑ j(d ) = a

D|a

цим числом найбільший спільний дільник d , тобто (a ,mi ) = d , дорівнює

23

= j a k d

Приклад.

Знайти кількість натуральних чисел, менших за a = 450 і таких що мають з цим числом спільний дільник d = 15

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

a = 450 =

30

d 15

Отже кількість чисел, менших за 450 і таких, що мають НСД з 450 рівним 15, буде k = j(30) = j(2 ×3×5) = (2 -1)(3 -1)(5 -1) = 8

Висновки Після вивчення теми 2 ви повинні знати такі факти:

-функція виділення цілої частини дійсного числа х повертає найбільше ціле число, яке не перевищує х,;

-функція виділення дробової частини дійсного числа х повертає різницю між числом х та його цілою частиною;

-функція f (a) називається мультиплікативною, якщо для неї виконуються 2

формулою:

t(a) = (1 + a1 )(1 + a2 )...(1 + ak )

-функція S (a) обчислення суми усіх дільників числа a = p1α1 × p2α2 × ...× pk αk є функцією мультиплікативною і обчислюється за формулою:

-числа, для яких S (a) = 2a носять назву „ досконалих” чисел;

-числа (2k -1) можуть бути простими тільки, коли k - просте число, такі числа носять назву простих чисел Мерсенна;

- функція, яка обчислює кількість чисел, взаємопростих з даним цілим

-кількість натуральних чисел mi , які не перевищують число a , ( mi £ a ), і мають з цим числом найбільший спільний дільник d , тобто (a ,mi ) = d , дорівнює

24