Итоги (что дальше?)

так в прошлых видео мы разобрались с основами шифрования рст и этот вид шифрование зависит от двух вещей во-первых как мы помним что разложение на простые множители достаточно сложная задача поэтому берутся два больших простых числа p1 и p2 и перемножаются получается некое число n и здесь мы полагаемся на то что для поиска этих простых чисел понадобится очень много времени возможно вам даже не хватит жизни во-вторых для р с и необходимо такие простые числа придумать которые бы не составило труда то есть я должен быстро сгенерировать большое простое число теперь давайте вернёмся к первому вопросу о сложности поиска делителей почему разложение числа на простые множители настолько сложная задача например нам дано некое число x и нужно узнать является ли x простым или составным мы попробовали написать несколько алгоритмов для решения этой задачи и в конце концов мы осознаем что это задача очень и очень ресурсоемкая поэтому не существует и мгновенного способа ее решения а с увеличением входного числа увеличивается и время работы программы которая пытается найти решение благодаря теореме о распределении простых чисел мы с вами знаем как растет время и поэтому можно примерно рассчитать количество необходимых шагов наглядно эту проблему можно представить в виде графика по оси y у нас будет время то есть количество шагов программы а по оси x размер входного числа так вот проблема заключается в том что эта кривая очень быстро растет даже в нашем случае если n 20 значное то задача уже практически не решаема а если взять 100 значное число то понятно что мы вообще не сможем ее решить наша программа выдаст сразу ошибку поэтому при помощи наших алгоритмов физически невозможно проверить является ли большое число простым или нет а для того чтобы разложить число на множители необходимо сделать гораздо больше шагов чем просто выяснить является ли оно простым для такой задачи нам потребуется найти все простые делители числа n а для проверки на простоту достаточно найти хотя бы один делитель это хорошо видно по тому как некоторые пользователи превращали алгоритм проверки числа на простоту в алгоритм разложения на множители они продолжали работу даже после нахождения 1 делителя то есть проверка простоты это лишь под задача разложения числа на множители и график будет выглядеть примерно вот так с увеличением входного числа кривая разложение на множители будет выше кривой проверки простоты и нельзя забывать что в любом случае наши ресурсы ограничены вычислительной мощностью и количеством имеющегося в нашем распоряжении времени мы сможем проделать не больше определенного количества таких примитивных шагов можно представить это ограничение в виде горизонтальной прямой это предел нашего графика все что выше этой линии для нас недосягаемо не решаема как вы помните при решении наших задач мы были ограничены достаточно медленным бортовым компьютером марсохода поэтому не смогли проверить просто туда же 20-значных чисел но даже если бы у нас была бы 100 компьютеров которые бы работали над нашей задачей целый год то есть мы смогли бы проверять даже большие числа но всегда упремся в некий предел выше которого задача снова становится нерешаемой и здесь встает ряд интересных вопросов я расскажу о двух вопросах которые рассмотрю дальше во-первых я рисовал кривую сложности задачи очень примерно однако было бы полезно для любого алгоритма вне зависимости от того какую задачу он решает и на каком устройстве работает сразу нарисовать соответствующие график роста его сложности просто посмотрев на описание алгоритма если бы у нас это получилось мы бы смогли классифицировать эти графики по их виду и сразу понимать сложность поставленной перед нами задачи тогда мы сможем проанализировать работу алгоритма даже до его запуска например вам дают некие описанные на бумаге алгоритма вы смотрите на него и говорите этот алгоритм не сможет обработать такой объем входных данных и тут мы подходим к вопросу вычислительной сложности алгоритма и если вы слышали такое понятие как экспоненциальная сложность это термин в теории сложности алгоритмов сложности задачи ограниченная экспонент ный а то многочлен от размерности задача второй вопросом многие из вас спрашивали как на практике генерировать большие простые числа которые требуются для шифрования р.с. эй давайте я быстро расскажу чтобы сгенерировать большое например 100 значное простое число нужно действовать по вот таким инструкциям генерируем некое случайное число проверяем его на простоту если простой алгоритм закончил работу если нет повторяем процесс пока не найдем простое в этом 3 шага вам алгоритме самая важная часть вот это проверка числа на простоту без неё алгоритм не будет работать спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них