Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 6: Тест простоты- Введение
- Пройди испытание на тест простоты
- Перебор делителей
- Чем ограничена память компьютера?
- Эффективность алгоритмов
- Уровень 3. Испытание
- Решето Эратосфена
- Уровень 4. Решето Эратосфена
- Тест простоты при помощи решета Эратосфена
- Уровень 5. Перебор делителей при помощи решета Эратосфена
- Теорема о распределении простых чисел
- Скатерть Улама
- Промежутки между простыми числами
- Компромисс времени и памяти
- Итоги (что дальше?)
Введение
Вы знакомы с уроком по современной криптографии? На последней проверке пользователи чаще всего задавали такой вопрос:
В этом уроке мы рассмотрели, как разложение на простые множители играет важнейшую роль в создании математических замков. Математический замок (или односторонняя функция) — это некая процедура, которую легко выполнить, но сложно обратить.
Например, если я выберу случайным образом два больших простых числа, скажем, P1=709 и P2=733
и перемножу их, получив N = P1 * P2
N = 709 * 733 = 519697 (эта операция легко вычисляется)
У меня в итоге будет некое большое число (519697), и я буду знать, как оно раскладывается на множители (709 * 733)
А теперь представьте, что я скрыл его разложение на простые множители и предоставил вам следующее:
519697 = ? * ? (это сложно вычислить)
Если я вас попрошу разложить это число на простые множители, с чего начать решение такой задачи? Не волнуйтесь, этот вопрос многих поставит в тупик! Чтобы ответить на него, придётся перебирать множество возможных делителей. Перемножить два числа можно быстро (и легко), а вот поиск простых делителей — это долгая (сложная) операция. Этот простой факт лежит в основе алгоритма шифрования RSA.
Чтобы понять разницу, взгляните на анимированную схему
Хотя, прежде чем продолжить, вернёмся к первому шагу и ответим на важный вопрос. Когда мы случайным образом выбираем два больших простых числа, насколько быстро это можно сделать? Насколько проста такая задача?
Если подумать, то вы в конечном счёте согласитесь, что этот шаг требует как минимум проверки, является ли случайно сгенерированное число (например, 99194853094755497) простым или составным. Есть ли у вас на калькуляторе для этого специальная кнопка?
IУ меня такой нет… Почему?
Чтобы ответить на этот вопрос, рассмотрим следующую задачу…
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.