Мобильная версия1. Его можно использовать для отрицания простоты очень больших составных чисел (конечно, также и меньших) путем их эффективного факторизации. Как хвастаются создатели алгоритма:
«Он характеризуется минимально возможной вычислительной сложностью». Однако они не дают общепринятых обозначений зависимости сложности вычислений от размера тестируемых чисел.
2. либо получить подтверждение простоты: по замыслу авторов, программа укажет все делители составного числа, а если таковых не найдет, то обеспечит стопроцентную уверенность в том, что проверяемое число является простым.< бр />
Одной из причин принятия использованного алгоритма стало обнаружение того, что компьютер выполняет умножение быстрее, чем деление, а это довольно большая разница, составляющая несколько десятков процентов.
Самый простой метод факторизации, но подходящий только для небольших чисел, — попытаться разделить проверяемое число на все последующие, все более крупные простые числа.
В алгоритме «первичное решето» эти числа на первом ходу умножаются, а затем проверенное число делится на полученное произведение.
Это дает заметную экономию в расчетах, поскольку тогда n чисел умножаются сами на себя, и тогда остается только одно деление (с остатком).
С другой стороны, в наивном методе выполняется n последующих операций деления.
Важно, что это выбранные числа, а именно произведение последовательных простых чисел, т.е. функция, называемая примориальной. Разработчик конкретной реализации имеет некоторую свободу в выборе размера/высоты примитива, но авторы рекомендуют, чтобы он был большим, но не превышающим емкость базовой переменной, используемой в данный момент, например кватро-целое (32 бита, т.е. ˜4295 миллионов, десятичное число, построенное из 10 цифр — и это размер, на который мы делим число при его тестировании). Стоит отметить, что ценность первобытного, с ростом его аргумента - растёт быстро] в сотни раз быстрее факториала!
По этой причине авторы использовали «многоэтажную» процедуру: как и выше, вам придется делать это «на первом этаже» процедуры, что стоит отметить, поскольку на следующих этажах основная функция заменяется на еще один: перейдя на первый этаж, авторы вводят новую функцию, которую они называют Van-guard, сокращенно Van — и обозначают ее знаком # перед двумя аргументами, с которыми она работает.
Ван → #(p₁ ; p₀) = p₁# : ( p₀#) где p# — основная функция, и, конечно же, p₀ < p₁
На следующем, более высоком этапе процедуры, тестируемое число (прошедшее предыдущие тесты) делится на #p₂, что дает:
а : #p₂ = b ⋅ #p₂ + r
— где r — остаток от деления. Затем проверяется, что r не имеет общих делителей ни с b, ни с #p₂
, и если есть хотя бы один такой делитель (обычно больше, не менее 2), то a также делит их, поэтому оно явно не простое. Однако если мы не получим исключающий ответ (т.е. отрицание приоритета проверяемого номера), мы должны перейти на следующий, более высокий этаж, используя новый журнал, полученный по формуле:q₃ = p₂# : p₁#
Вся процедура по сути сводится к следующему, шаг за шагом — проверке, имеет ли единственный остаток от деления, полученный на последующих этажах (один за другим), какие-либо общие делители с числом b, или с числом pₙ. Следовательно, это перенос проблемы в область сравнительно небольших чисел и достаточно простых алгоритмов (подпрограмм). Когда остаток от деления на данном этаже имеет эти общие делители, то проверяемое число делится на них, а полученный результат далее факторизуется, действуя поэтапно, пока проверяемое число не будет полностью разложено на множители.
Следует подчеркнуть, что чем из большего количества цифр состоят делители, используемые на последующих этажах, тем они крупнее — тем меньше шагов нам придется совершить, чтобы полностью факторизовать проверяемое большое многозначное число (или доказать его первичность).
____
В настоящее время невозможно определить авторство вышеописанной процедуры, поскольку подпись под отчетом хотя и имеется, но явно является псевдонимом, содержащим несколько аллюзий. Николя РаБарбар(ы)ки («рабарбар» по-польски — ревень) напоминает Николя Бурбаки, который на самом деле представлял собой целую группу французских математиков, публиковавшихся вместе под этим псевдонимом. Поэтому можно предположить, что РаБарбар(ы)ки – это тоже коллективный орган. А примечание, добавленное ниже, — видимо, относится к Шотландской Книге, а также упоминает ее местонахождение, т. е. Львов. Эта Книга также была коллективным трудом и представляла собой польскую Львовскую школу математики|Львовскую математическую школу, добившуюся больших успехов в межвоенные годы.
Подробнее: https://en.wikipedia.org/wiki/Primorial_sieve