Ответы к упражнениям.
Упражнения к Главе 1:
1.1. a) 13, b) 2, c) 35, d) 6, e) 71, f) 43, g) 48, h) 160, i) 154.
1.2. a) 22·3·41, b) 3·11·23·29, c) 35·31, d) 24·7·37, e) 72·53, f) 2·32·11·19·131, g)7·113·67 h) 53·31·109, i) 2·34·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) x7+x5+x4; x11+x9+x8+x7+x4+x2+1; b) x4+x2+x+1; x6+x4+x3+x; c) x8+x3+1; x11+x10+x8+x5+x4+x2; d) x; x10+x6.
2.2. a) x2+x+1, b) 0, c) x, d) 1.
2.3. a) (x+1), b) x2+1, c) x3+x, d) x2+x+1.
Упражнения к Главе 3:
3.4. a) 18, b) 24, c) 87.
3.5. a) 36, b) 45, c) 15.
Приложение 1.
Таблица простых чисел < 2558 и их наименьших первообразных корней.
p | g | p | g | p | g | p | g | p | g | p | g | p | g | p | g |
2 | 1 | 101 | 2 | 233 | 3 | 383 | 5 | 547 | 2 | 701 | 2 | 877 | 2 | 1049 | 3 |
3 | 2 | 103 | 5 | 239 | 7 | 389 | 2 | 557 | 2 | 709 | 2 | 881 | 3 | 1051 | 7 |
5 | 2 | 107 | 2 | 241 | 7 | 397 | 5 | 563 | 2 | 719 | 11 | 883 | 2 | 1061 | 2 |
7 | 3 | 109 | 6 | 251 | 6 | 401 | 3 | 569 | 3 | 727 | 5 | 887 | 5 | 1063 | 3 |
11 | 2 | 113 | 3 | 257 | 3 | 409 | 21 | 571 | 3 | 733 | 6 | 907 | 2 | 1069 | 6 |
13 | 2 | 127 | 3 | 263 | 5 | 419 | 2 | 577 | 5 | 739 | 3 | 911 | 17 | 1087 | 3 |
17 | 3 | 131 | 2 | 269 | 2 | 421 | 2 | 587 | 2 | 743 | 5 | 919 | 7 | 1091 | 2 |
19 | 2 | 137 | 3 | 271 | 6 | 431 | 7 | 593 | 3 | 751 | 3 | 929 | 3 | 1093 | 5 |
23 | 5 | 139 | 2 | 277 | 5 | 433 | 5 | 599 | 7 | 757 | 2 | 937 | 5 | 1097 | 3 |
29 | 2 | 149 | 2 | 281 | 3 | 439 | 15 | 601 | 7 | 761 | 6 | 941 | 2 | 1103 | 5 |
31 | 3 | 151 | 6 | 283 | 3 | 443 | 2 | 607 | 3 | 769 | 11 | 947 | 2 | 1109 | 2 |
37 | 2 | 157 | 5 | 293 | 2 | 449 | 3 | 613 | 2 | 773 | 2 | 953 | 3 | 1117 | 2 |
41 | 6 | 163 | 2 | 307 | 5 | 457 | 13 | 617 | 3 | 787 | 2 | 967 | 5 | 1123 | 2 |
43 | 3 | 167 | 5 | 311 | 17 | 461 | 2 | 619 | 2 | 797 | 2 | 971 | 6 | 1129 | 11 |
47 | 5 | 173 | 2 | 313 | 10 | 463 | 3 | 631 | 3 | 809 | 3 | 977 | 3 | 1151 | 17 |
53 | 2 | 179 | 2 | 317 | 2 | 467 | 2 | 641 | 3 | 811 | 3 | 983 | 5 | 1153 | 5 |
59 | 2 | 181 | 2 | 331 | 3 | 479 | 13 | 643 | 11 | 821 | 2 | 991 | 6 | 1163 | 5 |
61 | 2 | 191 | 19 | 337 | 10 | 487 | 3 | 647 | 5 | 823 | 3 | 997 | 7 | 1171 | 2 |
67 | 2 | 193 | 5 | 347 | 2 | 491 | 2 | 653 | 2 | 827 | 2 | 1009 | 11 | 1181 | 7 |
71 | 7 | 197 | 2 | 349 | 2 | 499 | 7 | 659 | 2 | 829 | 2 | 1013 | 3 | 1187 | 2 |
73 | 5 | 199 | 3 | 353 | 3 | 503 | 5 | 661 | 2 | 839 | 11 | 1019 | 2 | 1193 | 3 |
79 | 3 | 211 | 2 | 359 | 7 | 509 | 2 | 673 | 5 | 853 | 2 | 1021 | 10 | 1201 | 11 |
83 | 2 | 223 | 3 | 367 | 6 | 521 | 3 | 677 | 2 | 857 | 3 | 1031 | 14 | 1213 | 2 |
89 | 3 | 227 | 2 | 373 | 2 | 523 | 2 | 683 | 5 | 859 | 2 | 1033 | 5 | 1217 | 3 |
97 | 5 | 229 | 6 | 379 | 2 | 541 | 2 | 691 | 3 | 863 | 5 | 1039 | 3 | 1223 | 5 |
p | g | p | g | p | g | p | g | p | g | p | g | p | g |
1229 | 2 | 1429 | 6 | 1597 | 11 | 1783 | 10 | 1993 | 5 | 2161 | 23 | 2371 | 2 |
1231 | 3 | 1433 | 3 | 1601 | 3 | 1787 | 2 | 1997 | 2 | 2179 | 7 | 2377 | 5 |
1237 | 2 | 1439 | 7 | 1607 | 5 | 1789 | 6 | 1999 | 3 | 2203 | 5 | 2381 | 3 |
1249 | 7 | 1447 | 3 | 1609 | 7 | 1801 | 11 | 2003 | 5 | 2207 | 5 | 2383 | 5 |
1259 | 2 | 1451 | 2 | 1613 | 3 | 1811 | 6 | 2011 | 3 | 2213 | 2 | 2389 | 2 |
1277 | 2 | 1453 | 2 | 1619 | 2 | 1823 | 5 | 2017 | 5 | 2221 | 2 | 2393 | 3 |
1279 | 3 | 1459 | 5 | 1621 | 2 | 1831 | 3 | 2027 | 2 | 2237 | 2 | 2399 | 11 |
1283 | 2 | 1471 | 6 | 1627 | 3 | 1847 | 5 | 2029 | 2 | 2239 | 3 | 2411 | 6 |
1289 | 6 | 1481 | 3 | 1637 | 2 | 1861 | 2 | 2039 | 7 | 2243 | 2 | 2417 | 3 |
1291 | 2 | 1483 | 2 | 1657 | 11 | 1867 | 2 | 2053 | 2 | 2251 | 7 | 2423 | 5 |
1297 | 10 | 1487 | 5 | 1663 | 3 | 1871 | 14 | 2063 | 5 | 2267 | 2 | 2437 | 2 |
1301 | 2 | 1489 | 14 | 1667 | 2 | 1873 | 10 | 2069 | 2 | 2269 | 2 | 2441 | 6 |
1303 | 6 | 1493 | 2 | 1669 | 2 | 1877 | 2 | 2081 | 3 | 2273 | 3 | 2447 | 5 |
1307 | 2 | 1499 | 2 | 1693 | 2 | 1879 | 6 | 2083 | 2 | 2281 | 7 | 2459 | 2 |
1319 | 13 | 1511 | 11 | 1697 | 3 | 1889 | 3 | 2087 | 5 | 2287 | 19 | 2467 | 2 |
1321 | 13 | 1523 | 2 | 1699 | 3 | 1901 | 2 | 2089 | 7 | 2293 | 2 | 2473 | 5 |
1327 | 3 | 1531 | 2 | 1709 | 3 | 1907 | 2 | 2099 | 2 | 2297 | 5 | 2477 | 2 |
1361 | 3 | 1543 | 5 | 1721 | 3 | 1913 | 3 | 2111 | 7 | 2309 | 2 | 2503 | 3 |
1367 | 5 | 1549 | 2 | 1723 | 3 | 1931 | 2 | 2113 | 5 | 2311 | 3 | 2521 | 17 |
1373 | 2 | 1553 | 3 | 1733 | 2 | 1933 | 5 | 2129 | 3 | 2333 | 2 | 2531 | 2 |
1381 | 2 | 1559 | 19 | 1741 | 2 | 1949 | 2 | 2131 | 2 | 2339 | 2 | 2539 | 2 |
1399 | 13 | 1567 | 3 | 1747 | 2 | 1951 | 3 | 2137 | 10 | 2341 | 7 | 2543 | 5 |
1409 | 3 | 1571 | 2 | 1753 | 7 | 1973 | 2 | 2141 | 2 | 2347 | 3 | 2549 | 2 |
1423 | 3 | 1579 | 3 | 1759 | 6 | 1979 | 2 | 2143 | 3 | 2351 | 13 | 2551 | 6 |
1427 | 2 | 1583 | 5 | 1777 | 5 | 1987 | 2 | 2153 | 3 | 2357 | 2 | 2557 | 2 |
Приложение 2.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
|
| . |
ТЕОРЕТИКО - ЧИСЛОВЫЕ МЕТОДЫ В КРИПТОГРАФИИ |
|
Рабочая программа для специальности |
|
075200 – Компьютерная безопасность |
|
Тюмень 2007
- Теоретико-числовые методы в криптографии
- Аннотация.
- Предисловие
- Введение
- Глава 1. Основы теории чисел. §1. Теория делимости.
- 1.1. Основные понятия и теоремы.
- 1.2. Наибольший общий делитель.
- 1.3 Нок (наименьшее общее кратное)
- 1.4. Простые числа
- Решето Эратосфена
- 1.5. Единственность разложения на простые сомножители.
- 1.6. Асимптотический закон распределения простых чисел.
- §2. Функция Эйлера.
- 2.1. Мультипликативные функции.
- 2.2. Функция Эйлера.
- §3. Теория сравнений
- 3.1. Свойства сравнений:
- 3.2. Полная система вычетов.
- 3.3. Приведенная система вычетов
- 3.4. Обратный элемент.
- 3.5. Алгебраические структуры на целых числах.
- 3.6. Теоремы Эйлера и Ферма. Тест Ферма на простоту.
- Тест Ферма на простоту
- 3.7. Применение теоремы Эйлера в rsa:
- §4. Сравнения с одним неизвестным
- 4.1. Сравнения первой степени.
- 4.2. Система сравнений первой степени. Китайская теорема об остатках.
- 4.3. Применения китайской теоремы об остатках.
- 4.4. Сравнения любой степени по простому модулю.
- 4.5. Сравнения любой степени по составному модулю.
- §5. Теория квадратичных вычетов
- 5.1. Квадратичные вычеты по простому модулю.
- 5.2. Символ Лежандра. Символ Якоби.
- Свойства символа Лежандра:
- Свойства символа Якоби:
- 5.3. Тест на простоту Соловея-Штрассена.
- Тест Соловея-Штрассена:
- 5.4. Решение квадратичных сравнений по простому модулю.
- 5.5. Квадратичные сравнения по составному модулю.
- 5.6. Тест на простоту Миллера-Рабина.
- 5.7. Связь задач извлечения квадратных корней и факторизации по модулю rsa. Криптосистема Рабина.
- 5.8. Квадраты и псевдоквадраты.
- 5.9. Числа Блюма.
- §6. Первообразные корни и индексы. Порождающий элемент и дискретный логарифм.
- 6.1. Основные понятия и теоремы.
- 6.2. Существование первообразных корней по модулю p.
- 6.3. Первообразные корни по модулям pα, 2pα.
- 6.4. Нахождение первообразных корней по простому модулю.
- 6.5. Существование и количество первообразных корней.
- 6.6. Дискретные логарифмы.
- 6.7. Проблема Диффи-Хеллмана.
- 6.8. Условная стойкость шифра Эль Гамаля.
- §7. Построение доказуемо простых чисел общего и специального вида.
- 7.1. Теорема Сэлфриджа и доказуемо простые числа общего вида на основании полного разложения (n—1).
- 7.2. Теорема Поклингтона и доказуемо простые числа общего вида на основании частичного разложения (n—1).
- 7.3. Числа Ферма. Теорема Пепина.
- 7.4. Числа Мерсенна.
- 7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины гост р 34.10-94.
- Глава 2. Алгебраические основы теории чисел.
- §1. Основные понятия алгебры.
- 1.1. Начальные понятия.
- 1.2. Делимость в кольцах.
- 1.3. Деление с остатком.
- 1.4. Основная теорема арифметики.
- §2. Конечные поля и неприводимые многочлены.
- §3. Кольца многочленов.
- 3.1. Кольца многочленов.
- 3.2. Кольцо многочленов Zp[X].
- 3.3. Конечные поля многочленов.
- Глава 3. Алгоритмы в криптографии и криптоанализе. §1. Элементы теории сложности.
- §2. Алгоритмы факторизации.
- 2.1. Метод пробных делений.
- 2.2. Метод Ферма.
- 2.3. Метод квадратичного решета.
- 2.6. Методы случайных квадратов.
- §3. Алгоритмы дискретного логарифмирования.
- 3.1. Метод прямого поиска.
- 3.2. Шаг младенца – шаг великана.
- 3.4. Алгоритм Полига-Хеллмана.
- 3.5. Алгоритм исчисления порядка (index-calculus algorithm).
- Задачи и упражнения.
- Упражнения к Главе 2.
- Ответы к упражнениям.
- 1. Пояснительная записка
- 1.1. Цели и задачи дисциплины
- 1.2. Требования к уровню освоения содержания дисциплины
- 2. Объем дисциплины и виды учебной работы
- 3. Тематический план изучения дисциплины
- 4. Содержание разделов дисциплины
- 6. Вопросы к экзаменам
- 7.Литература основная:
- Дополнительная:
- Оглавление