Упражнения к Главе 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) 9042 mod 41; d) 8485 mod 187; g) 3161613 mod 16;

b) 34160003 mod 15; e) (-2)634178 mod 117; h) 5186609 mod 9;

c) (-5)100016 mod 11; f) 50190021 mod 38; i) 347174007 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) x2≡17(mod 19); d) x2≡2 (mod 7); g) x2≡3 (mod 41);

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

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

 

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

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

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

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

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

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

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

 

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

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

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

c) x2≡ 1(mod 8); f) x2≡ 2(mod 315); i) x2≡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. Отыскать p8 и p9 – 8-е и 9-е простые числа, представимые в виде 4k+3. Составить число Блюма n=p8p9. На основе BBS-генератора с ключом s0=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.

 



Дата добавления: 2018-11-26; просмотров: 805;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.014 сек.