Меню

Python генератор простые числа

Ищем простые числа в python — функции генераторы, yeld

Как вы помните простое число — это такое число которое делится только на себя и на 1.
Никаких супер мега методик тут не будет. Я просто постараюсь на примере объяснить значение команды yield .

С начала напишем функцию, которая будет проверять простое это число или нет:

Думаю тут затруднений быть не должно.. Функция просто проверяет в цикле все числа от 2 до проверяемого и если хотя-бы 1 делится без остатка возвращает лож.
Следующей будет самая «интересная» функция этой статьи:

Эта функция генерирует простые числа. Мы в бесконечном цикле (не бойтесь это не повлияет на ресурсы, на самом деле в бесконечность интерпретатор не залезет) проверяем каждое число от 1 и если оно простое заносим его в результат при помощи yield . Эта команда по сути является чем-то вроде функции добавления значений в результат. Тут это неплохо показано на примере.
Ну и теперь используем єто всё:

Для каждого элемента (который мы назвали n) из числа который генерируется в primes(). И выводим все числа меньшие сотни.

Комментарии

Ваш код выдает не только простые числа, он выводит нечетные числа. Следует подправить первую функцию:
def isprime(n):
. if n == 1:
. return False
. for x in range(2, n):
. if n % x == 0:
. return False
. return True

Если я введу двойку то ответ будет Not prime (хотя это Prime). Почему нельзя прописать что если n == 2 то это Prime?

Источник

Простой генератор простых чисел в Python

может кто-нибудь, пожалуйста, скажите мне, что я делаю неправильно с этим кодом? В любом случае, это просто печать «count». Мне просто нужен очень простой генератор (ничего особенного).

22 ответов

  • почему вы распечатываете счет, когда он не делится на x? Это не означает, что он простой, это означает только, что этот конкретный x не делит его
  • continue переход к следующей итерации цикла, но вы действительно хотите, чтобы остановить его с помощью break

вот ваш код с несколькими исправлениями, он печатает только простые числа:

для очень более эффективного главного поколения, см. сетку Эрастотенес, как другие предложили. Вот хорошая, оптимизированная реализация со многими комментариями:

обратите внимание, что он возвращает генератор.

мы получим все простые числа до 20 в списке. Я мог бы использовать сито Эратосфена, но ты сказал вам нужно что-то очень простое. 😉

чтобы проверить, является ли число простым:

здесь простой (Python 2.6.2) решение. что соответствует первоначальному запросу OP (теперь шесть месяцев); и должно быть совершенно приемлемым решением в любом курсе «Программирование 101». Отсюда и этот пост.

этот простой метод «грубой силы» «достаточно быстр» для чисел до около 16 000 на современных ПК (занял около 8 секунд на моем поле 2 ГГц).

очевидно, это можно было бы сделать намного эффективнее, не пересчитывая primeness каждого четного числа, или каждый кратно 3, 5, 7 и т. д. Для каждого ряда. Вижу решето Эратосфена (см. реализацию eliben выше), или даже решето Аткина если вы чувствуете себя особенно храбрым и/или сумасшедший.

предостережение Emptor: я питон нуб. Пожалуйста, не принимайте мои слова за Евангелие.

на мой взгляд, всегда лучше использовать функциональный подход,

поэтому я сначала создаю функцию, чтобы узнать, является ли число простым или нет, а затем использовать его в цикле или другом месте по мере необходимости.

затем запустите простое понимание списка или выражение генератора, чтобы получить список простых,

Это кажется домашним заданием, поэтому я дам подсказку, а не подробное объяснение. Поправьте меня,если я ошибся.

вы отлично справляетесь с тем, что вытаскиваете, когда видите четный делитель.

но вы печатаете «count», как только видите даже один число, которое не делится на него. 2, например, не делится ровно на 9. Но это не делает 9 премьер. Вы можете продолжать идти, пока не будете уверены нет количество в диапазон совпадает.

(Как ответили другие, сито-гораздо более эффективный способ пойти. просто пытаюсь помочь вам понять, почему этот конкретный код не делает то, что вы хотите)

Как насчет этого, если вы хотите вычислить простое число напрямую:

еще один простой пример, с простой оптимизацией только с учетом нечетных чисел. Все сделано с ленивыми потоками (генераторами python).

использование: простые числа = список (create_prime_iterator (1, 30))

оператор continue, выглядит неправильно.

вы хотите начать с 2, потому что 2-это первое простое число.

вы можете написать » while True:», чтобы получить бесконечный цикл.

вам нужно убедиться, что все возможные делители не делят равномерно число, которое вы проверяете. В этом случае вы будете печатать номер, который вы проверяете в любое время, только один из возможных делителей не делит число равномерно.

также вы не хотите использовать оператор continue, потому что continue просто заставит его проверить следующий возможный делитель, когда вы уже выяснили, что число не является простым.

это довольно быстро для больших чисел, так как он проверяет только против уже простых чисел для делителей числа.

теперь, если вы хотите создать список простых чисел, вы можете сделать:

использование генераторов здесь может быть желательно для эффективности.

и просто для справки, вместо того, чтобы сказать:

вы можете создать список простых чисел, используя списочные включения в довольно элегантной манере. Взято из здесь:

похоже на user107745, но использует » все » вместо двойного отрицания (немного более читабельно, но я думаю, что такая же производительность):

в основном он перебирает x в диапазоне (2, 100) и выбирает только те,которые не имеют mod == 0 для всех t в диапазоне(2, x)

другой способ, вероятно, просто заполняет простые числа, когда мы идем:

SymPy является библиотекой Python для символической математики. Он предоставляет несколько функций для генерации простых чисел.

Если вы хотите найти все простые числа в диапазоне, вы можете сделать следующее:

просто добавить while its и ваш номер для диапазона.
Вывод:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101

вот версия numpy сита Эратосфена, имеющая как хорошую сложность (ниже, чем сортировка массива длины n), так и векторизацию.

Источник

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

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

shinenvice034

Active member

Mr Nom4ik

Well-known member

Да вроде бы всё просто:
Исходя из определения, вам нужно просто проверять, делится ли каждое число, меньше заданного, на какие-то меньше себя без остатка.

То есть должно быть 2 цикла, один главный, один вложенный.
В первом перебираются числа от 9 символов —

А вложенный цикл будет пробегать от 2 до этого числа и проверять, есть ли остаток от деления
В целом код может выглядеть так

Если нужно в бесконечном цикле то как-то так

Proxy n1nja

Well-known member

Если честно не очень понял твое условие, но если нужное случайное число от N количества знаков, то могу предложить тебе такой вот вариант

Функция generate_random_number принимает на вход аргумент, какой длины должно быть число и возвращает число, заданной длины. Функция checking_number_prime принимает на вход любое число и возвращает ответ, является ли число простым.

П.С.
На правах рекламы. Подписывайся на нашу группу питонистов кодебая, там тебе всегда помогут [GROUP=14]ТЫК[/GROUP]

Proxy n1nja

Well-known member

PyataCHOK

Active member

Зря ты оправдывался, мой АКЕЛЛА. Маугли щас заступится за вожака.
Алгоритм от F22 также плох, как и твой.
У него даже нет никакого алгоритма, он попросту спрятался за красивыми фразами.
Если бы на основе умозаключений f22 кто-то написал алгоритм и запустил его(алгоритм) то стало-бы очевидным никудышность всего того, что представлено выше.

Между тем, решение давно рассмотрено в учебнике кандидата технических наук, доцента Златопольского Дмитрия Михайловича «Основы программирования на язые Python»
Страница 120 -121.

Во времена совка такие задачи каждый олимпиадник щёлкал в считанные минуты, а не глотал ноотропин с глицином.

Зря ты оправдывался, мой АКЕЛЛА. Маугли щас заступится за вожака.
Алгоритм от F22 также плох, как и твой.
У него даже нет никакого алгоритма, он попросту спрятался за красивыми фразами.
Если бы на основе умозаключений f22 кто-то написал алгоритм и запустил его(алгоритм) то стало-бы очевидным никудышность всего того, что представлено выше.

Между тем, решение давно рассмотрено в учебнике кандидата технических наук, доцента Златопольского Дмитрия Михайловича «Основы программирования на язые Python»
Страница 120 -121.

Во времена совка такие задачи каждый олимпиадник щёлкал в считанные минуты, а не глотал ноотропин с глицином.

Не поленился и нашёл творчество этого автора. Даже страницу нашёл и код перепечатал.

Могу сказать, что вы не правы.
На бОльших объёмах, код приведённый мной показывает лучшие результаты. Можете проверить сами

Источник

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

В продолжение темы, начатой в этой серии статей, сегодня мы поговорим о генерации простых чисел. Генерация бывает вероятностной и бывает гарантированной. Так вот, наш случай — с гарантией, которая позволяет использовать получаемые числа в приложениях, связанных с криптографией, что обеспечивает, например, безопасность распоряжения вашими деньгами через банковские приложения. Далее вы увидите, как гарантированно получать простые числа достаточного для криптографии размера, а так же какими могут быть проблемы, если пренебречь гарантиями.

Общая схема обеспечения безопасности при обмене данными опирается на сложность разложения большого составного числа на множители. При этом если множителей много, то они будут маленькими, а это сильно упрощает взлом системы безопасности. Поэтому большое составное число получают при помощи умножения двух простых чисел определённого размера. Но здесь очевидна одна проблема — как выбрать достаточно большое простое число?

Сначала определимся с размером. В современной криптографии порядок составного числа определяется формулой , то есть собственно порядок равен 2048 в двоичной систем счисления. А делители у этого составного числа бывают порядка 1024, то есть где-то около значений . Почему 1024? Потому что уже лет десять назад было разложено на множители число порядка 768, а сегодня уже весьма вероятно разложение составных чисел порядка 1024. Вот и решено для надёжности увеличить порядок сразу в два раза, то есть до 2048. Ну а отталкиваясь от этого порядка легко определить порядок необходимых сомножителей.

Но что будет, если порядок сомножителей окажется много меньше 1024? Тогда за приемлемое время можно разложить составное число, даже если оно имеет порядок 2048. Значит нужно гарантировать, что выбранные нами сомножители действительно имеют порядок близкий к 1024 и при этом являются простыми, то есть не разлагаются на множители. Но вот сам выбор осуществляется по вероятностной схеме, а это как раз и ведёт к потенциальным проблемам.

Проверка вероятности простоты числа осуществляется на основе предположения о том, что число «скорее всего» простое, если его период (о котором рассказывается здесь) является делителем самого числа, минус единица (). В виде формулы это выглядит так:

Здесь — исследуемое число, — значение от до (оно определяет основание системы счисления, в которой вычисляется период), — период исследуемого числа. Операция здесь означает взятие остатка от деления первого операнда на второй.

Существующие проверки опираются именно на такой подход, поскольку для больших чисел безусловное определение простоты известными тестами занимает очень много времени. Но минус такой проверки очевиден — иногда можно получить составное число, вместо простого. При этом какие делители окажутся в составе такого числа — никто не знает. Точнее это сможет выяснить злоумышленник, применив известные методы факторизации, которые начинают работать за приемлемое время, если множители окажутся порядка менее чем несколько сотен бит.

Как часто ошибается вероятностная проверка простоты? Достаточно редко. Бывает одна ошибка на несколько десятков тысяч простых, а бывает и две, но ничто не гарантирует нас и от трёх. Кроме того, многое зависит от используемого теста. Так, например в стандартной библиотеке языка Java в классе BigInteger реализована проверка, которая допускает промах 2-3 раза на тысячу простых. То есть не стоит думать, что если теоретически ошибок очень мало, то и на практике всё будет в шоколаде.

Чем это опасно? Вроде бы и не так страшно, как могут сказать некоторые, ведь ну что с того, если какой-нибудь сайт, закрывающий просмотр своих страниц протоколом https, получит легко вычисляемый ключ, то какие от этого будут проблемы? Ну узнают хакеры, какие новости вы читали на этом сайте, а что толку? Но на самом деле шифрование производится не только при просмотре веб-страниц. Более неприятная ситуация случится, если хакеры узнают ключ вашего любимого банковского сервиса по дистанционному управлению вашими деньгами. Хотя опять же, вроде бы для того, чтобы наверняка вскрыть обмен с банком (и если банк использует слабую проверку простоты), хакеру придётся ждать примерно 500 лет, пока наконец реализуется вероятность выпуска легко вычисляемого ключа, ведь ключи обычно имеют срок действия 1 год и потому чтобы гарантировать взлом нужно ждать пока не будут проведены 500 выпусков нового ключа. Вроде всё логично, но есть очередное «но» — банков на свете гораздо больше, чем 500 штук. Поэтому прямо сейчас, возможно именно в вашем любимом банке, хакеры могут получить доступ к вашим же деньгам.

Испугались? Наверняка нет, ведь все мы очень смелые, пока жареный петух не клюнет. Но пугаться всё же есть чего. Пусть вероятность успешной атаки хакеров именно на ваш банк и не так высока, но тем не менее, если она реализуется, то ваши деньги наверняка не найдут. Почему? Очень просто — стандартное первое предположение службы безопасности банка — виноват кто-то из сотрудников с соответствующими правами доступа. Не хакер, вероятность вмешательства которого они тоже рассматривают как минимальную, а именно кто-то свой. Поэтому хакер вполне может остаться безнаказанным.

Как устранить эту проблему? Нужно научиться получать гарантированно простые числа. Но как гарантировать их простоту? Для этого существуют четыре метода.

Первый метод — перебор с минимумом ограничений. Обычно это вариант усовершенствованного решета Эратосфена. Метод надёжный и гарантированный, но ограничен очень скромными порядками (менее сотни). Поэтому такой метод неприменим в криптографии.

Второй метод — перебор с более сильными ограничениями. Так, если период числа равен самому числу, минус один, то число гарантированно простое. Формула здесь такая — . Но вот для определения равенства периода разности числа и единицы, используются очень тяжёлые методы, которые работают не для всех классов чисел. Поэтому применение их в криптографии упирается либо в ограниченность количества чисел специфических классов, либо во время выполнения проверки, если мы будем наращивать размер числа. И кроме того, даже числа определённого класса сами по себе ничего не гарантируют, что означает необходимость перебирать много чисел-кандидатов. Вот, например, числа Мерсенна, для которых есть безусловный тест простоты, уже все перебрали и выяснили, что в используемом в криптографии диапазоне их практически нет. Вот весь их список с близкими порядками — 1279, 2203, 2281, 3217. Как вы видите, от 1024 до 2048 есть лишь одно подходящее число. Но даже если взять остальные, то их количество нам очень наглядно намекает — не стоит! Значит опять нам не повезло с методом проверки.

Третий метод — вероятностный. Именно его сегодня используют, в том числе, в вашем любимом банке. Как он работает? Очень просто — проверяется остаток от деления произвольного числа в степени на , если остаток равен единице — вероятно, что число простое. И вот слово «вероятно» здесь наиболее неприятное. И хотя вероятностные методы проверки простоты содержат ещё и дополнительные улучшения, но тем не менее, как было показано выше, стандартная библиотека Java довольно часто ошибается.

И наконец, четвёртый метод. Он работает не так быстро, как вероятностные тесты (хотя и здесь можно кое-что оптимизировать), но зато даёт гарантированно простые числа, да ещё и с легко определяемым периодом. Для чего нужен период простого числа, спросите вы? Например для генерации псевдослучайной или шифрующей последовательности. Точнее, зная период, мы точно знаем, сколько чисел будет в последовательности, что позволяет легко планировать, как долго мы можем использовать генератор последовательности на основе данного числа. Правда это уже относится к симметричному шифрованию, но тоже может пригодиться в ряде случаев. Далее же мы рассмотрим теорию гарантирующей простоту проверки чисел-кандидатов.

Теоретические основы

Чтобы понять, как генерировать гарантированно простые числа, нужно немного погрузиться в математику. Но не пугайтесь, математика здесь на уровне пятого класса.

Для полноты понимания рекомендуется посмотреть здесь подробности о том, что такое период и ряды остатков. Ну а кратко скажем, что ряд остатков образуется при делении «уголком» (известный любому школьнику метод) единицы на выбранное для исследования число. При этом на каждом шаге появляется разность между выше расположенным числом, с дописанным к нему ноликом, и произведением исследуемого числа на значение от 0 до 9 (для десятичной системы счисления) — это и есть остаток. Но шагов при делении «уголком» много, поэтому и остатков тоже много, а вместе они образуют ряд остатков, в котором один и тот же набор чисел периодически повторяется бесконечное число раз. Признаком начала нового цикла является остаток, равный единице. Количество остатков между единицами — это длина периода (или цикла). Вот, собственно, и всё, но также стоит понимать, что такой метод построения ряда остатков можно применить, используя любую систему счисления, и в частности далее чаще всего будет использована система с основанием 2 (а не 10, как принято в школе). При использовании других систем счисления все правила сохраняются, но количество вариантов произведений на каждом шаге будет другим, равным b (от base), то есть основанию системы счисления.

Итак, из ранее показанного мы знаем, что составные числа всегда дают относительно короткие периоды, не включающие ряд «запрещённых» значений. Зная разложение составного числа на множители легко вычислить, сколько значений обязаны отсутствовать в ряде остатков, формирующих период данного числа. Ряд остатков не будет содержать множители и все числа, кратные этим множителям, если сам ряд построен по основанию системы счисления, не кратному ни одному из делителей (то есть основание не делится на делители числа). Например, если множителей всего два, то количество кратных им остатков определяется по формуле , где — количество кратных остатков, и — множители, формирующие наше составное число. Зная количество «запрещённых» остатков, легко вычислить, что ряд остатков длиною более половины значения , будет иметь длину, равную . То есть такой ряд будет на короче, чем ряд, который получился бы, если данное число было бы простым. Это объясняет, почему все числа с периодом, равным полному периоду (то есть ), оказываются простыми — если бы из последовательности остатков был исключён хотя бы один элемент (который «запрещён»), то период стал бы меньше . В результате наличия такой закономерности мы наблюдаем работоспособность всех тех вероятностных тестов, которыми сегодня проверяют простоту числа. Эти тесты вычисляют значения в ряде остатков на позиции или , и если значения равны или , то можно с большой вероятностью утверждать, что число простое. Почему лишь с большой вероятностью, а не гарантировано? Потому что период вероятностные тесты не вычисляют, а между позициями и могут встретиться ещё единицы, что будет означать неравенство периода значению , но если период не равен , то число может быть составным. При этом само по себе отсутствие равенства не критично, важно другое — такое расположение единиц могут дать псевдопростые числа. Среди проверенных таким тестом чисел можно найти псевдопростые, которые являются составными и тем помогают хакерам, ворующим ваши деньги. Ведь каковы делители таких составных чисел? Они вполне могут оказаться достаточно малыми для того, чтобы злоумышленник легко вскрыл зашифрованный обмен данными.

Теперь вспомним, почему вообще могут появляться псевдопростые числа. Такие числа имеют короткие периоды, которые повторяются много раз в пределах полного периода , а потому иногда могут «вмастить» и уложиться целое количество раз в полный период. Так, например, число 25 имеет период длиною 4 для системы счисления с основанием 7. для 25 равно 24, попробуем поделить: 24/4=6. То есть данный период уложился целое число раз в полный период. Этот факт можно проверить по приведённой выше формуле для сокращения периода, но с учётом того факта, что a и b в данном случае одинаковы. Максимально возможный период будет равен 24-4=20, здесь 24 — полное количество остатков, 4 — количество остатков, кратных 5. Но период не всегда бывает максимальным, а все остальные варианты можно получить поделив нацело максимальный период. 20 делится на 2,4,5,10, и как раз при делении 20 на число из приведённого списка мы получаем период длиною 4, который и даёт нам в конце полного периода единицу. А при проверке простоты проверяют как раз значения на позиции , то есть последнее значение в полном периоде. И для 25 оно равно 1, что является признаком простоты числа. Хотя на самом деле однозначный признак простоты, это когда для всех оснований систем счисления, менее , последнее значение в полном периоде равно единице. Но проверять все системы счисления для больших чисел нет никакой возможности, вот и появляются псевдопростые числа, которые иногда используются даже в криптографии, чем повышают уязвимость наших финансов.

Как устранить влияние псевдопростых чисел? В принципе просто — можно проверить периоды для всех систем счисления, но тогда на эту операцию для больших чисел не хватит никакого времени. Поэтому мы пойдём другим путём. И путь тоже простой (в буквальном смысле — в нём используются другие простые числа). Мы видели, что короткие периоды могут уложиться в полный период целое число раз, и это даёт нам псевдопростые числа. Но что нам мешает эти понедельники «взять и отменить»? Да в общем-то, ничего не мешает.

Для существования коротких периодов полный период () должен делиться на много делителей. Так для числа 25 полный период 24 делится на 2, 3, 4, 6, 8, 12. Вот столько есть возможностей для проникновения на охраняемую территорию псевдопростых чисел. Значит нам нужно просто взять в качестве полного периода простое число, ведь оно вообще ни на что не делится и потому автоматически спасает нас от вражеского элемента. Правда есть одно «но» — нам нужны простые числа, а они, как известно, нечётные (кроме одного исключения — 2), значит если простое, то само простым уже быть не может. Поэтому нам придётся допустить возможность для появления неполных периодов. Чем это плохо? Как мы видели выше — полный период гарантирует простоту числа, а вот про неполный — мы пока не доказали. Значит нам нужно доказать данный момент.

Доказательство довольно простое — для составного период, длиною, укладывающейся в два раза, полученный в системе счисления, не кратной делителям N, имеет всего два ряда остатков, и ни один из них не должен содержать чисел, кратных делителям числа («запрещённых» чисел). Если исключается хоть один элемент из одного ряда остатков, то и второй автоматически уменьшается на столько же (ведь один ряд равен другому, домноженному на любое число, отсутствующее в первом). Значит при наличии делителей у числа , мы получим меньшую суммарную длину двух периодов со всеми «разрешёнными» остатками, нежели значение полного периода и тем самым сдвинем единицу с места в конце полного периода, чем обеспечим отсутствие псевдопростоты. Но может ли количество кратных делителям остатков оказаться таким, чтобы дать ровно половину или одну треть полного периода? Ведь тогда мы получили бы, например, две трети «разрешённых» остатков (два ряда) и одну треть «запрещённых», а в сумме — полный период. Но для получения одной трети нам нужно обеспечить делимость полного периода () на 3, что мы можем довольно легко исключить — берём простое число, умножаем его на два и прибавляем к результату единицу — вуаля, перед нами гарантированно исключающее псевдопростоту число. У него количество кратных делителям остатков не может быть равным одной третьей полного периода, потому что на три полный период не делится. Остаётся вариант с половиной остатков, кратных делителям . Этот вариант устраняется чуть сложнее, поэтому ниже будет небольшое отступление.

Вычисление периода, или все числа — дети Мерсенна

Период любого числа можно вычислить. В простейшем случае вычисление производится простым делением уголком до тех пор, пока нам не встретится остаток, равный единице (в системе счисления, не кратной делителям ). Но для больших чисел это нереально долго. Поэтому есть необходимость в выводе формулы для вычисления периода. И такая формула существует, правда не в идеальном виде, когда на входе имеем число, а на выходе — период. Формула такая:

Здесь — исследуемое число, — основание используемой системы счисления (base), — максимальная степень , при которой результат возведения в степень меньше (по другому — индекс старшего разряда в в системе счисления ), — расстояние слева направо в ряду остатков от индекса (равного количеству разрядов в ) до единицы, — некоторый целый коэффициент.

Вывод формулы

По определению формулы понятно, что (1) , то есть первая степень , которая больше , позволяет вычесть и получить некую разницу в виде . Так же из определения следует, что (2) , здесь — целочисленный коэффициент. Если домножить (1) на и заменить на его значение из (2), которое равно , то получим N=\frac-1>$» data-tex=»inline»/>.

Полезные свойства

Как мы видим, используя эту формулу можно получать числа с заранее известным периодом. Правда есть одна сложность — нужно подбирать коэффициент , что для больших чисел опять превращается в нечто недостижимое. Но формула даёт нам другое — мы наглядно видим, как формируются все числа. Да, абсолютно все положительные целые числа можно получить по этой формуле, ведь у всех чисел есть какой-то период. И что интересно — все числа получаются от деления числа Мерсенна на один из его делителей. Вспомним, что числом Мерсенна называется такое число, которое равно . В формуле же в числителе мы видим обобщение для чисел Мерсенна с любым основанием (включая 2, разумеется). И если нас интересуют простые числа, то другие основания, кроме 2, нам вообще не понадобятся.

Зная, что мы делим число Мерсенна, нам было бы полезно уметь вычислять период чисел именно для случая деления чисел Мерсенна (вспомним расширенное понятие периода здесь). Но что очень замечательно — формула для вычисления мерсенновского периода совпадает с формулой для вычисления периода типа . Ну а для вывода формулы деления чисел Мерсенна используется тот же принцип, что и при выводе формулы для деления , за исключением формулы для вычисления значения в ряде остатков с индексом , которая выглядит так — , а для двоичных чисел получаем .

Теперь у нас все карты на руках и мы можем начинать игру по вскрытию псевдопростых засланцев в рядах простых чисел.

Как мы знаем из предыдущих серий, при делимости нацело мерсенновский период числа должен укладываться в количество разрядов числа Мерсенна целое число раз. Поэтому в формуле выше решение в целых числах возможно лишь если знаменатель имеет период либо равный числителю, либо кратно меньший. Но кратно меньший период даст нам, в том числе, и делители самого числа , ведь если делит число Мерсенна, то значит и его делители тоже делят число Мерсенна. И это очень важный момент, ведь из него вытекает, что длины периодов делителей N делят длину периода нацело. То есть если мы возьмём такое, что его период равен периоду числителя, тогда все делители будут одновременно и делителями числа Мерсенна, а потому должны укладываться в период и , и числа Мерсенна целое число раз.

Снова про половину периода

Теперь вспомним, что мы остановились на поиске способа доказать, что мы можем исключить случай, когда половина длины ряда остатков числа кратна его делителям. Доказать мы это хотели для устранения псевдопростых чисел при выборе одного простого числа в качестве основы для конструирования периода следующего простого числа. Так вот теперь мы знаем, что если конструируемое число имеет делители, то их периоды всегда делят период конструируемого числа нацело. Тогда нам остаётся проверить — какие делители могут уложиться в ранее заданные ограничения на конструируемое число. А ограничения такие — его период делится лишь на и на . Значит и делителями могут быть лишь числа с периодами и . Период имеет число , более ни одно число такого периода не имеет. Период не укладывается целое количество раз в , ведь — простое, поэтому делимость на три исключается при таком периоде. Значит остаётся лишь одна возможность — делители имеют период . Но число не может быть меньше или равно своему периоду, поэтому минимальное значение для делителей такое — . Если перемножить два минимальных делителя, то получим — , такое значение должно быть не больше , ведь мы говорим о делителях . Тогда получаем неравенство N^2-2N+1\leq 0$» data-tex=»inline»/>. Это неравенство может быть отрицательным или равным нулю только при , поэтому для всех сконструированных таким способом чисел псевдопростота исключена, если полученное число больше . Ну а для меньших чисел мы можем проверить простоту даже в уме.

Теперь есть два варианта — новое число простое число, что нам и требовалось, либо это число составное и тогда его период не укладывается целое число раз в полный период, а потому такое число легко проверить на простоту, вычислив последнее значение в полном ряду остатков. То есть сконструированное число можно смело проверять стандартными вероятностными тестами простоты, и что важно, результат теста будет уже не вероятностный, а гарантированный. Вот так в итоге мы освободились от проклятия псевдопростоты, давлеющей над всеми вероятностными тестами.

Но конечно, жизнь была бы мёдом, если бы все проблемы решались так просто. Исключив псевдо-простоту, мы так и не исключили числа, которые ни от кого не прячутся и ни подо что не маскируются. А с ними есть ещё одна проблема — мы пока что умеем проверять произвольный член последовательности остатков лишь при помощи возведения в степень с последующим взятием остатка. Но такой метод очень медленный. Точнее, он достаточно быстр для чисел, используемых в криптографии, но вот для поиска больших простых он не пригоден в домашних условиях, ибо требует много лет вычислений обычного домашнего компьютера, что не даёт нам возможность получить 400k$ (как показано здесь).

Но тем не менее, для вычисления криптографических простых у нас уже почти всё готово. Хотя остаётся ещё наш старый друг — максимализм. Он спрашивает — раз можно использовать период , то что мешает использовать периоды и т.д.? И оказывается, что при должной осторожности — ничего не мешает!

Точно так же, как и в случае с периодом , для периода имеем возможность задать ограничение снизу, умножив простое число на 4 и прибавив 1. Тогда мы гарантируем себя от псевдопростых с периодами менее . Значит остаётся рассмотреть возможность появления псевдопростых с периодом, кратным 4, 3, 2 (1 для составных исключается, как показано выше). Из формулы для вычисления числа по периоду видно, что период делимого числа должен быть равен наименьшему общему кратному его делителей, из чего следует, что возможный период числа должен не только укладываться целое количество раз в (иначе не будет псевдопростоты), но и содержать в себе целое количество периодов делителей. Таким образом резко ограничивается количество возможных делителей псевдопростого числа. Поскольку период любого числа не может быть длиннее , то для возможного делителя , дающего в результате деления 3, период не может быть длиннее , кроме того учтём, что период числа 3 равен 2. должно быть нечётным, поскольку нечётным является . Из перечисленного следует, что чётный период N/3-1 является наименьшим общим кратным с периодом 2 числа 3, значит возможный период потнециально псевдопростого N должен быть равен периоду числа . Всего есть одно значение величины периода , для которого возможна псевдопростота, это . Для остальных значений либо слишком мало, либо его период (а вместе с ним и период ) уйдёт в запрещённую область ниже . Такая же история и с нечётными числами, меньше , но у них периоды не могут быть больше , а потому все они просто исключаются из рассмотрения. Теперь покажем, что не может иметь период , а значит не может делить полный период нацело. Сначала вспомним формулу , которая даёт нам количество кратных делителям остатков для числа, делящегося только на и . В нашем случае , как предполагается, может делиться на и на 3, все остальные делители исключены, поэтому получаем — . Теперь из полного периода нужно вычесть «запрещённые» значения, которых будет , а потом разделить на 4. Получаем возможный период произведения : , что меньше , то есть период длиной невозможен из-за необходимости учитывать «запрещённые» остатки, которая уводит все возможные псевдопростые периоды в запрещённую область (меньше ). Значит такая ситуация гарантирует нам, что сконструированное число не псевдопростое, а потому мы снова можем быть уверены в результатах последующего вероятностного теста простоты.

Аналогично, и с учётом делимости полного периода, можно получить такие же результаты и для других значений. Но если мы хотим так получать криптографические простые числа, то домножая на 2,4,6 мы будем очень долго наращивать размер числа, поэтому есть смысл посмотреть в сторону другого варианта — умножения двух простых чисел. Если мы умножим одно простое на другое, то получим нечётное число, поэтому обязательно нужно домножить ещё и на 2, чтобы получить чётный полный период и нечётное число-кандидат в простые. Полный период в таком случае будет делиться на , где и — простые числа. Теперь нам нужно доказать, что либо указанные периоды не дадут псевдопростоты, либо обнаружить признаки, предупреждающие нас о наличии псевдопростоты. Сразу заметим, что если период будет равен , то число будет простым (как показано выше). Так же выше показано, что число с половинным периодом не может быть псевдопростым, поэтому период длиной можно исключить. Хотя для полноты картины можно проверить период альтернативными способами. Так, если период равен , то учитывая, что и простые, становится понятно, что наименьшее общее кратное периодов делителей может быть равно только , при этом периоды делителей могут быть равны либо у обоих, либо у одного , а у другого . Поскольку период всегда меньше самого числа, то явно будет больше . Значит и псевдопростота при таком периоде невозможна. Поэтому остаётся проверить периоды . 2 меньше минимального возможного периода периода для всех чисел, больше 3, поэтому такой период исключаем. Теперь предположим, что сконструированное число делится на и , тогда при равенстве периода значению , их периоды тоже будут равны , потому что это единственное наименьшее общее кратное для двух чисел, ведь не делится ни на что. Отсюда вытекает, что , где — первый возможный сомножитель с периодом , и — второй. Далее: $» data-tex=»inline»/> $» data-tex=»inline»/> . Здесь может быть равен только единице, иначе слева не получится целое число. Тогда: , из чего следует, что если , то псевдопростых с периодом быть не может. Остаётся проверить псевдопростоту при , что можно сделать проверкой значения в ряду остатков на позиции , если там 1, то такое число может быть псевдопростым и его стоит исключить из дальнейших операций. Рассуждения для полностью аналогичны, что означает необходимость проверки равенства единице и его остатка при условии .

Для периода имеем: $» data-tex=»inline»/> $» data-tex=»inline»/> $» data-tex=»inline»/> . Получаем, что при (или эквивалентно — ) опять не может быть простоты, но если , то нужно проверять остаток на позиции . Аналогично и для — проверяем если и для необходимость выполнить проверку лишь для позиций и , потому что периоды и дадут повтор как раз в положении и . Проверку выполняем лишь при указанных выше условиях, что почти в два раза ускорит процесс при проверке больших значений или , ведь для них обязательно выполняется при предложенной ниже схеме генерации простых, а меньшие значения будут проверяться очень быстро из-за их небольшой величины.

Таким образом выше были показаны теоретические основы для получения возможности генерировать гарантированно простые числа для таких критичных областей, как криптография.

Кроме того, открывается путь для проверки простоты произвольного числа, при условии нахождения делителей его полного периода (). Так, для простых чисел

Источник

Adblock
detector