0Pricing
Cryptology Academy · Урок

Простые числа и факторизация

Узнайте, почему простые числа лежат в основе криптографии с открытым ключом

«Простые числа и факторизация» — бесплатный урок Cryptology Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Cryptology Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Cryptology Academy содержит 4 уроков всего.

Добро пожаловать

Простые числа делятся только на 1 и на самих себя. Это атомы умножения и основа RSA, Диффи — Хеллмана и многих других криптосистем.

Определение и примеры

Простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... Число является простым, если его единственные положительные делители — 1 и оно само. 1 по соглашению — NOT простое число.

Основная теорема арифметики

Каждое целое число > 1 можно единственным образом разложить на простые множители, если не учитывать их порядок. 60 = 2² × 3 × 5. Именно эта однозначность делает криптографию на основе факторизации работоспособной.

Пробное деление

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True Достаточно проверять числа только до √n: если множитель меньше √n не найден, n является простым.

Решето Эратосфена

Чтобы найти все простые числа до N, начните со списка чисел от 2 до N. Вычеркните кратные 2, затем 3, затем 5 и так далее. Оставшиеся числа простые. Алгоритм работает за O(N log log N).

Проверка простоты: Миллер — Рабин

Для больших чисел (2048 бит) пробное деление работает слишком медленно. Миллер — Рабин — вероятностная проверка: запустите её 40 раз, и вероятность ошибки будет меньше 4^(-40).

Разложение целых чисел на множители

Если дано n = p × q, поиск p и q представляет собой задачу факторизации целых чисел. Для 2048-битного n лучшие известные алгоритмы требуют 2^112 операций, что в настоящее время практически невыполнимо.

Почему RSA использует два больших простых числа

Модуль RSA: n = p × q. Зная n, но не зная p и q, трудно вычислить закрытый ключ. Безопасность полностью основана на сложности факторизации n.

Генерация больших простых чисел

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime Алгоритм: сгенерируйте случайное нечётное число, проверьте его с помощью Миллера — Рабина и повторяйте, пока число не окажется простым.

Безопасные и сильные простые числа

Безопасное простое число p = 2q+1, где q также является простым. Безопасные простые числа противостоят определённым атакам на DH. В RSA иногда используются сильные простые числа, чтобы предотвратить атаку Полларда на p-1.

Промежутки между простыми числами и бесконечность

Евклид доказал существование бесконечного количества простых чисел в 300 BCE. Гипотеза о близнецах-близнецах (простые числа p и p+2 существуют в бесконечном количестве) до сих пор не доказана. Для криптографии простые числа никогда не заканчиваются.

Быстрая проверка

Почему RSA использует большие простые числа?

Итоги

Теперь Вы понимаете простые числа и факторизацию. Далее мы применим функцию Эйлера и GCD — последние математические инструменты, необходимые перед изучением RSA.

Часто задаваемые вопросы

Урок «Простые числа и факторизация» бесплатный?

Да — полный текст урока «Простые числа и факторизация» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Cryptology Academy, подпишись на CoddyKit PRO. Курс Cryptology Academy содержит 4 уроков всего.

Чему я научусь в уроке «Простые числа и факторизация»?

Узнайте, почему простые числа лежат в основе криптографии с открытым ключом Ты практикуешь Cryptology Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Cryptology Academy?

Предыдущий опыт не требуется. Cryptology Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Простые числа и факторизация»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Cryptology Academy?

Да. Каждый урок Cryptology Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Основы двоичной и шестнадцатеричной систем
  2. Основы модульной арифметики
  3. Простые числа и факторизация
  4. GCD, функция Эйлера и введение в теорию чисел
← Назад к Cryptology Academy