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

Описание

Для выбранного числа 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:

1, 2, 3, 4, 5, ...

Рассматриваемые парами, они производятся повторными прибавлениями по 2 к каждому числу в паре, начиная с {1,2}:

1, 2  ;  3, 4  ;  5, 6, ...

Каждое второе так сгенерированное число будет чётным. Таким образом, нечётные числа генерируются повторными прибавлениями по 2 начиная с {1}:

1  ;  3  ;  5  ;  7 ...

Рассматривая их по три числа, каждое получается повторными прибавлениями по 2 * 3 = 6, начиная с {1,3,5}:

1, 3, 5  ;  7, 9, 11  ;  ...

Каждое второе число в этих тройках будет кратно 3-м, потому что все числа вида 3 + 6k являются нечётными числами кратными 3-м. Таким образом, все числа, взаимно простые с первыми двумя простыми числами, то есть взаимно простые с 2 и 3, то есть с 2 * 3 = 6, можно производить повторными прибавлениями по 6, начиная с {1,5}, без 3х:

1, 5  ;  7, 11  ;  13, 17  ;  ...

Эта же самая последовательность может быть сгенерирована повторными прибавлениями по 2 * 3 * 5 = 30, превращая каждые пять последовательных диапазонов по два числа в каждом, в один соединенный диапазон из десяти чисел:

1, 5, 7, 11, 13, 17, 19, 23, 25, 29  ;  31, 35, 37, ...

Из каждых десяти этих взаимно простых с 6-кой чисел, два числа кратны 5-и, таким образом, оставшиеся восемь будут взаимно простыми с 30-ю:

1, 7, 11, 13, 17, 19, 23, 29  ;  31, 37, 41, 43, 47, 49, ...

Всё это естественным образом обобщается и на последующие простые числа.

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

• {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 , как

n=1; n+6=7; n+4=11; n+2=13; n+4=17; n+2=19; n+4=23;

n+6=29; n+2=31; n+6=37; n+4=41; n+2=43; ...

и так далее.

Литература

• Pritchard, Paul (January 1981). . Commun. ACM (англ.) . New York, NY, USA: Association for Computing Machinery. 24 (1): 18—23. doi : . ISSN . Дата обращения: 3 июня 2023 .

См. также

• Решето Эратосфена
• Решето Аткина