Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 3 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Содержание
Введение 7
1. Простые числа 10
1.1. Модулярная арифметика . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Алгоритм быстрого возведения в степень по модулю . . . . . . . 13
1.3. Решето Эратосфена и критерии простоты . . . . . . . . . . . . . 14
1.4. Метод пробных делений . . . . . . . . . . . . . . . . . . . . . . . 15
1.5. Решето Аткина . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6. Тест Поклингтона . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7. Генерация простых чисел . . . . . . . . . . . . . . . . . . . . . . 20
1.8. Расширенный алгоритм Евклида . . . . . . . . . . . . . . . . . . 23
1.9. Символ Лежандра . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.10. Тест простоты Миллера–Рабина . . . . . . . . . . . . . . . . . . 27
1.11. Вероятностный тест простоты Соловея–Штрассена . . . . . . . 29
1.12. Полиномиальный критерий простоты AKS . . . . . . . . . . . . 31
1.13. Распределение простых чисел . . . . . . . . . . . . . . . . . . . . 32
1.14. Извлечение квадратного корня в конечных полях . . . . . . . . 34
1.15. Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . 36
1.16. π , e и другие известные константы . . . . . . . . . . . . . . . . 38
1.17. Открытые проблемы теории чисел . . . . . . . . . . . . . . . . . 39
1.18. Великая теорема Ферма . . . . . . . . . . . . . . . . . . . . . . . 42
1.19. Числа Ферма, Мерсенна и Кармайкла . . . . . . . . . . . . . . . 45
2. Простые алгоритмы факторизации 52
2.1. Метод Ферма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2. (p − 1)–метод Полларда . . . . . . . . . . . . . . . . . . . . . . . 54
2.3. (p + 1)–метод Вильямса . . . . . . . . . . . . . . . . . . . . . . . 60
2.4. ρ-метод Полларда . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.5. ρ-метод Полларда для вычисления дискретного логарифма . . 65
2.6. Факторизация с использованием непрерывных дробей . . . . . . 68
2.7. Уравнение Пелла . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4
Содержание
Введение                                                                     7

1. Простые числа                                                            10
  1.1. Модулярная арифметика . . . . . . . . . . . . . . . . . . . . . . 10
  1.2. Алгоритм быстрого возведения в степень по модулю . . . . . . . 13
  1.3. Решето Эратосфена и критерии простоты . . . . . . . . . . . . . 14
  1.4. Метод пробных делений . . . . . . . . . . . . . . . . . . . . . . . 15
  1.5. Решето Аткина . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
  1.6. Тест Поклингтона . . . . . . . . . . . . . . . . . . . . . . . . . . 19
  1.7. Генерация простых чисел . . . . . . . . . . . . . . . . . . . . . . 20
  1.8. Расширенный алгоритм Евклида . . . . . . . . . . . . . . . . . . 23
  1.9. Символ Лежандра . . . . . . . . . . . . . . . . . . . . . . . . . . 25
  1.10. Тест простоты Миллера–Рабина . . . . . . . . . . . . . . . . . . 27
  1.11. Вероятностный тест простоты Соловея–Штрассена . . . . . . . 29
  1.12. Полиномиальный критерий простоты AKS . . . . . . . . . . . . 31
  1.13. Распределение простых чисел . . . . . . . . . . . . . . . . . . . . 32
  1.14. Извлечение квадратного корня в конечных полях . . . . . . . . 34
  1.15. Китайская теорема об остатках . . . . . . . . . . . . . . . . . . . 36
  1.16. π , e и другие известные константы . . . . . . . . . . . . . . . . 38
  1.17. Открытые проблемы теории чисел . . . . . . . . . . . . . . . . . 39
  1.18. Великая теорема Ферма . . . . . . . . . . . . . . . . . . . . . . . 42
  1.19. Числа Ферма, Мерсенна и Кармайкла . . . . . . . . . . . . . . . 45

2. Простые алгоритмы факторизации                                           52
  2.1. Метод Ферма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
  2.2. (p − 1)–метод Полларда . . . . . . . . . . . . . . . . . . . . . . . 54
  2.3. (p + 1)–метод Вильямса . . . . . . . . . . . . . . . . . . . . . . . 60
  2.4. ρ-метод Полларда . . . . . . . . . . . . . . . . . . . . . . . . . . 61
  2.5. ρ-метод Полларда для вычисления дискретного логарифма . . 65
  2.6. Факторизация с использованием непрерывных дробей . . . . . . 68
  2.7. Уравнение Пелла . . . . . . . . . . . . . . . . . . . . . . . . . . . 71


                                      4

Страницы