Тест простоты Ферма

итак наша цель определить последовательность действий которые могут либо точно доказать является ли некое входное целое число составным либо определить его как простое с достаточно большой устраивающие на степенью достоверности этот алгоритм должен быть достаточно эффективным и быстрым на любом устройстве при этом ни замедляться с увеличением размера входных данных то есть с увеличением входного числа и мы с вами уже пришли к выводу что нам может помочь некая закономерность который соответствует все простые числа и очень немногие составные в прошлом видео ролике мы с вами наглядно разобрали малую теорему ферма из нее следует очень интересное правило возьмем некое простое число p и некое целое число а которая будет меньше п тогда p будет являться делителем а в степени b минус a чаще всего это правило записывают немного иначе а в степени b равно а по модулю п поскольку у чисел а и b нет общих делителей ведь п у нас простое число то можно разделить обе части на а такая запись теорема тоже иногда встречается а в степени p минус 1 равно единице по модулю п и я повторюсь мы так сделали только потому что наибольший общий делитель чисел a и p единица перед вами наглядная демонстрация этого принципа чтобы вы посмотрели как он работает если в качестве я беру простое число в результате всегда получается единица какое бы число а мы не взяли а если в качестве б у нас была бы составное число тогда единица будет получаться очень редко и каждый раз когда в результате получается не единица это будет доказательством того что число p составное то есть данное нам число не может быть простым и это основа нашего теста прежде чем углубиться в детали давайте сделаем шаг назад и выпишем последовательность действий для нашей проверки и так на входе мы получаем некое целое число п мы генерируем некое случайное число а меньшие числа p затем мы ищем наибольший общий делитель a и p и проверяем равен ли он единицы если нет если наибольший общий делитель чисел а и b больше единицы значит у них есть общий делитель и тогда мы доказали что число p составное все работа алгоритма закончена число p составное но если делителя нет тогда возникает ключевой вопрос равняется ли а в степени b минус 1 единицы по модулю п если нет это верный признак что p составное все останавливаем работу p составное то есть если наша формула выдала единицу то получается что п простоя верно я запрограммировал эту последовательность действий и слева у меня тест фирма а справа стандартный алгоритм проверки делимости мы точно знаем что перебор всех возможных делителей никогда не ошибается и на первый взгляд кажется что тест фирма работает однако вскоре обнаружилась проблема я вел число 511 и тест фирмы говорит что оно простое а проверка делимости что оно составное с точки зрения теста фирма число 511 кажется простым но оно составное давайте вернемся к нашей формуле и посмотрим что случилось перед нами пример так называемого псевдо простого числа это составное число но существуют такие значения а при которых формула выдаст единицу и тест ошибется такие значения а при которых формула выдаст единицу для составного числа мы назовем обманками они нас обманывают и заставляет думать что число p составное но обратите внимание если выбрать другое значение а мы обнаружим много доказательств того что число p составное может тогда попробовать поступить так же как когда мы пытались оптимизировать алгоритм проверки делимости а именно повторить эксперимент несколько раз генерируя все новые значения для а и на есть что у нас не будут попадаться дни обманки доказано что количество обманок является делителем общего количество целых чисел из которых мы выбираем а иными словами обманок выборки не больше половины если мы выбираем значения а случайным образом то вероятность найти доказательства делимости как минимум 1 2 после т повторения этого алгоритма вероятность того что для составного числа нам будут снова и снова попадаться одни обманки не превышает единица деленные на 2 в степени t то есть после 20 попыток и вероятность ошибочно назвать составное число простым меньше одной миллионной это значит что нам очень очень не повезло и мы все двадцать раз выбирали только обманки если подумать что у нас получился очень мощный инструмент давайте посмотрим на тест в действие увеличим количество проверок и кажется что теперь он работает идеально обратите внимание даже в самом худшем случае то есть когда у нас на входе большое простое число тогда алгоритм производит максимальное количество действий однозначно тест фирма несравнимо эффективнее проверки делимости в частности потому что количество проверок не увеличивается с увеличением входного числа и в этом главное различие мы сами устанавливаем количество проверок и все можно не волноваться что наш алгоритм в какой-то момент зациклиться на миллионе итерации как случалось раньше это пример квинтэссенции прикладной математики мы берем открытую кем-то закономерность и значительно сокращаем вычислительную нагрузку однако в этой системе есть один небольшой изъян сможете его найти спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них