А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

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. Пользуясь таблицей простых чисел, найти канонические разложения следующих чисел:

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

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

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

1. Вычислить НОК(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. Пользуясь свойствами функции Эйлера, вычислить φ(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.

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

2.1. Вычислить сумму и произведение многочленов f(x) и g(x) на Z₂[x]:

a) f(x)=x⁷+x⁵+x+1, g(x)=x⁴+x+1; c) f(x)=x⁸+x², g(x)=x³+x²+1;

b) f(x)=x⁴+x, g(x)=x²+1; d) f(x)=x⁵; g(x)=x⁵+x.

2.2. Вычислить остаток от деления f(x) на g(x) на Z₂[x].

a) f(x)=x⁸+x⁴+x+1, g(x)=x³+x+1; c) f(x)=x¹⁰+x²+x+1, g(x)=x²+x+1;

b) f(x)=x⁴+x, g(x)=x²+x+1; d) f(x)=x⁵+x⁴+1; g(x)=x²+x.

2.3. Вычислить НОД(g(x),f(x)) на Z₂[x].

a) f(x)=x⁶+x⁵+x³+x²+1, g(x)= x⁵+x⁴+x+1;

b) f(x)=x⁶+x⁴, g(x)=x⁴+1;

c) f(x)=x⁴+x³+x²+x, g(x)=x⁵+x³;

d) f(x)=x⁹+x⁸+x; g(x)=x⁷+x⁴+x³+1.

Упражнения к Главе 3:

3.1. Осуществить 2-факторизацию следующих чисел, используя метод Ферма и метод квадратичного решета с решетами по модулям 4, 5, 7. Сравнить количество итераций для этих двух методов.

a) 12317; c) 7081; e) 551; g) 1679; i) 6111; k) 1221;

b) 851; d) 18161; f) 481; h) 7313; j) 1197; l) 609.

3.2. Осуществить 2-факторизацию следующих чисел, используя ро-метод Полларда.

a) 1183; b) 1881; c) 2597; d) 1057; e) 5461; f) 299.

3.3. Осуществить факторизацию следующих чисел, используя p—1 –метод Полларда.

a) 133; b) 209; c) 161; d) 527; e) 1393; f) 3277.

3.4. Вычислить следующие дискретные логарифмы, пользуясь алгоритмом «шаг младенца – шаг великана».

a) log₃ 14 mod φ(31); b) log₅ 42 mod φ(47); c) log₃ 30 mod φ(89).

3.5. При помощи алгоритма исчисления порядка вычислить следующие дискретные логарифмы.

a) log₃ 57 mod φ(89); b) log₃ 61 mod φ(79); c) log₃ 279 mod φ(587).

Ответы к упражнениям.

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

1.1. a) 13, b) 2, c) 35, d) 6, e) 71, f) 43, g) 48, h) 160, i) 154.

1.2. a) 2²·3·41, b) 3·11·23·29, c) 3⁵·31, d) 2⁴·7·37, e) 7²·53, f) 2·3²·11·19·131, g)7·11³·67 h) 5³·31·109, i) 2·3⁴·71.

1.3. a) 24552, b) 6300, c) 10368, d) 1050, e) 7623, f) 219, g) 25048, h) 31189, i)43120.

1.4. a) 72, b) 54, c) 96, d) 294, e) 2, f) 12, g) 48, h) 2880, i) 16.

1.5. a) верно, b) верно, c) неверно, d) неверно, e) верно, f) неверно, g) верно, h)неверно, i) неверно.

1.7. a) —3; 12, b) 4; 4, c)—1; 80, d) 2; 2, e)—7; 8, f) 8; 8, g) 20; 20, h)—1; 2, i)0;0.

1.8. a) 5, b) 6, c) 11, d) 9, e) 7, f) не существует, g) 10, h) 21, i) 8.

1.9. a) 23, b) 4, c) 5, d) 43, e) 4, f) 18, g) 3, h) 8, i) 221.

1.10. a) x≡5(mod 11), b) x≡12(mod 13), c) x≡13(mod 17), d) x≡6, 15, 20(mod 21), e) x≡21, 52(mod 62); f) решений нет; g) x≡8(mod 16), h) x≡2+5t(mod 125), где t= , i) x≡20(mod 29).

1.11. a) x≡8(mod 35), b) x≡52(mod 105), c) x≡53(mod 77), d) x≡101(mod 180), e) решений нет, f) x≡206(mod 210).

1.12. a) -1, b) -1, c) 1, d) 1, e) 0, f) 1, g) 1, h) 1, i) -1, j) -1, k) -1, l) -1.

1.13. a) ±6(mod 19), b) ±9(mod 13), c) ±7(mod 41), d) ±3(mod 7), e) ±5(mod 11), f) ±4(mod 11), g) решений нет, h) ±6(mod 17), i) ±6(mod 31).

1.14. a) ±4(mod 9), b) ±7(mod 25), c) ±9(mod 49), d) ±1(mod 4), e) решений нет, f) ±3, ±5(mod 16), g) ±1, ±15(mod 32), h) ±38(mod 81), i) ±53(mod 125), j) ±2(mod 6), k) ±1,±4(mod 15), l) ±1,±5,±7,±11(mod 24), m) ±9,±16(mod 35), n) решений нет, o) ±3,±7(mod 20), p) решений нет, q) ±2,±23,±37,±47(mod 105), r) ±4,±29 (mod 75).

1.15. a) решений нет, b) 2, c) 4, d) 4, e) 8, f) решений нет, g) 4, h) 2, i) 1.

1.18. 1011011101.

1.19. a) не существует, b) 24 корня, c) 24 корня, d) 40 корней, e) нет существует, f) 8 корней.

1.20. a) 3, b) 2, c) 2, d) 2, e) 17, f) 11, g) 3, h) 3, i) 2, j) 3, k) 3, l) 6.

Упражнения к Главе 2:

2.1. a) x⁷+x⁵+x⁴; x¹¹+x⁹+x⁸+x⁷+x⁴+x²+1; b) x⁴+x²+x+1; x⁶+x⁴+x³+x; c) x⁸+x³+1; x¹¹+x¹⁰+x⁸+x⁵+x⁴+x²; d) x; x¹⁰+x⁶.

2.2. a) x²+x+1, b) 0, c) x, d) 1.

2.3. a) (x+1), b) x²+1, c) x³+x, d) x²+x+1.

Упражнения к Главе 3:

3.4. a) 18, b) 24, c) 87.

3.5. a) 36, b) 45, c) 15.

Приложение 1.

Таблица простых чисел < 2558 и их наименьших первообразных корней.

Характеристики

Список файлов книги