Теорія чисел в криптографії

Питання 5. Ознаки подільності чисел. Загальні принципи:

Будь-яке ціле (n +1)-значне число можна подати у десятковій системі так:

N =10n a

n

+10n−1 a

n−1

+ ...+10

2 a

2

+10a + a

0

;

0 £ a

i

£ 9; i =

0,n

1

Застосовують ще один запис числа N як послідовності цифр:

N = an an−1 ...a2 a1ao ; 0 £ ai £ 9; i = 0,n

Розв’язати питання подільності такого числа на будь-яке інше число k можна розглянувши послідовність залишків від ділення степенів основи числення на k :

r

= a

0

- k × q

0

; r =10 - k × q ; r

=102 - k × q

2

; ...;r =10n - k × q

n

;

0

1

1 2

n

де

- відповідні неповні частки від ділення 10i , i =

на k . Очевидно, що

q

0

,q ,...,q

n

0,n

1

залишки ri ,

i =

не перевищують числа k

за значенням і за кількістю різних значень.

0,n

Відповідно до властивостей такої послідовності відносно k можна вивести відповідне правило подільності.

а) Подільність цілого числа на 2:

N =10n a

n

+10n−1 a

n−1

+ ...+102 a

2

+10a + a

0

1

Усі доданки крім останнього діляться на 2, отже для подільності N на 2 необхідно, щоб

остання цифра числа a0

ділилася на 2 (була парною).

б) Подільність на 3 та на 9:

+

99...9

+ ...+ (99 +1)a

+ (9 +1)a + a

=

N =

99...9 +1 a

n

+1 a

n−1

2

0

123

123

1

n

n−1

+ 9...9a

+ ...+ 99a

+

(a

+ a

+ ...+ a

+ a + a

)

= 9...9a

n

n−1

2

9a +

n

n−1

2

0

{

{

1

1

n

n−1

Перший доданок ділиться на 3 та на 9, отже для подільності N на 3 або на 9 необхідно, щоб сума цифр числа N ділилася на 3 або на 9 відповідно.

в) Подільність на 4:

N = (10n an +10n−1 an−1 + ...+102 a2 + 8a1 )+ (2a1 + a0 )

Отже для подільності N на 4 необхідно, щоб другий доданок 2a1 + a0 ділився на 4. Наприклад 183 546 976 ділиться на 4 бо 7 × 2 + 6 = 20M4

в) Подільність на 5:

N =10n an +10n−1 an−1 + ...+102 a2 +10a1 + a0

Усі доданки крім останнього діляться на 5, отже для подільності N на 5 необхідно, щоб остання цифра числа a0 ділилася на 5.

г) Подільність на 8:

N = (10n an +10n−1 an−1 + ...+ 96a2 + 8a1 )+ (4a2 + 2a1 + a0 )

Отже для подільності N на 8 необхідно, щоб другий доданок 4a2 + 2a1 + a0 ділився на 8. Відома і інша ознака подільності на 8 – для того, щоб все число N = an an−1 ...a2 a1ao

ділилося на 8 необхідно, щоб число a2 a1a0 ділилося на 8.

11

Для визначення подільності на 8 тризначного числа зручно розглянути його, як

10(10a2 + a1 )+ a0 = 8(10a2 + a1 )+ 2(10a2 + a1 )+ a0

Якщо 2(10a2 + a1 ) + a0 ділиться на 8, то і все число ділиться на 8.

Такий спосіб можна застосовувати до чисел, які отримуємо під час перевірки на подільність не однократно, до тих пір, поки подільність не стане очевидною.

Приклад: Дослідити число 195 347 839 на подільність на 8.

Розв’язання

Визначимо, чи ділиться 839 на 8:

839 =10 ×83 + 9 2 ×83 + 9 =175 = 10 ×17 + 5 2 ×17 + 5 = 39 10 ×3 + 9

10↔2	10↔2	10↔2
6 + 9 =15 =10 ×1+ 5 2 + 5 = 7
10↔2	10↔2

За ознакою число 839 не ділиться на 8 без залишку. Залишок має значення 7. Отже і вихідне число N = 195347839 при діленні на 8 має залишок 7.

Дійсно, 195347839 = 24 418 479 7 8 8

д) Подільність на 7:

Для формулювання ознаки подільності на 7 дослідимо послідовність залишків від ділення степенів числа 10 на 7:

10 = 7 ×1

+ 3, q

=1, r = 3;

102

=100 = 7 ×14 + 2, q

2

= 14,

r

= 2;

1

1

2

103

=1000 = 7

×142 + 6, q

3

= 142, r = 6 або 103 =1000 = 7 ×143 -1, q

3

= 143, r

= -1

3

3

104

=10

000 =

7 ×1428 + 4, q4 =1428, r4 = 4; 105 =100 000 = 7 ×14285 + 5, q5 =14285, r5 = 5;

106

=1000000 = 7 ×142857 +1,

r =1

6

Після r6

значення залишків будуть повторюватися,

починаючи з

r1 = 3 . Тим самим

отримана послідовність вміщує у собі усі можливі ненульові залишки від ділення довільного степеня числа 10 на 7.

На увагу заслуговують 2 залишки –												залишок числа 103 =1000 : r											= -1 і залишок числа
																						3
106 =1000000 : r				=1 .
		6
Якщо цифрову послідовність довільного натурального числа																					N =									розбити
																								an an−1 ...a2 a1a0
на трійки, починаючи з наймолодших позицій, то число набуде вигляду:
N = ...+106 a	a	a	6	+103 a	a	a	3	+ a a a		0	= ...+ (7 × q		6	+1)a	a	a	6	+ (7 × q	3	-1)a		a	a		3	+ a a a		0	=
8	7			5	4			2	1					8	7						5	4				2	1

= 7 × N1 + ...+ a8 a7 a6 - a5 a4 a3 + a2 a1a0

Тут 7 × N1 - доданок всіх елементів розкладення числа, які мають у собі множник 7,

... + a8 a7 a6 - a5 a4 a3 + a2 a1a0 - сума залишків від ділення степенів числа 10, кратних 3, на 7. З такого подання числа можна вивести ознаку ділення на 7:

Для того щоб узнати чи ділиться конкретне число на 7 без залишку необхідно попередньо числову послідовність даного числа розбити на трійки, починаючи з правого боку, понумерувати трійки, скласти отримані тризначні числа з непарними номерами окремо, з парними – окремо. Далі від суми тризначних чисел з непарними номерами відняти суму тризначних чисел з парними номерами.

Якщо отримане число ділиться на 7, то вихідне число ділиться на 7.

Якщо отримане число при діленні на 7 має ненульовий залишок, то такий залишок буде мати і вихідне число.

12

Приклад: Перевірити, чи ділиться на 7 число 24 135 897 155.

Розв’язання

Розбиваючи число на трійки з правого боку, маємо цифри: 155, 897, 135, 24. З них непарні: 155 і 135, парні – 897 і 24. Сумуємо їх: 155+135=290 – сума непарних трійок; 897+24=921 – сума парних трійок, 290 − 921 = −631- число на 7 не ділиться. Має залишок r = −1 або r = 6

Отже вихідне число має залишок від ділення на 7 теж 6 (або -1).

Дійсно 24135897155 = 3447985307 6 або 24135897155 = 3447985308 - 1

7	7	7				7
е) Подільність на 19:
Для визначення ознаки подільності цілого числа N =						на 19 подамо вихідне
					an an−1 ...a2 a1a0
число таким способом:	N =10 A + a0 ,	A =		.
			an an−1 ...a2 a1

Якщо число N ділиться на 19, то можна записати: 10 A + a0 = 19 × q , де q - повна частка.

Не порушуючи рівності і з ціллю виділення ліворуч частини, що ділиться на 19 умножимо отриману рівність на 2:

2(10 A + a0 ) =19 × q × 2; 19 A + (A + 2a0 ) = 19 × q × 2

Отже, для того, щоб число N = an an−1 ...a2 a1a0 ділилося на 19 необхідно, щоб число (A + 2a0 ) ділилося на 19, A = an an−1 ...a2 a1 .

Приклад

Перевірити, чи ділиться число 12 345 687 на 19.

Розв’язання

N =12345687; A = 1234568, a0 = 7, A + 2a0 =1234568 +14 = 1234582; A = 123458, a0 = 2, A + 2a0 = 123458 + 4 =123462

A = 12346, a0 = 2, A + 2a0 =12346 + 4 = 12350; A = 1235, a0 = 0, A + 2a0 =1235 + 0 =1235;

A = 123, a0 = 5, A + 2a0 =123 +10 =133;

A = 13, a0 = 3, A + 2a0 = 13 + 6 = 19

Остання сума ділиться на 19, отже і вихідне число ділиться на 19

Висновок – число 12 345 687 ділиться на 19 - 12345687 = 649773 .

19

13

Питання 6 Неперервні дроби.

Будь-яке дійсне число α R можна подати, як неперервний дріб. Нехай q1 - найбільше

ціле число,

q1 ≤ α .

Тоді довільне неціле

число α R можна подати так:

α = q +

1

,

α > 1. Відповідно, α , α ,...α

s−1

R , якщо вони не цілі, можна подати:

1

α 2

2

2

3

α 2 = q2

+

1

, α3 > 1

α3

α3 = q3

+

1

, α 4 > 1

1

α 4

, або α = q1 +

q2

+

1

.....................................

q3

+ .....

α s−1 = qs−1

+

1

, α s > 1

M

α s

1

KK +

qs−1

+

1

α s

Якщо α - ірраціональне число, то таке подання буде безкінечним.

Якщо ж α = a Q , то неперервний дріб буде скінчений і розкладення можна отримати за b

допомогою алгоритму Евкліда:

a = bq + r ;

a

= q +

1

1

1

b

1

b

r1

= r

+ r ;

rn−2

= q

+

1

b

1

r

q

b = r1q2

+ r2 ;

= q2

+

n−2

n−1

n

n

rn−1

n

rn−1

r

r1

rn .

1

r2

= r q

rn−1

= q

r1

1

r

n+1

;

n+1

r = r q

+ r ;

= q

+

n−1

n

r

3

3

1 2

3

r

r2

n

2

r3

.....................................

Тоді

a

= q +

1

b

1

+

1

q2

q3

+ ...

M

... +

1

qn

+

1

qn+1

Використовуючи розкладання числа за алгоритмом Еікліда, неперервний дріб можна подати, як скінчену послідовність неповних часток.

a = [q1 ,q2 , ...,qn ,qn+1 ] b

14

Зробимо позначення:

d

= q ; d

= q

+

1

;

d

= q +

1

;....; d

= q

+

1

1

2

3

s

1

1

q2

1

q2 +

1

1

+

1

q2

q3

q3

+ ...

M

...... +

1

qs−1 +

1

qs

Такі дроби носять назву підходящі дроби

Щоб

скласти

алгоритм обчислення

будь-якого підходящого дробу di , позначимо

P = 1,

Q

= 0 та

a

=

Ps

. Зауважимо,

що у кожному підходящому дробу d

достатньо

0

s

0

b

Qs

qs−1 замінити на qs−1 +

1

. Тоді

qs

d

=

q1

=

P1

;

d

= q +

1

=

q1 × q2 +1

=

P1q2 + P0

=

P1 × q2 + P0

=

P2

1

2

1 Q1

1

q2

q2

1× q2 + 0 Q1 × q2 + Q0

Q2

1

q

+

P

+ P

q P + P + P q

(P q

+ P )+ P

q P + P

q

q

q

2

3

1

0

2

3

2

d3

=

=

3 1

1

0

=

3

1

0

1

=

3 2

1

q

q Q + Q + Q q

q

(Q q

1

2

3

2

+ Q ) + Q q Q + Q

3 1

1

0

3

1

0

1

3 2

1

q2 +

Q1

+ Q0

q3

.................................................................................................................

δ s

=

qs × Ps −1 + Ps −2

=

Ps

Qs

qs × Qs −1 + Qs−2

Отже, для обчислення будь-якого di ,

i > 1 нам необхідно обчислити

Pi = qi × Pi−1 + Pi−2 та

Qi = qi × Qi−1 + Qi−2

Для обчислення зручно застосувати схему:

і

0

1

2

....

і-2

і-1

і

...

n-1

n

qi

q1

q2

....

qi−2

qi−1

qi

....

qn−1

qn

Pi

1

q1

P2

....

Pi−2

Pi−1

Pi

....

Pn−1

a

Qi

0

1

Q2

....

Qi−2

Qi−1

Qi

....

Qn−1

b

Останні

2

стовбці

використовуються

тільки

у разі,

коли

дріб a =

a

такий,

що не

b

скорочується.

Приклад. Розкласти у неперервний дріб

151

.

13

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

151

дріб такий, що не скорочується. Розкладемо за алгоритмом Евкліда:

13

151 = 13 ×11 + 8

q1 = 11

13 = 8 ×1 + 5

q2 = 1

8 = 5 ×1 + 3

q3 = 1

15

5 = 3 ×1 + 2

q4

= 1

151

1

3 = 2 ×1 +1

q5

= 1

Отже,

= 11+

1

2 = 1× 2

q6

= 2

13

1

+

1+

1

1+

1

1

1+

2

+ 0

151 = [11,1,1,1,1,2] 13

Наведена схема має вигляд:

і	0	1	2	3	4	5	6
qi		11	1	1	1	1	2
Pi	1	11	12	23	35	58	151
Qi	0	1	1	2	3	5	13

Тобто дріб 151 має такі підходящі дроби:

13

d1

=

P1

= 11;

d2

=

P2

= 12; d3

=

P3

=

23

= 11

1

; d4

=

P4

=

35

= 11

2

; d5

=

P5

=

58

= 11

3

Якщо

Q2

Q3

Q4

Q5

Q1

2

2

3

3

5

5

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

Властивості схеми розкладання:

1.

Для усіх

i > 0 маємо: Pi Qi−1 - Qi Pi−1

= (-1)i .

Дійсно, i = 1 :

P1Q0 - Q1 P0

= q1 × 0 -1×1 = -1 = (-1)1

i = 2 : P Q - Q P =

(q P + P )Q - (Q q

2

+ Q )P = q

2

(P Q - P Q ) - (P Q - P Q ) = 0 - (-1) = (-1)2

2

1

2

1

2

1

0

1

1

0

1

1

1

1

1

1

0

0

1

і т. д.

2.

Для усіх i > 1 маємо di

- di−1

=

(-1)i

Qi Qi−1

(-1)i

Дійсно, di - di−1

=

Pi

-

Pi−1

=

Pi Qi−1 - Pi−1Qi

=

Qi

Qi−1

Qi Qi−1

Qi Qi−1

3.

Для

усіх

1 < i < n

раціональний

нескорочуваний

дріб

a =

a

з додатнім

b

знаменником завжди розташований між di−1

та di

, ближче до di .

Приклад.

Маємо неперервний дріб [2,1,3,4,1,2].

Побудувати відповідне найменше раціональне число a . b

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

Будуємо таблицю для обчислення підходящих дробів і згідно схеми обчислюємо всі підходящі дроби.

16

	і	0	1		2					3			4	5	6
	qi		2		1					3			4	1	2
	Pi	1	2		3					11			47	58	163
	Qi	0	1		1					4			17	21	59
Останній стовбець таблиці дасть				P6		=	a	=	163			- нескорочуваний дріб, якому відповідає
				Q6			b	59

даний в умові задачі неперервний дріб.

Висновки.

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

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

a = b × q + r, 0 £ r < b ,
де q − неповна частка, r − залишок;
-	число a ділиться на b , якщо r = 0 ;
-	ціле число p називається простим, якщо ділиться тільки на 1 і на себе, всі

інші цілі числа - складені; - простих чисел безкінечно багато;

- якщо пара цілих чисел a та b має спільні дільники, то серед них обов’язково є найбільший спільний дільник (НСД) d = (a ,b);

- якщо (a ,b) =1 , то числа взаємнопрості;

- числа a та b мають безкінечно багато чисел, кратних одночасно обом цім числам, найменше з кратних носить назву найменшого спільного кратного чисел a та b - [a ,b];

- [a ,b]= ( ab ) ; a ,b

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

a = p1α1 × p2 α2 ×... × pk αk ,

де pi - різні за значенням прості числа, ai - степені входження відповідного простого числа pi до числа a , i = 1,k ;

- будь-яке раціональне число m можна розкласти у скінчений неперервний n

дріб, а будь-яке ірраціональне число – у нескінчений;

-будь-який раціональний дріб m на числовій осі розташований між двох його

n

підходящих дробів, ближче до правого краю.

Після вивчення теми 1 ви повинні вміти:

-знайти НСД за допомогою алгоритму Евкліда;

-застосувати найстаріший метод відбору простих чисел, менших за дане – решето Ератосфена;

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

-виходячи з канонічної форми кількох цілих чисел знайти їх НСД та НСК;

17

- використовуючи таблицю підходящих дробів знайти розв’язок рівняння ax + by = d ;

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

Контрольні питання до теми № 1.

1.Дати визначення простого числа, складеного числа, неповної частки, залишку.

2.Сформулювати основні властивості подільності чисел.

3.Сформулювати теорему про ділення з залишком.

4.В чому полягає різниця між взаємно простими і попарно простими числами?

5.Дати визначення спільного дільника довільного набору цілих чисел a , b, c , d .

6.Дати означення найбільшого спільного дільника (a ,b).

7.Спираючись на властивості подільності чисел довести, що якщо числа a , b можна зв’язати рівністю a = b × q + r , то (a ,b) = (b,r ) .

8.Сформулювати алгоритм Евкліда для знаходження (a ,b).

9.Відомо, що a - довільне число, а p - просте число. Які можливі варіанти (a , p)?

10.Дати визначення найменшого спільного кратного [a ,b]. Який існує зв’язок між

(a ,b) та [a ,b]?

11.Яке обмеження існує на найменший дільник числа a ?

12.Сформулювати теорему про єдиність канонічного розкладання довільного цілого числа a на прості множники.

13.Що таке неперервний дріб?

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

15.Що таке підходящий дріб. Якщо взяти два сусідніх підходящих дроба, то де буде розташоване вихідне число?

16.Сформулюйте самостійно схему обчислення підходящих дробів для довільного нескорочуваного раціонального дробу.

17.Які властивості мають підходящі дроби?

18.Використовуючи схему розкладання раціонального числа на неперервні дроби знайти для двох чисел 197 та 23 розв’язок рівняння 197x + 23y = 1.

18

ТЕМА №2 НАЙВАЖЛИВІШІ ФУНКЦІЇ В ТЕОРІЇ ЧИСЕЛ.

Питання 1 Функції виділення цілої та дробової частини дійсного числа. Питання 2 Мультиплікативні функції.

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

Ключові терміни

Функція виділення цілої частини, функція виділення дробової частини, мультиплікативні функції, кількість дільників, сума додатних дільників, недостатнє число, надлишкове число, досконале число, число Мерсенна, дружні числа, функція Ейлера.

Питання 1. Функції виділення цілої та дробової частини дійсного числа.

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

[x] = N; x = N + q; N Î Z; 0 < q < 1;

Приклади: [-100] = -100; [45,9] = 45; [- 5,1] = -6

2. Функція виділення дробової частини дійсного числа х повертає різницю між числом х та його цілою частиною [x]:

{x} = x - [x] = q; 0 < q < 1

Приклади: {-100} = 0; {45,9} = 0,9; {- 5,1} = 0,9

Приклад застосування функції виділення цілої частини:

Визначити степінь α простого числа p , з яким це число входить до числа n!.

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

p буде

. Серед них множників, кратних

У числі n!

множників, які кратні

n

p 2

буде

p

n

£ n , а

pk +1 > n . Отже загальна кількість входжень

,

і т.

д.

доти,

доки

pk

p

до n!

2

p

буде:

n

n

n

a =

+

+ ... +

2

k

p

p

p

Приклад. Знайти з яким степенем число p = 2 входить до числа 11!

11

11

11

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

+

+

= 5 + 2 +1 = 8

2

4

8

Дійсно,

11!= 1× 2 × 3 × 4 × 5 × 6 × 7 ×8 × 9 ×10 ×11 = 1× 21 × 3 × 22 × 5 × (21 × 3)× 7 × 23 × 9 × (21 × 5)×11

Порахувавши усі степені 2, будемо мати: 1 + 2 + 1 + 3 + 1 = 8

19

Питання 2. Мультиплікативні функції.

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

1.	f (a)	визначена для усіх a = 0,1,2... і хоча б для одного a0								f (a0 ) = 0 .
2.	Для будь-яких a1 ,				a2 : (a1 , a2 ) = 1 виконується: f (a1 × a2 ) =					f (a1 )× f (a2 )
Приклад -			a r , де r R
Властивості мультиплікативних функцій.
1.	Для будь-якої мультиплікативної функції f (1) = 1 .
Доведення: ("a Î N					(a,1) = 1,		f (a) = f (a ×1) = f (a)× f (1) f (1) = 1)
Якщо розглянути a1 , a2 ,..., ak							попарно простих чисел, то
f (a1 × a2 ×... × ak ) = f (a1 )×						f (a2 )×... ×		f (ak ), зокрема
f	(p α1 p	α2	×... × p	αk )=	f	(p α1 )× f (p		α2 )×... × f (p	αk )
	1	2		k		1		2	k

Наприклад, задамо мультиплікативну функцію так: f (1) = 1, f (pα )= 2, "a > 0 . Тоді для

довільного цілого числа a = p α1

× p

α2 ×...× p

αk

a

> 0,

i =

будемо мати:

2

,

i

1, k

1

k

f (p α1 × p

2

α2 ×...× p

αk )

=

f (p α1 )× f (p

α2

)×...× а(p

αk

)= 2k

, зокрема:

1

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 = p α1 × p

α2

×...× p

αk -

довільне ціле число,

f (a)

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

1

2

k

β1 × p

β2

βk ,

функція,

D | a - множина усіх дільників a виду d = p

×...× p

0 £ b

£ a

, i =

.

i

1, k

1

2

k

i

Тоді

∑ f (d ) = (1+ f (p1 )+ f (p1

2 )+ ... + f (p1

α1 ))(1 + f (p2 )+ f (p2

2 )+ ... + f (p2

α2 ))×...×

D|a

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

× (1 + f (pk )+ f (pk

Доведення:

Для доведення необхідно перемножити усі дужки, отримаємо суму усіх дільників:

f (p β1

)f (p

β2

)×...× f (p

k

βk )= f (p β1

× p

β2

×...× p

βk )= f (d ),

0 £ b

i

£ a

i

1

2

1

2

k

20