Русская Википедия:Кольцевая факторизация
Кольцевая факторизация — это метод создания последовательностей натуральных чисел, взаимно простых с несколькими первыми простыми числами, через использование повторяющихся паттернов в расположении таких чисел, естественно присущих им. Применяется как техника оптимизации в некоторых теоретико-числовых алгоритмах, связанных с простыми числами, таких как факторизация и решето Эратосфена.
Описание
Для выбранного числа n (обычно не больше 4 или 5), первые n простых чисел определяют конкретный способ создания последовательности натуральных чисел, таких что они и только они взаимно просты с этими простыми числами, то есть что они не кратны ни одному из этих простых чисел, а все другие числа кратны какому либо из этих простых чисел.
Таким образом, этот метод применим для улучшения метода пробного деления для целочисленной факторизации, поскольку ни одно из сгенерированных чисел не нужно будет проверять пробными делениями на эти маленькие простые числа, а все числа кратные хоть одному из этих простых чисел будут автоматически пропущены также без всяких делений.
Метод пробного деления состоит в последовательном делении разлагаемого числа на целые числа в порядке возрастания (2, 3, 4, 5, …). Распространённое улучшение состоит в проверке только простыми числами, то есть 2, 3, 5, 7, 11, . . . .
В кольцевой факторизации начинают с небольшого списка чисел, называемого базисом — обычно с нескольких первых простых чисел; затем генерируется список — называемый колесом — целых чисел, взаимно простых с каждым числом из базиса.
Это позволяет впоследствии для чисел, произведённых «катанием колеса», рассматривать как их возможные множители только простые числа не входящие в базис , как будто эти сгенерированные числа уже были проверены, и было обнаружено, что они не делятся ни на одно из простых чисел из базиса. Это является оптимизацией, потому что все эти операции становятся излишними и их можно вообще не выполнять, а все числа которые делятся, пропускаются автоматически также без всяких делений.
При использовании этого метода при поиске простых чисел, или просеивания в общем, этот метод уменьшает количество чисел-кандидатов, которые следует рассматривать как возможные простые числа. С базисом {2} сокращение составляет 1/2 = 50% всех чисел, так как все чётные числа исключаются заранее. С базисом {2, 3} остаются только 2/6 ≈ 33.3% всех чисел, что означает, что 2/3 всех номеров-кандидатов автоматически игнорируются. Бо́льшие базисы уменьшают эту пропорцию ещё сильнее: например, с базисом {2, 3, 5} до 8/30 ≈ 26.7%; а с базисом {2, 3, 5, 7} до 48/210 ≈ 22.9%.
Однако, чем крупнее колесо, тем больше требуется на него вычислительных ресурсов, a добавочные сокращения числа кандидатов получаемые от каждого последующего увеличения колеса становятся всё меньше. Таким образом последующие увеличения колеса быстро становятся невыгодными. В частности, с базисом {2, 3, 5, 7, 11} сокращение числа кандидатов составляет (48*10)/(210*11) ≈ 20.8% то есть выгода по сравнению с предыдущим колесом составляет всего 2%, а длина необходимого для этого базиса возросла в 10 раз.
Пример
Натуральные числа от 1 и выше производятся повторным прибавлением с шагом по 1, начиная с 1:
Рассматриваемые парами, они производятся повторными прибавлениями по 2 к каждому числу в паре, начиная с {1,2}:
Каждое второе так сгенерированное число будет чётным. Таким образом, нечётные числа генерируются повторными прибавлениями по 2 начиная с {1}:
Рассматривая их по три числа, каждое получается повторными прибавлениями по 2 * 3 = 6, начиная с {1,3,5}:
Каждое второе число в этих тройках будет кратно 3-м, потому что все числа вида 3 + 6k являются нечётными числами кратными 3-м. Таким образом, все числа, взаимно простые с первыми двумя простыми числами, то есть взаимно простые с 2 и 3, то есть с 2 * 3 = 6, можно производить повторными прибавлениями по 6, начиная с {1,5}, без 3х:
Эта же самая последовательность может быть сгенерирована повторными прибавлениями по 2 * 3 * 5 = 30, превращая каждые пять последовательных диапазонов по два числа в каждом, в один соединенный диапазон из десяти чисел:
Из каждых десяти этих взаимно простых с 6-кой чисел, два числа кратны 5-и, таким образом, оставшиеся восемь будут взаимно простыми с 30-ю:
Всё это естественным образом обобщается и на последующие простые числа.
Таким образом, здесь мы видим первые три колеса:
- {1} (содержащее одно, то есть (2-1) число) с «окружностью» 2, для создания последовательности чисел взаимно простых с 2, то есть нечётных чисел, путём повторного прибавления по 2;
- {1, 5} (содержащее два, то есть (2-1)*(3-1) числа) с «окружностью» 2 * 3 = 6, для создания последовательности чисел взаимно простых с 6 повторным прибавлением по 6;
- {1, 7, 11, 13, 17, 19, 23, 29} (содержат восемь, то есть (2-1)*(3-1)*(5-1) чисел) с «окружностью» 2*3*5 = 30, для получения последовательности чисел взаимно простых с 30 повторным прибавлением по 30; и т. д..
Эти колеса могут быть представлены и несколько иным способом, а именно, вычисляя разности между последовательными числами, и размещая их в циклическом списке той же длины что и базис. Затем последовательность создаётся начиная с 1 путём повторного прибавления этих разностей одной за другой к последнему произведённому числу, неограниченно, раз за разом. Это ближе всего к метафоре «катящегося колеса».
Например, {1, 7, 11, 13, 17, 19, 23, 29, 31} превращается в {6, 4, 2, 4, 2, 4, 6, 2}, а затем последовательность генерируется начиная с n=1, как
и так далее.
Литература
