Упражнения к Главе 1.

1.1. Вычислить НОД(a,b) при помощи алгоритма Евклида с делением с остатком и бинарного алгоритма Евклида. Сравнить количество итераций.

a) a = 715, b = 195; d) a = 1818, b = 726; g) a = 2448, b = 1632;

b) a = 246, b = 396; e) a= 6887, b = 6319; h) a = 1600, b = 1120;

c) a = 175, b = 14945; f) a = 1763, b = 1634; i) a = 2310, b = 3388.

1.2. Пользуясь таблицей простых чисел, найти канонические разложения следующих чисел:

a) 492; d) 4144; g) 624239;

b) 22011; e) 2597; h) 422375;

c) 7533; f) 425106; i) 11502.

1.3. Вычислить НОК(a,b).

a) a = 744, b = 198; d) a = 50, b = 42; g) a = 3131, b = 808;

b) a = 60, b = 1575; e) a= 231, b = 1089; h) a = 1063, b = 3;

c) a = 128, b = 81; f) a = 73, b = 219; i) a = 1960, b = 1232.

1.4. Пользуясь свойствами функции Эйлера, вычислить φ(a).

a) a = 73; d) a = 343; g) a = 210;

b) a = 81; e) a= 6; h) a = 10800;

c) a = 97; f) a = 28; i) a = 32.

1.5. Выяснить, верны ли сравнения:

a) 25 ≡ —1 (mod 13); d) 3 ≡ 15 (mod 11); g) 128 ≡ 20 (mod 9);

b) 11 ≡ 3 (mod 2); e) 45 ≡ 12 (mod 11); h) 32 ≡ 5 (mod 7);

c) 100 ≡ 14 (mod 17); f) 98 ≡ 46 (mod 5); i) 13 ≡ 1 (mod 14).

1.6. Выписать полную и приведенную системы вычетов по модулю n. Сравнить количество чисел в приведенной системе вычетов со значением функции Эйлера от n.

a) n = 7; b) n = 9; c) n = 11; d) n = 16; e) n = 6; f) n = 2;

1.7. Вычислить абсолютно наименьший и наименьший неотрицательный вычеты числа a по модулю m.

a) a = 12, m = 15; d) a = 50, m = 12; g) a = —80 , m = 100;

b) a = 35, m = 31; e) a= 8, m = 15; h) a = —4, m = 3;

c) a = —1, m = 81; f) a = 8, m = 17; i) a = 11, m = 11.

1.8. Вычислить обратный элемент, если он существует:

a) 5^-1 mod 8; d) 14^-1 mod 25; g) 46^-1 mod 51;

b) 7^-1 mod 41; e) 13^-1 mod 92; h) 77^-1 mod 101;

c) 23^-1 mod 63; f) 9^-1 mod 27; i) 22^-1 mod 25.

1.9. Пользуясь теоремой Эйлера, вычислить:

a) 90⁴² mod 41; d) 8⁴⁸⁵ mod 187; g) 3¹⁶¹⁶¹³ mod 16;

b) 34¹⁶⁰⁰⁰³ mod 15; e) (-2)⁶³⁴¹⁷⁸ mod 117; h) 5¹⁸⁶⁶⁰⁹ mod 9;

c) (-5)¹⁰⁰⁰¹⁶ mod 11; f) 50¹⁹⁰⁰²¹ mod 38; i) 347¹⁷⁴⁰⁰⁷ mod 349;

1.10. Решить сравнения:

a) 5x ≡ 3(mod 11); d) 6x ≡15(mod 21); g) 13x≡8(mod 16);

b) 8x ≡ 5(mod 13); e) 16x≡26(mod 62); h) 25x≡50(mod 125);

c) 15x≡25(mod 17); f) 21x≡14(mod 42); i) 13x≡37(mod 29).

1.11. Решить системы сравнений.

a) ; c) ; e) ;

b) ; d) ; f) .

1.12. Вычислить, пользуясь свойствами символа Якоби:

a) ; c) ; e) ; g) ; i) ; k) ;

b) ; d) ; f) ; h) ; j) ; l) .

1.13. Решить следующие квадратичные сравнения по простому модулю, если решение существует.

a) x²≡17(mod 19); d) x²≡2 (mod 7); g) x²≡3 (mod 41);

b) x²≡3 (mod 13); e) x²≡3 (mod 11); h) x²≡2 (mod 17);

c) x²≡8 (mod 41); f) 2x²≡10 (mod 11); i) 3x²≡15(mod 31).

1.14. Решить следующие квадратичные сравнения по составному модулю, если решение существует.

a) x²≡7(mod 9); g) x²≡1 (mod 32); m) x²≡11 (mod 35);

b) x²≡—1(mod 25); h) x²≡67 (mod 81); n) x²≡5 (mod 12);

c) x²≡32(mod 49); i) x²≡59 (mod 125); o) x²≡9 (mod 20);

d) x²≡1(mod 4); j) x²≡4(mod 6); p) x²≡31 (mod 105);

e) x²≡3(mod 8); k) x²≡1(mod 15); q) x²≡4 (mod 105);

f) x²≡9(mod 16); l) x²≡1(mod 24); r) x²≡ 16 (mod 75).

1.15. Определить, сколько решений имеют сравнения.

a) x²≡—1(mod 59); d) x²≡ 17(mod 32); g) x²≡1(mod 150);

b) x²≡ 3(mod 83); e) x²≡ 25(mod 96); h) x²≡4(mod 343);

c) x²≡ 1(mod 8); f) x²≡ 2(mod 315); i) x²≡1(mod 2).

1.16. Выписать все квадраты и все псевдоквадраты из приведенной системы вычетов по модулю n.

a) n = 15; b) n = 21; c) n = 33; d) n = 6; e) n = 14; f) n = 35.

1.17. Указать, какие их приведенных ниже чисел являются числами Блюма.

a) 7; b) 21; c) 47; d) 469; e) 35; f) 59.

1.18. Отыскать p₈ и p₉ – 8-е и 9-е простые числа, представимые в виде 4k+3. Составить число Блюма n=p₈p₉. На основе BBS-генератора с ключом s₀=121 составить ключевую последовательность длиной 10 бит.

1.19. Существуют ли первообразные корни по модулю n, и если существуют, то сколько их?

a) n = 15; b) n = 71; c) n = 53; d) n = 202; e) n = 16; f) n = 25.

1.20. Найти первообразные корни по следующим модулям:

a) 3; c) 27; e) 26; g) 43; i) 169; k) 89;

b) 9; d) 13; f) 18; h) 86; j) 4; l) 41.