Файл: M51_21_-_kopia.pdf

86 

1 

≤ 

β

1

(n)

≤ 

β(n) =[log

2

(n)]+1, т.е.β

1

(n) = O(log

2

(n)) 

 
Відзначимо, що функція β

1

(n) може бути рекурсивно задана наступним 

чином [4]: 

β

1

(0)=0; β

1

(1) = 1; 

β

1

(n)        =    

β

1

(2n) = β

1

(n); 

β

1

(2n+1) 

= β

1

(n) + 1. 

 
3. Функція β

0

 (n)  

Функція  визначена  для  цілого  додатного  n,  і    β

0

(n) 

є  кількість  «0»  в 

двійковому  поданні  числа  n.  Функція  β

0

(n)  не  є  монотонно  зростаючою 

функцією. Для всіх  

 
                    n =2

k

-1,   

β

0

(n)=0 

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

β(n) = β

0

(n) + β

1

(n). 

Для  подальшого  аналізу  представляє  також  інтерес  визначення 

середнього  значення  функції  β

1

(n) 

для  n = {0,1,…,N}, де  N=2

k

-1 (

тобто 

двійкове подання числа N займає k розрядів), позначимо його через βs (N). 

Тоді   

∑

=

β

+

=

β

N

0

m

s

s

)

m

(

1

N

1

)

N

(

 . 

Оскільки  кількість  чисел,  що  мають  L  одиниць  в  K  розрядах  дорівнює 

кількості сполучень з L по K, то тоді: 

1

K

-1

k

0

L

L

K

k

1

L

-1

L

-1

K

k

1

L

L

K

N

0

m

s

2

*

K

C

*

K

C

L

K

*

L

C

*

L

(m)

β

−

=

=

=

=

=

=

=

=

∑

∑

∑

∑

,  

 
оскільки N=2

k

-1, 

то: 

2

β(N)

2

1)

(N

log

2

K

1

1

2

2

*

K

(m)

β

1

N

1

(N)

β

2

K

1

k

N

0

m

s

s

=

+

=

=

+

−

=

+

=

−

=

∑

                    (11.1). 

 
Ідея  швидкого  алгоритму  розв'язання  задачі  про  зведення  в  ступінь 

полягає  у  використанні  двійкового  розкладання  числа  n  і  обчислення 
відповідних ступенів шляхом повторного зведення в квадрат [5].  

87 

Нехай, наприклад,  n=11,  
 
 

тоді    x

11

 = x

8

 * x

2

 * x

1

,  x

4

 = x

2

 * x

2

і   x

8

 = x

4

 * x

4

. 

 
Алгоритмічна  реалізація  ідеї  вимагає  послідовного  виділення  бітів, 

зведення  х  у  квадрат  і  множення  y  на  ті  ступені  х,  для  яких  у  двійковому 
розкладанні n присутня одиниця. 

 
XstK (x,n;y); 

z 

←

 x; 

y 

←

 1; 

Repeat 

If (n mod 2) = 1 

then  

y 

←

 y*z; 

z 

←

 z*z; 

n 

←

 n div 2; 

Until n = 0 
Return (y) 
End 
 
Одержимо  функцію  трудомісткості  даного  алгоритму,  використовуючи 

введені  раніше  позначення  і  прийняту  методику  рахунків  елементарних 
операцій  у  формальній  системі  процедурно-орієнтованої  мови  високого 
рівня: 

Fa(n) = 2 + β(n)*(2+2+2+1) + β

1

(n)*(2)= 7*β(n) + 2*β1(n)+2      (11.2) 

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

поданні    n  –  β(n),  а  кількість  повторень  операції  y 

←

    y*z  –   

кількістю 

одиниць в цьому поданні – β

1

(n), що й відображає формула 11.2.  

Визначимо  трудомісткість  алгоритму  для  особливих  значень  n,  такими 

особливими значеннями є випадки, коли n=2

k

або n=2

k

 – 1: 

 
– 

в випадку коли  n=2

k 

,  то β

1

(n)=1 і   Fa(n)= 7*β(n) + 4; 

 
– 

в випадку коли n=2

k

 -

1, то β

1

(n)= β(n) і  Fa(n)= 9*β(n) + 2. 

88 

Якщо  показник  ступеня  заздалегідь  невідомий,  то  можна  отримати 

середню  оцінку,  в  припущенні,  що  подання  числа  n  займає  не  більше  k 
двійкових розрядів, тобто n <2k або log2n <k. Тоді за формулою (11.1)  

 
β

s

(N) = β(N)/2, где N=2

k

-1,  

 
звідки: 
 

Fa(n) 

≤ 

7*β(N) + 2*β

s

(N)+2 = 8*β(N) + 2 =8*([log

2

(n)]+1)+2 = 8*k +2. 

 
Таким  чином,  кількість  операцій,  виконуваних  швидким  алгоритмом 

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

Введення  спеціальних  функцій  β

1

(n)  і  β(n)  дозволило  отримати  точне 

значення функції трудомісткості цього алгоритму.  

11.2 

Відомості з теорії простих чисел 

 
а) Порівняння 

Кажуть,  що  два  числа  a  і  b  можна  порівняти  по  модулю  c,  якщо  вони 

дають при діленні на c рівні залишки. 

Операція  отримання  залишку  від  ділення  a  на  c  записується  у  вигляді:  

а modc = d, що еквівалентно поданням: a = k * c + d;  

Порівнянність двох чисел по модулю означає, що: 
а modc = b modc і записується як (a 

≡

 b) modc 

 
Приклади: (13 

≡

 6) mod7,  (17 

≡

 22) mod5 

Якщо, а modc = 0, то, число а ділиться на c без залишку: (a 

≡

 0)modc 

 
б) Прості числа 

Число  p  називається  простим,  якщо  вона  не  має  інших  дільників,  крім 

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

Безліч простих дільників, доказ належить Евкліду: 
Нехай p1, ..., pk, – всі прості числа, але тоді число  

89 

а = (p1 * p2 * ... * pk + 1)  

 
у залишку від ділення на будь-яке з них дає одиницю  

 
a mod pi = 1 

і отже є простим.  

 
в) Функція π (n) 
Функція π (n) в теорії простих чисел позначає кількість простих чисел, 

не переважаючих n. 

Наприклад π (12) = 5, оскільки існує 5 простих чисел, не переважаючих 

12, 

а саме: 2,3,5,7,11. 

Асимптотична  поведінка  функції  π  (n)  було  отримано  наприкінці  XIX 

століття [5] і пов'язане з функцій інтегрального логарифма: 

 
Для великих n  –  

π

(n)  

≈

   li(n)  

≈

   n / ln n. 

 
Отриманий  результат  означає,  що  прості  числа  не  так  вже  «рідкісні», 

ймовірність того, що серед взятих випадково ln n чисел, що не перевершують 
n, 

одне з них просте, достатньо велика.  

Відзначимо, що це використовується при пошуку великих простих чисел 

в ймовірнісному тесті Міллера-Рабіна [5]. 

11.3 

Питання для самоконтролю 

 
1) 

Функції  підрахунку  кількості  бітів  і  кількості  одиниць  в  двійковому 

поданні числа та їх властивості. 

2) 

Алгоритм швидкого зведення в ступінь. 

3

) Аналіз трудомісткості алгоритму швидкого зведення в ступінь; 

4

) Поняття напівгрупи, моноїд і групи, приклади груп. 

5) 

Порівняння та відомості з теорії простих чисел. 

90 

12.

КРИПТОСИСТЕМА RSA 

І

ТЕОРІЯ

АЛГОРИТМІВ 

12.1 

Мультиплікативна група відрахувань за модулем n 

 
Розглянемо деякі групи, утворені на множині відрахувань за модулем n: 

Нехай n – ціле додатне число, тоді множина залишків від ділення будь-якого 
цілого додатного числа на n називається множиною відрахувань за модулем n 
і позначається як Zn: 

 
Z

n

 = { 0, 1, 2,…, n-1} 

 
Якщо як групову операцію розглянути операцію додавання за модулем n: 

(+  modn), 

то  множина  Zn  утворює  з  цією  операцією  і  нулем,  в  якості 

«

одиниці»,  групу  {Z

n

,  +  modn,  0}, 

яку  називають  адитивною  групою 

відрахувань за модулем n.  

Зворотним елементом для a 

∈

 Zn 

буде елемент a

-1

 = (n – a) modn 

Якщо як групову операцію розглянути операцію множення за модулем n: 

(*modn), 

то множина  Z'n утворює з  цією операцією і одиницею групу {Z'

n

, 

*modn,  1}, 

яку  називають  мультиплікативною  групою  відрахувань  за 

модулем n, що позначається звичайно як Zn*. 

Зворотний  елемент  в  групі  Zn*  існує,  тільки  якщо  НСД  (z,  n) = 1  

Кількість  чисел, взаємопростих з n, і, отже, кількість елементів в  групі Zn* 
може бути отримано за формулою Ейлера [5, 9]: 

Z

n

*

 = 

ϕ

(n) = n*П (1-1/p

i

),  

де p

i

 – 

прості дільники числа n. 

Наприклад: 

ϕ

(15) = 15*(1-1/3)(1-1/5) = 15*2/3*4/5=8 

Якщо число n – просте число, тобто  n = p, то 

ϕ

(p) = p(1-1/p) = (p-1). 

Знаходження 

зворотного 

елементу 

для 

деякого 

елемента 

мультиплікативною групи по множенню зазвичай виконується за допомогою 
розширеного алгоритму Евкліда [5]. 

Зауважимо, що теорема про єдинство зворотного елемента в групі Zn* ,  

а  1  і  (n – 1)  є зворотними самі собі, тобто: 

1*1 = 1modn

і  (n-1)*(n-1) = (n

2

 – 2n +1)modn = 1