Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 07.06.2024

Просмотров: 58

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Приклад -

a r , де r R .

 

 

 

 

 

 

 

 

 

 

 

 

Властивості мультиплікативних функцій

 

 

 

1. Для будь-якої мультиплікативної функції

f (1) = 1 .

 

Якщо розглянути a1 , a2 ,..., ak попарно простих чисел, то

f (a1 × a2 ×... × ak ) =

f (a1 )× f (a2 )×... × f (ak ), зокрема

 

f (p

α1

p

α2 ×... × p

k

αk )=

 

f

(p α1 )× f (p

 

α2 )×... × f (p

αk ).

 

1

 

2

 

 

 

 

 

 

 

1

 

 

 

2

 

k

 

Наприклад,

задамо

 

 

мультиплікативну

 

функцію

так:

f (1) = 1,

f (pα )= 2,

 

"a > 0 .

Тоді

для

довільного цілого

числа

a = p α1

× p

α2

×...× p

αk

 

a

 

> 0,

i =

 

будемо мати

 

,

i

1, k

 

1

 

2

 

 

 

k

 

 

 

 

 

 

 

 

 

 

 

 

 

f (p

α1

× p

α2 ×...× p

αk

)=

 

f (p

α1 )× f (p

α2 )×...× а(p

 

αk )= 2k ,

 

1

 

 

2

 

 

 

k

 

 

 

1

 

 

 

2

k

 

зокрема

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f (1) = 1, f (2) = 2, f (7) = 2,

 

f (9) = f (32 ) = 2,

 

f(14) = f (2 ×7) = f (2) f (7) = 4.

2.Добуток двох мультиплікативних функцій – функція мультиплікативна.

Нехай f (a) = f1 (a) f2 (a) – задана функція.

f(a1 × a2 ) = f1 (a1 × a2 ) f2 (a1 ×a2 ) = f1 (a1 ) f1 (a2 ) f2 (a1 ) f2 (a2 ) =

=( f1 (a1 ) f2 (a1 ))( f1 (a2 ) f2 (a2 )) = f (a1 ) f (a2 ) .

3. Нехай a = p1α1 × p2

α2

× ...× pk αk - довільне ціле число,

f (a) -

довільна мультиплікативна

функція, D | a -

множина

усіх

дільників a виду d = p1

β1

× p2

β2 × ...× pk βk , 0 £ βi

£ α i , i =

 

.

1,k

Тоді вірним буде таке:

 

 

 

 

 

 

∑ f (d ) = (1+ f ( p1 ) + f ( p12 ) + ... + f ( p1α1 ))´

D|a

´(1+ f ( p2 ) + f ( p22 ) + ... + f ( p2α2 ))´...

27

´(1+ f ( pk ) + f ( pk 2 ) + ... + f ( pk αk )) .

2.3.ПРИКЛАДИ МУЛЬТИПЛІКАТИВНИХ ФУНКЦІЙ

1.Кількість дільників числа a = p1α1 × p2 α2 ×...× pk αk .

Введемо мультиплікативну

функцію

f (a) =1 . Розглянемо

для цієї функції 3-ю властивість мультиплікативних функцій.

Ліва

частина: ∑ f (d ) = ∑1 = 1 +1 +1... становить

кількість

 

D|a

D|a

 

 

 

дільників числа a . Права частина: (1 + a1 )(1 + a2 )...(1+ ak ).

Отже,

кількість

дільників

числа a

дорівнює

добутку

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

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

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

τ (pα )= (α + 1) .

Для p простого числа кількість дільників дорівнює

τ ( p) = 1 +1 = 2 .

Приклад

Знайти кількість дільників числа:

1. a = 31; 2. a = 64 = 26 ; 3. a = 84 = 22 ×3 × 7 .

Розв’язання

1.

a = 31 – просте число. Отже, τ (31) = 1 +1 = 2 . Це числа 1

і 31.

a = 64 = 26 – степінь простого числа 2. Отже,

2.

28

τ (26 ) = 6 +1 = 7 .

3. a = 84 = 2

2 ×3 × 7 – число типу a = p α1

× p

α2

×...× p

αk ,

 

1

 

2

 

k

τ (22 ×3× 7) = τ (22 )×τ (3)×τ (7) = (2 +1)(1 +1)(1 +1) = 3× 2 × 2 = 12 .

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

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

увластивість 3. Отримаємо:

∑d = (1+ p1 + p12 + ... + p1α1 )×

D|a

´(1+ p2 + p22 + ... + p2α2 ) ×...×(1+ pk + pk 2 + ... + pk αk ) .

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

Використовуючи формулу суми геометричної прогресії для

n = ai +1,

(i =

 

) членів, отримаємо

 

 

 

 

 

1, k

 

 

 

 

 

S (p α1

× p

2

α2 ×...× p

 

αk )=

p1α1 +1 -1

×

p2

α2 +1 -1

×...×

pk αk +1 -1

.

k

 

 

 

 

 

1

 

 

 

 

 

p1 -1

 

p2 -1

 

pk -1

 

 

 

 

 

 

 

 

 

 

S (a)

–

 

мультиплікативна

функція

визначення суми

додатних дільників числа a = pα , α > 0 дорівнює:

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

Приклад

Знайти суму дільників числа:

1. a = 24 ×5 ×73 ×19 ; 2. a = 84 = 22 ×3 × 7 .

Розв’язання

1. S (24 ×5 ×73 ×19)= 25 -1 × 52 -1 × 74 -1 ×192 -1 = 1488000 ;

1

4

6

18

29

2. S (22 ×3 × 7)= 23 -1 × 32 -1 × 72 -1 = 5 ×8 × 48 = 160 . 1 2 6 12

3. Функція Ейлера та її властивості

Означення

Функція Ейлера визначає для довільного цілого додатного числа a кількість чисел з ряду цілих 0 £ bi £ a -1, взаємно

простих з числом a , тобто таких, що (a,bi ) = 1. Позначається функція Ейлера j(a).

Приклади j(1) =1 - за означенням.

a = 2, j(2) =1 , поперед числа 2 є одне число – 1; 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 – просте число, то увесь ряд

цілих чисел, менших за 13 є взаємно простий з ним.

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

степенем простого числа:

 

 

 

 

 

 

 

 

 

 

 

 

 

1) для a = p –

 

простого числа – j(p) = p1 - p0 = p -1 ;

 

 

 

2) для a = pα

–

 

степеня простого числа –

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

j(p) = pα 1

-

 

 

= pα - p

α−1 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

p

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Функція Ейлера є мультиплікативною функцією.

 

 

 

 

 

 

Розглянемо

 

 

канонічне

подання

довільного

 

цілого

a = p α1

× p

α2 ×...× p

 

αk

. Для довільного

цілого

функція

Ейлера

1

 

2

 

 

k

 

 

 

 

 

 

 

 

 

 

 

 

 

 

буде мати вигляд

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

α1

 

 

 

α2

αk

 

1

 

1

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

j(a) = j(p1

× p2

×... × pk

 

 

 

 

 

 

 

,

)= a × 1 -

 

1 -

 

... 1 -

 

 

 

 

 

 

 

 

 

 

 

 

p1

p2

pk

 

30

Смотрите также файлы