Данная статья является продолжением статьи «Задание числовых рядов и последовательностей с простыми числами и формулы простых чисел» [1].
В элементарной теории чисел к одному из основных ее направлений относят малую теорему Ферма, которая утверждает, что если р – простое число и а – целое число, не делящееся на р, то ар-1-1 делится на р.
В настоящее время в понятиях и символьных обозначениях теории сравнений это утверждение обычно сводится к простому выражению (1):
aр-1 ≡ 1 (mod p), (1)
которое означает, что ар-1 сравнимо с 1 по простому модулю р.
Наряду с этой формулировкой малой теоремы Ферма так же используется ее несколько видоизмененный вариант, который отличается отсутствием требования, чтобы число а не делилось на р, но является более слабым утверждением:
Если р – простое число, то для каждого целого числа а будет справедливо сравнение (2).
aр≡ a (mod p), (2)
Можно отметить, что непонятны причины столь распространенного использования в формулировке малой теоремы Ферма понятий и символьных обозначений теории сравнений. Обоснования целесообразности их применения в данном случае отсутствуют. В работе [2] было показано, что никакой необходимости применять понятия и символьные обозначения теории сравнений не существует, и для подобных целей проще и удобнее использовать обычную формулу, выполняющую процедуру замены исходного числа остатком от его целочисленного деления на модуль. В связи с этим ниже приведен третий вариант формулировки малой теоремы Ферма, содержащий формулу, выполняющую процедуру замены исходного числа остатком от его целочисленного деления на модуль. В этой формуле роль модуля выполняет число р.
Если р – простое число, то для каждого натурального числа а, не делящегося на число р, будет выполняться равенство (3).
aр-1-р·[aр-1/р] = 1, (3)
где [ ] – знак, обозначающий целую часть числа или обозначает операцию по отбрасыванию дробной части от результата вычисления выражения, стоящего в прямоугольных скобках (здесь и далее по тексту).
Теорема сформулирована в 1640 году Пьером Ферма и впоследствии в разное время было предложено сравнительно много различных вариантов ее доказательства.
Большое значение малой теоремы Ферма связано, прежде всего, с тем, что в ней впервые был сформулирован признак простоты произвольного натурального числа. Использование, которого позволяет определять простоту числа без нахождения нетривиальных делителей числа, что обычно требует выполнения значительных объемов вычислений и, соответственно, очень больших затрат времени. Это обстоятельство предопределило большую значимость теоремы для решения ряда практических задач, в которых требуется обеспечить возможность быстрого нахождения больших простых чисел.
В связи с этим, естественно, что на основе малой теоремы Ферма был разработан, так называемый, тест простоты Ферма:
Если р — простое число, то оно удовлетворяет сравнению (1) для любого а, которое не делится на р.
Но, к сожалению, оказалось, что выполнение сравнения (1) является необходимым, но недостаточным признаком простоты числа. То есть, если найдётся хотя бы одно а, для которого сравнение (1) не выполняется, то число р будет составным, в противном случае число р с некоторой вероятностью может оказаться как простым, так и составным. Здесь уже, по умолчанию, предполагалась принципиальная невозможность вычисления, всех значений остатков от целочисленного деления aр-1 на число р для всех возможных чисел а.
Составное число р, для которого выполняется сравнение (1) называют псевдопростым по основанию а. И при проверке числа на простоту тестом Ферма стараются выбрать как можно больше чисел а. Так как чем больше количество чисел а, для которых выполняется сравнение (1), тем больше вероятность того, что число р простое. И в результате тест Ферма стал считаться первым вероятностным тестом, то есть тестом, который даёт ответ о составности числа либо его несоставности лишь с некоторой вероятностью.
При этом никаких доказательств того, что тест Ферма является именно вероятностным тестом, никогда не приводилось. Если принять, что тест Ферма является лишь вероятностным, то это будет означать отсутствие возможности вычисления, всех значений остатков от целочисленного деления aр-1 на число р для всех чисел а. И действительно, может показаться, что такой возможности нет, так как число а может принимать бесконечное число значений, а именно, в качестве чисел а можно использовать все натуральные числа по порядку, ряд которых, как известно, бесконечен.
Однако это не так. Потому, что левая часть равенства (3) представляет собой функцию (4) для вычисления значений остатков y от целочисленного деления aр-1 на число р при изменении а.
y = aр-1-р·[aр-1/р], (4)
А функция вида (4) представляет собой так же ещё и периодическую импульсную функцию с периодом равным р [2, 3]. Это означает, что все возможные значения остатков y можно вычислить при помощи уравнения (4) уже в пределах первого периода, то есть при последовательном изменении значений числа а от нуля до р. Во всех последующих периодах значения остатков y просто будут повторяться. Для пояснения этого обстоятельства можно представить значение числа а в виде выражения (5).
a = k·р + l, (5)
где k – порядковый номер периода, принимает значения 0, 1, 2, 3,... и так далее до любого целого числа, l – любое целое число от нуля до р.
Теперь выражение aр-1 можно по известной формуле бинома Ньютона разложить на отдельные слагаемые:
aр-1 = (k·р + l)р-1 = (k·р)р-1 + (р-1)·l·(k·р)р-2 +...+ lр-1
Для целей данной статьи достаточно записать частичную сумму слагаемых, как результат применения этой формулы. Все эти слагаемые, кроме lр-1, всегда кратны р, что позволяет сделать следующие преобразования:
(k·р)р-1 + (р-1)·l·(k·р)р-2 +...+ lр-1 = р·(kр-1·рр-2 + l·(р-1)·kр-2·рр-3 +...) + lр-1
B = kр-1·рр-2 + l·(р-1)·kр-2·рр-3 +...
aр-1 = (k·р + l)р-1 = р·B + lр-1 (6)
Подставив полученное выражение (6) для вычисления значений ар-1 в уравнение (4) приведем его к виду (8).
y = р·B + lр-1 - р·[(р·B + lр-1)/р] (7)
Поскольку р·B точно делится на р, то из выражения (7) можно удалить все слагаемые р·B.
y = lр-1 - р·[lр-1/р] (8)
Из уравнения (8) следует, что будет и справедливо сравнение (9).
aр-1 ≡ lр-1 (mod p) (9)
Также из уравнения (8) следует, что все возможные значения остатков y зависят не от всего числа a, а только от его части l. Число l, в отличие от бесконечного числа a, конечно. Как уже было указано выше, оно может принимать значения только в пределах диапазона от нуля до p. Впрочем, из этого диапазона следует удалить значения l, при которых уравнение (8) будет возвращать тривиальные значения остатков y. Это значения l, равные нулю и p, при которых y будет всегда равен нулю, а также значения l, равные 1 и p-1, при которых y будет всегда равен единице.
Поскольку l конечное число, то всегда можно, пусть и за очень большое время в случае проверки больших чисел, но все же вычислить значения всех возможных остатков y. И тем самым не с некоторой вероятностью, а точно доказать или опровергнуть, с помощью малой теоремы Ферма, простоту числа p. Это означает, что тест простоты Ферма, основанный на малой теореме Ферма, отнесли к вероятностным тестам ошибочно. Этот тест простоты все же является истинным тестом, так как всегда может обеспечить в ходе своего применения однозначное подтверждение или опровержение факта простоты проверяемого числа.
Разумеется, для того чтобы малую теорему Ферма можно было использовать в качестве истинного теста простоты ее формулировка должна быть изменена:
Число p – простое тогда и только тогда, когда для каждого натурального числа a из диапазона от 2 до p-2 будет справедливо сравнение (1).
Очевидно, что перебор всех значений числа a из диапазона от 2 до p-2 потребует значительных затрат времени, особенно для больших чисел p. Поэтому, естественно, что возникает вопрос, а нельзя ли сократить этот диапазон? Для ответа на этот вопрос необходимо установить, как изменяются значения остатков y при изменении числа a в пределах диапазона от 0 до p, то есть в пределах одного периода периодической функции (4).
Поскольку требуется рассмотреть изменения значений остатков y только в пределах одного периода, то выражение (5) можно упростить:
a = р - l, (10)
где l – любое целое число от нуля до p.
Теперь выражение aр-1 можно разложить на отдельные слагаемые:
aр-1 = (р - l)р-1 = рр-1 - (р-1)·l·рр-2 +...+ lр-1
Все эти слагаемые, кроме lр-1, всегда кратны p, что позволяет сделать следующие преобразования:
рр-1 - (р-1)·l·рр-2 +...+ lр-1 = р·(рр-2 - l·(р-1)·рр-3 +...) + lр-1
B = рр-2 - l·(р-1)·рр-3 +...
aр-1 = (р - l)р-1 = р·B + lр-1 (11)
Подставив полученное выражение (11) для вычисления значений ар-1 в уравнение (4) приведем его к виду (13).
y = р·B + lр-1-р·[(р·B + lр-1)/р], (12)
Поскольку р·B точно делится на р, то из выражения (12) можно удалить все слагаемые р·B.
y = lр-1-р·[lр-1/р], (13)
Из уравнения (13) следует, что будет и справедливо сравнение (14).
aр-1 ≡ lр-1 (mod p) (14)
Так как значение a определяется по формуле (10), то сравнение (14) можно записать в виде сравнения (15).
(р - l)р-1 ≡ lр-1 (mod p) (15)
Очевидно, что из формулы (10) следует, что при изменении l от нуля до p значение a будет изменяться от p до нуля.
Например, если p=9, то l и a будут соответственно принимать следующие значения: 0 и 9; 1 и 8; 2 и 7; 3 и 6; 4 и 5; 5 и 4; 6 и 3; 7 и 2; 8 и 1; 9 и 0.
При этом в соответствии со сравнением (15) остатки y по основаниям a, равным l и p-l всегда будут равны друг другу. Таким образом, все возможные значения остатков y можно вычислить при помощи уравнения (4) уже в пределах первой половины периода p, то есть при последовательном изменении значений числа a от нуля до (p-1)/2. При последовательном изменении значений числа a на второй половине периода p, от (p+1)/2 до p все значения остатков y повторятся и никаких новых значений не появится. Причем значения остатков будут расположены строго симметрично относительно середины периода.
Например, если p=21, то основание a и остаток y будут соответственно принимать следующие значения: 0 и 0; 1 и 1; 2 и 4; 3 и 9; 4 и 16; 5 и 4; 6 и 15; 7 и 7; 8 и 1; 9 и 18; a=(p-1)/2=(21-1)/2=10 и 16; a=(p+1)/2=(21+1)/2=11 и 16; 12 и 18; 13 и 1; 14 и 7; 15 и 15; 16 и 4; 17 и 16; 18 и 9; 19 и 4; 20 и 1; 21 и 0.
Необходимо отметить, что с учётом нуля только периоды для нечетных p делятся пополам и поэтому свойства периодов для четных p будут отличаться. Но поскольку простых четных чисел, за исключением двойки, не бывает, то и применять к ним малую теорему Ферма нет необходимости.
Таким образом, из изложенного следует, что для любого нечетного числа p будет справедливо сравнение (16) для всех оснований a от нуля до (p-1)/2.
aр-1 ≡ (p-a)р-1 (mod p) (16)
Если же число p будет ещё и простым, то всегда будут справедливы сравнения (1) и (17).
(p-a)р-1≡ 1 (mod p) (17)
Исходя из этого общее количество чисел a, необходимых для полного тестирования числа на простату при помощи малой теоремы Ферма можно сократить в два раза. С учётом этой возможности формулировку малой теоремы Ферма, пригодной для использования в качестве истинного теста простоты, можно оптимизировать:
Число p – простое тогда и только тогда, когда для каждого натурального числа a из диапазона от 2 до (p-1)/2 будет справедливо сравнение (1).
Теперь приведем примеры применения данной теоремы для тестирования чисел на простоту.
Доказательство того, что число p=11 является простым числом. Для этого в уравнение (4) в качестве основания a последовательно подставим все натуральные числа диапазона от 2 до (p-1)/2=(11-1)/2=5 и вычислим значения y всех возможных остатков. Тогда основание a и остаток y будут соответственно иметь следующие значения: 2 и 1; 3 и 1; 4 и 1; 5 и 1. Так как для всех натуральных чисел a из диапазона от 2 до (p-1)/2 остаток y оказался равным единице, то есть было справедливо сравнение (1), то простоту числа 11 можно считать доказанной.
Очевидно, что малая теорема Ферма в рассматриваемой формулировке достоверно обеспечивает доказательство составности тестируемого составного числа.
Доказательство того, что псевдопростое число Кармайкла p=1729=7·13·19 является составным числом. Для этого в уравнение (4) в качестве основания a последовательно подставим все натуральные числа диапазона от 2 до (p-1)/2=(1729-1)/2=864 и вычислим значения y всех возможных остатков. Тогда основание a и остаток y будут соответственно иметь следующие значения: 2 и 1; 3 и 1; 4 и 1; 5 и 1; 6 и 1; 7 и 742.
Так как при a=7 остаток y оказался равен 742, а не единице, то есть сравнение (1) не выполняется, то число 1729 никак не может быть простым. А значит, оно составное.
Дальнейшее сокращение количества значений числа a при установлении факта простоты числа p с помощью малой теоремы Ферма следует из приведенных в статье [1] формул для вычисления всех членов последовательности натуральных чисел, в которой все составные числа заменены нулями [4]. В частности из этих формул следует, что для установления факта простоты числа p достаточно в качестве числа a последовательно использовать все простые числа из диапазона от 2 до [p0,5].
Более того, как это было показано в статье [1], в качестве числа a можно использовать всего одно строго определенное число равное произведению всех простых чисел из диапазона от 2 до [p0,5].
Разумеется, наложение отмеченных ограничений на выбор числа a, потребует внесения изменений в формулировку малой теоремы Ферма:
Если натуральное число a= p1·p2·…·pn, где pn простые числа, следующие строго в порядке их возрастания начиная с p1 = 2, то любое натуральное число p из диапазона от pn до pn2 будет простым тогда и только тогда, когда будет справедливо сравнение (1).
Далее приведен пример применения малой теоремы Ферма в данной формулировке для тестирования чисел на простоту.
Если a=2·3·5·7=210, то малая теорема Ферма в рассматриваемой формулировке позволит точно установить факт простоты либо составности всех чисел от 7 до 72=49. Для чего по формуле (4) необходимо вычислить значения остатков y для каждого числа p из указанного диапазона чисел.
p=8 y=2107- 8·[2107/8]=0 p=29 y=21028- 29·[21028/29]=1
p=9 y=2108- 9·[2108/9]=0 p=30 y=21029- 30·[21029/30]=0
p=10 y=2109- 10·[2109/10]=0 p=31 y=21030- 31·[21030/31]=1
p=11 y=21010- 11·[21010/11]=1 p=32 y=21031- 32·[21031/32]=0
p=12 y=21011- 12·[21011/12]=0 p=33 y=21032- 33·[21032/33]=12
p=13 y=21012- 13·[21012/13]=1 p=34 y=21033- 34·[21033/34]=6
p=14 y=21013- 14·[21013/14]=0 p=35 y=21034- 35·[21034/35]=0
p=15 y=21014- 15·[21014/15]=0 p=36 y=21035- 36·[21035/36]=0
p=16 y=21015- 16·[21015/16]=0 p=37 y=21036- 37·[21036/37]=1
p=17 y=21016- 17·[21016/17]=1 p=38 y=21037- 38·[21037/38]=20
p=18 y=21017- 18·[21017/18]=0 p=39 y=21038- 39·[21038/39]=30
p=19 y=21018- 19·[21018/19]=1 p=40 y=21039- 40·[21039/40]=0
p=20 y=21019- 20·[21019/20]=0 p=41 y=21040- 41·[21040/41]=1
p=21 y=21020- 21·[21020/21]=0 p=42 y=21041- 42·[21041/42]=0
p=22 y=21021- 22·[21021/22]=12 p=43 y=21042- 43·[21042/43]=1
p=23 y=21022- 23·[21022/23]=1 p=44 y=21043- 44·[21043/44]=12
p=24 y=21023- 24·[21023/24]=0 p=45 y=21044- 45·[21044/45]=0
p=25 y=21024- 25·[21024/25]=0 p=46 y=21045- 46·[21045/46]=26
p=26 y=21025- 26·[21025/26]=2 p=47 y=21046- 47·[21046/47]=1
p=27 y=21026- 27·[21026/27]=0 p=48 y=21047- 48·[21047/48]=0
p=28 y=21027- 28·[21027/28]=0
В приведенном примере все числа p для которых вычисленные значения остатков y равны единице в соответствии с малой теоремой Ферма будут простыми. Причем они не вероятно, а точно будут простыми. Причины, по которым среди них не может быть псевдопростых чисел, были рассмотрены в статье [1].
В целях сокращения вычислительных операций можно немного изменить вариант рассматриваемой формулировки малой теоремы Ферма:
Если натуральное число a= p1·p2·…·pn-1, где pn простые числа, следующие строго в порядке их возрастания начиная с p1 = 2, то любое натуральное число p из диапазона от pn до pn2 будет простым тогда и только тогда, когда будет справедливо сравнение (1).
Используя малую теорему Ферма в этой формулировке, приведенный выше пример, можно изложить в более компактном виде.
Если a=2·3·5=30 и известно, что следующее после 5 простое число равно 7, то малая теорема Ферма в рассматриваемой формулировке позволит точно установить факт простоты либо составности всех чисел от 7 до 72=49. Для чего по формуле (4) необходимо вычислить значения остатков y для каждого числа p из указанного диапазона чисел.
p=8 y=307- 8·[307/8]=0 p=29 y=3028- 29·[3028/29]=1
p=9 y=308- 9·[308/9]=0 p=30 y=3029- 30·[3029/30]=0
p=10 y=309- 10·[309/10]=0 p=31 y=3030- 31·[3030/31]=1
p=11 y=3010- 11·[3010/11]=1 p=32 y=3031- 32·[3031/32]=0
p=12 y=3011- 12·[3011/12]=0 p=33 y=3032- 33·[3032/33]=9
p=13 y=3012- 13·[3012/13]=1 p=34 y=3033- 34·[3033/34]=30
p=14 y=3013- 14·[3013/14]=2 p=35 y=3034- 35·[3034/35]=30
p=15 y=3014- 15·[3014/15]=0 p=36 y=3035- 36·[3035/36]=0
p=16 y=3015- 16·[3015/16]=0 p=37 y=3036- 37·[3036/37]=1
p=17 y=3016- 17·[3016/17]=1 p=38 y=3037- 38·[3037/38]=30
p=18 y=3017- 18·[3017/18]=0 p=39 y=3038- 39·[3038/39]=3
p=19 y=3018- 19·[3018/19]=1 p=40 y=3039- 40·[3039/40]=0
p=20 y=3019- 20·[3019/20]=0 p=41 y=3040- 41·[3040/41]=1
p=21 y=3020- 21·[3020/21]=18 p=42 y=3041- 42·[3041/42]=18
p=22 y=3021- 22·[3021/22]=8 p=43 y=3042- 43·[3042/43]=1
p=23 y=3022- 23·[3022/23]=1 p=44 y=3043- 44·[3043/44]=28
p=24 y=3023- 24·[3023/24]=0 p=45 y=3044- 45·[3044/45]=0
p=25 y=3024- 25·[3024/25]=0 p=46 y=3045- 46·[3045/46]=30
p=26 y=3025- 26·[3025/26]=4 p=47 y=3046- 47·[3046/47]=1
p=27 y=3026- 27·[3026/27]=0 p=48 y=3047- 48·[3047/48]=0
p=28 y=3027- 28·[3027/28]=8
Как видно из представленного примера сокращение вычислительных операций никак не повлияло на вычисление простых чисел и лишь привело к изменению величин остатков y для составных чисел p. Причем это изменение величин остатков было количественным, но не качественным.
Приведенные примеры содержат тестирование на простоту всех чисел p из диапазона от pn до pn2, однако здесь рассматривается использование малой теоремы Ферма в качестве универсального и истинного теста простоты и соответственно в этом случае тестированию потребуется подвергать лишь отдельные числа p. Поэтому необходимо рассмотреть вопрос о величине диапазона чисел при котором малая теорема Ферма будет сохранять свойства универсального и детерминированного теста простоты.
Очевидно, что с ростом pn будет увеличиваться и этот диапазон, а так как ряд простых чисел бесконечен, то и диапазон чисел, для которых можно будет устанавливать факт их простоты при помощи малой теоремы ферма, тоже будет увеличиваться до бесконечности. Например:
Если pn=7, то диапазон будет от 7 до pn2=49, в котором будет 49-7=42 числа.
Если pn=101, то диапазон будет от 101 до pn2=10201, в котором будет 10201-101=10100 чисел.
Если pn=3511, то диапазон будет от 3511 до pn2= 12327121, в котором будет 12327121-3511=12323610 чисел.
Если pn= 2147483647, то диапазон будет от 2147483647 до pn2=4611686014132420609, в котором будет 4611686014132420609-2147483647=4611686011984936962 числа. И так далее, действительно, можно продолжать до бесконечности.
Конечно, число a с увеличением pn тоже очень быстро растет, но необходимо учитывать, что число a потребуется вычислить всего один раз и, следовательно, на его формирование можно будет потратить сравнительно много времени в плоть до нескольких лет, а то и вовсе увеличивать постоянно. Важно чтобы это время не оказалось неприемлемо большим.
Для оценки затрат времени можно посмотреть достигнутые результаты в деле вычисления значений всех простых чисел подряд. Так по состоянию на 2013 год в рамках проекта по проверке гипотезы Гольдбаха за приемлемое время были вычислены все простые числа меньшие 4·1018. Это составляет 95676260903887607 простых чисел.
В настоящее время обычно рекомендуемая минимальная длина криптографического ключа составляет 1024 бита (309 десятичных знаков) или 2048 бит (617 десятичных знаков). Из этого следует, что для того чтобы к числам, имеющим указанную длину, применять малую теорему Ферма в качестве детерминированного и универсального теста простоты необходимо минимально вычислить все простые числа примерно меньшие, чем 10155 или 10309. Показатели степеней этих чисел от показателя степени 18, уже практически достигнутого числа, отличаются только примерно в 10 раз. С момента вычисления всех простых чисел меньших 4·1018 прошло около десяти лет и в настоящее время вычислительная техника обладает большими возможностями. Кроме этого, чем больше становятся простые числа, тем реже они встречаются в последовательности натуральных чисел. Поэтому задача вычисления всех простых чисел вплоть до рассматриваемой длины является практически достижимой.
Существует еще одна проблема, заключающаяся в том, что число a, равное произведению большого количества простых чисел, скорее, всего, окажется непригодным к практическому использованию из-за неприемлемо большой длины. Но эту проблему можно решить за счет разделения числа a на несколько частей. Для этого необходимо составить выражение (18).
x = (a1р-1-р·[a1р-1/р])·(a2р-1-р·[a2р-1/р])·…·(arр-1-р·[arр-1/р]), (18)
где a1 = p1·p2·p3·p4·p5·p6, a2 = p7·p8·p9·p10·p11, ar = pn-4·pn-3·pn-2·pn-1, где pn простые числа, следующие строго в порядке их возрастания без повторов начиная с p1 = 2, то есть каждое простое число pn используется только один раз. Количество чисел pn в произведении для каждого числа аr выбирается исходя из возможностей используемой вычислительной техники и величины простых чисел pn, то есть с ростом простых чисел pn их количество в произведении для каждого числа аr необходимо будет уменьшать.
Очевидно, что любое натуральное число p из диапазона от pn до pn2 будет простым тогда и только тогда, когда x, вычисленное по формуле (18), будет равно единице. В противном случае число p будет точно составным.
Теперь можно рассмотреть примеры использования выражения (18).
Если взять простое число p=563, то для него pn=[5630,5]=23. И число a=2·3·5·7·11·13·17·19·23=223092870. Теперь разделим число a на два меньших числа: a1=2·3·5·7·11·13=30030 и a2=17·19·23=7429. И вычислим значение x по формуле (18):
x=(30030562-563·[30030562/563])·(7429562-563·[7429562/563])=1
Поскольку x равно единице, то простота числа 563 была точно подтверждена.
Если взять псевдопростое число Кармайкла p=561=3·11·17, то для него pn=[5610,5]=23. И число a=2·3·5·7·11·13·17·19·23=223092870. Теперь разделим число a на два меньших числа: a1=2·3·5·7·11·13=30030 и a2=17·19·23=7429. И вычислим значение x по формуле (18):
x=(30030560-561·[30030560/561])·(7429560-561·[7429560/561])=17952
Поскольку x не равно единице, то число 561 точно является составным.
Если проверяемое на простоту число p выходит за пределы диапазона от pn до pn2, то малая теорема Ферма позволит утверждать о его простоте опять лишь с некоторой вероятностью. Но эта вероятность будет значительно большей, чем при традиционном выборе основания a, что очевидным образом следует из факта, что любое число Кармайкла содержит как минимум три простых множителя.
Факт точного доказательства или опровержения, с помощью малой теоремы Ферма, простоты числа сравнительно легко устанавливается. Тем не менее, во всех учебниках и справочниках по математике тест простоты Ферма неизменно указывается в качестве вероятностного теста.
С одной стороны, столь упорное, представление теста простоты Ферма лишь в качестве вероятностного теста вызывает удивление, а с другой стороны позволяет предположить умышленное сокрытие части информации особенно, если учитывать использование малой теоремы Ферма при разработке и применении различных криптографических систем.
Конечно, как часто в подобных обстоятельствах и происходит, можно заявить, что это всё известно. Однако поскольку практическое применение теста простоты Ферма имеет значение только в качестве вероятностного теста, а его применение в качестве истинного теста приведет к необходимости выполнения недопустимо большого объема вычислений, то его, как бы по некой договорённости, принято считать только вероятностным тестом.
И с таким объяснением отнесения теста простоты Ферма к вероятностным тестам можно было бы согласиться, если бы не существование иных тестов простоты по своим свойствам близких к тесту простоты Ферма, но, тем не менее, считающихся истинными тестами простоты.
Например, метод пробных делений предлагается использовать для проверки на простоту только относительно небольших чисел [5], а в случае генерации больших простых чисел его уже прямо используют лишь в качестве предварительного вероятностного теста простоты путем деления проверяемого числа лишь на малые простые числа [6]. То есть применение метода пробных делений, как и малой теоремы Ферма, имеет значение только в качестве вероятностного теста, а его применение в качестве истинного теста приведет к необходимости выполнения недопустимо большого объема вычислений. Но это почему-то в отличие от малой теоремы Ферма не мешает его во всех учебниках указывать в качестве истинного теста простоты.
Однако объяснить, почему так происходит довольно просто.
Простое число определяют как натуральное число, если оно отлично от единицы и делится без остатка только на единицу и на само себя. Натуральное число называется составным, если оно превосходит единицу и не является простым [5]. Таким образом, простые числа отличаются от составных чисел при помощи всего одного отличительного признака. И этот отличительный признак может быть полностью проверен или нет. Причем в ходе применения любого теста простоты. В связи с этим объективного способа отнесения того или иного теста простоты к вероятностным тестам не существует. Действительно любой тест простоты можно по тем или иным причинам выполнять лишь частично и на этом основании объявить его вероятностным. Поэтому все вероятностные тесты простоты следует считать лишь условно вероятностными.
По всей видимости, и малую теорему Ферма объявили вероятностным тестом простоты потому, что кто-то когда-то на основании каких-то соображений решил, что основания a для выражения (1) следует выбирать случайным образом, который не обеспечивает получение детерминированного результата, а не так, как предлагается, например, в данной статье с обеспечением получения детерминированного результата.
Вообще, если исходить из определения простого числа, то задача любого универсального детерминированного теста простоты заключается в установлении факта наличия или отсутствия у проверяемого числа делителей строго определенного вида. Очевидно, что тест простоты будет тем лучше, чем меньше вычислительных операций для решения этой задачи необходимо будет выполнить. И тест простоты, основанный на малой теореме Ферма, в этом отношении никак не может являться самым эффективным, так как предполагает вычисление больших степеней больших чисел.
Поэтому малую теорему Ферма желательно модифицировать таким образом, чтобы можно было отказаться от вычисления степеней. Что это принципиально возможно было показано в статье [1]. При этом выражение (4) для вычисления значений остатков y для малой теоремы Ферма можно будет уже записать в виде выражения (19).
y = a-р·[a/р], (19)
где a= p1·p2·…·pn-1, где pn простые числа, следующие строго в порядке их возрастания начиная с p1 = 2, p - натуральное число из диапазона от pn до pn2.
Выражение (19) фактически представляет собой цикл алгоритма Евклида для нахождения наибольшего общего делителя двух натуральных чисел [5]. И это не случайно, так как малая теорема Ферма в определенном смысле является частным случаем алгоритма Евклида для нахождения наибольшего общего делителя. В частности для простого числа p и числа aр-1 алгоритм Евклида всегда за один цикл будет находить наибольший общий делитель равный единице. Если алгоритм Евклида для нахождения наибольшего общего делителя использовать в качестве теста простоты, то результаты его применения будут совпадать с результатами тестирования при помощи малой теоремы Ферма.
Действительно если p – простое число и а – целое число, не делящееся на p, то наибольший общий делитель НОД (а, p)=1. Для теста простоты на основе алгоритма Евклида также существуют псевдопростые числа. Потому что если p – составное число и а и p взаимно простые числа, то НОД (а, p)=1. Тут можно сказать и иначе, а именно, что это обстоятельство является основной причиной появления псевдопростых чисел при применении малой теоремы Ферма. То есть если числа а при использовании алгоритма Евклида в качестве теста простоты выбирать так же, как и традиционно, для теста Ферма, случайным образом, то такой тест тоже будет лишь вероятностным. Но если число а будет вычисляться так как это предлагается делать в настоящей статье, то тест простоты на основе алгоритма Евклида для нахождения наибольшего общего делителя будет детерминированным и универсальным.
На основании выше изложенного для простых чисел можно сформулировать следующую теорему.
Теорема 1. Если натуральное число a= p1·p2·…·pn-1, где pn простые числа, следующие строго в порядке их возрастания начиная с p1 = 2, то любое натуральное число p из диапазона от pn до pn2 будет простым тогда и только тогда, когда НОД (а, p)=1.
Теорема 1 представляет собой детерминированный и универсальный тест простоты. Её применение будет более эффективно по сравнению с малой теоремой Ферма, так как она непосредственно в ходе тестирования позволяет вычислить нетривиальный делитель проверяемого числа, если он, конечно, есть, и используемые в ней алгоритмы нахождения наибольшего общего делителя являются самыми быстрыми из всех известных.
Вычисление НОД (а, p) на основе алгоритма Евклида и выражения (19) происходит следующим образом. Начиная с n=2, по рекуррентной формуле (20) последовательно вычисляются значения остатков zn.
z0 = a, z1 = р, zn = zn-2 - zn-1·[zn-2/zn-1], (20)
При zn = 0 НОД (а, p) = zn-1 и вычисления останавливаются.
Проблемы, связанные с вычислением числа а, были рассмотрены выше при рассмотрении его использования в выражении (1) малой теоремы Ферма. В том числе было предложено решать проблему ожидаемой неприемлемо большой длины числа а за счет разделения его на несколько частей. Точно также можно поступать и при тестировании на простоту больших чисел при помощи Теоремы 1. При этом НОД (а, p) будет вычисляться как произведение по формуле (21).
НОД (а, p) = НОД (а1, p)·НОД (а2, p)·...·НОД (аr, p), (21)
где а= а1·а2·…·аr, где а1= p1·p2·p3·p4·p5·p6, а2= p7·p8·p9·p10·p11, аr= pn-4·pn-3·pn-2·pn-1, где pn простые числа, следующие строго в порядке их возрастания без повторов начиная с p1 = 2, то есть каждое простое число pn используется только один раз. Количество чисел pn в произведении для каждого числа аr выбирается исходя из возможностей используемой вычислительной техники и величины простых чисел pn, то есть с ростом простых чисел pn их количество в произведении для каждого числа аr необходимо будет уменьшать.
Вычисление НОД (аr, p) может осуществляться как при помощи формулы (20), так и с помощью любой модификации алгоритма Евклида. Так же на применении Теоремы 1 никак не отразится использование формулы (21) при вычислении НОД (а, p).
Теперь можно рассмотреть примеры использования Теоремы 1.
Перед началом использования Теоремы 1 необходимо сформировать число а. Это можно, например, сделать, используя, следующие пять чисел, которые являются частями числа а.
а1=2·3·5·7·11·13·17·19·23·29=6469693230
а2=31·37·41·43·47·53=5037203051
а3=59·61·67·71·73=1249792339
а4=79·83·89·97·101=5717264681
а5=103·107·109·113·127=17239698439
Число а вычисляется как произведение чисел а1,… а5.
а= а1·а2·а3·а4·а5=40729680599249024150621323470 · 17239698439
Здесь число а пришлось, представит в виде произведения двух чисел, так как для используемого при вычислениях, встроенного в Windows, калькулятора оно оказалось слишком длинным. Однако, применив формулу (21) можно будет и дальше выполнить все вычисления на данном калькуляторе. И вообще при совершении практических вычислений нет необходимости вычислять полностью число а. Достаточно вычислить по отдельности чисела а1,… а5.
При условии использования сформированного числа а. Диапазон чисел, при котором Теорема 1 будет сохранять свойства универсального и детерминированного теста простоты, определяется исходя из того, что наибольший простой сомножитель в числе а5 равен 127, а следующее после 127 простое число равно 131. И составляет от 131 до 1312=17161.
Таким образом числа а1,… а5 и число а больше вычислять не потребуется для проверки на простоту или вычисления нетривиального делителя любого числа из диапазона от 131 до 17161.
Подтвердим с помощью Теоремы 1 простоту числа p=17159, которое принадлежит диапазону чисел от 131 до 17161.
Для этого последовательно, для каждого числа а1,… а5, вычислим НОД (аr, p) с использованием формулы (20):
z0=6469693230, z1=17159,
z2=6469693230-17159·[6469693230/17159]=12393, …
z11=4-3·[4/3]=1, z12=3-1·[3/1]=0
НОД (а1, p) = НОД (6469693230, 17159)=1
z0=5037203051, z1=17159,
z2=5037203051-17159·[5037203051/17159]=7011, …
z9=19-18·[19/18]=1, z10=18-1·[18/1]=0
НОД (а2, p) = НОД (5037203051, 17159)=1
z0=1249792339, z1=17159,
z2=1249792339-17159·[1249792339/17159]=16574, …
z7=3-2·[3/2]=1, z8=2-1·[2/1]=0
НОД (а3, p) = НОД (1249792339, 17159)=1
z0=5717264681, z1=17159,
z2=5717264681-17159·[5717264681/17159]=5994, …
z11=4-3·[4/3]=1, z12=3-1·[3/1]=0
НОД (а4, p) = НОД (5717264681, 17159)=1
z0=17239698439, z1=17159,
z2=17239698439-17159·[17239698439/17159]=16821, …
z10=9-4·[9/4]=1, z11=4-1·[4/1]=0
НОД (а5, p) = НОД (17239698439, 17159)=1
НОД (а, p) = НОД (а1, p) · НОД (а2, p) · НОД (а3, p) · НОД (а4, p) · НОД (а5, p) = 1·1·1·1·1=1
Поскольку НОД (а, p) = 1, то в соответствии с Теоремой 1 число p = 17159 точно является простым.
Теперь рассмотрим пример доказательства с помощью Теоремы 1 составности псевдопростого числа Кармайкла p = 15841 = 7·31·73, которое принадлежит диапазону чисел от 131 до 17161, с одновременным вычислением его нетривиальных делителей.
Для этого последовательно, для каждого числа а1,… а5, вычислим НОД (аr, p) с использованием формулы (20):
z0=6469693230, z1=15841,
z2=6469693230-15841·[6469693230/15841]=7056, …
z7=49-42·[49/42]=7, z8=42-7·[42/7]=0
НОД (а1, p) = НОД (6469693230, 15841)= 7
Таким образом, был вычислен один из нетривиальных делителей числа 15841, который равен 7.
Поскольку НОД (а1, p) =7 > 1 и следовательно НОД (а, p) тоже будет больше единицы, то в соответствии с Теоремой 1 составность числа 15841 можно считать доказанной. И дальнейшее его тестирование на простоту можно было бы остановить. Однако одновременно предполагалось вычислить нетривиальные делители числа 15841. Поэтому продолжим вычисления.
z0=5037203051, z1=15841,
z2=5037203051-15841·[5037203051/15841]=2666, …
z5=2511-155·[2511/155]=31, z6=155-31·[155/31]=0
НОД (а2, p) = НОД (5037203051, 15841)=31
Таким образом, был вычислен один из нетривиальных делителей числа 15841, который равен 31.
z0=1249792339, z1=15841,
z2=1249792339-15841·[1249792339/15841]=803, …
z6=219-146·[219/146]=73, z7=146-73·[146/73]=0
НОД (а3, p) = НОД (1249792339, 15841)=73
Таким образом, был вычислен один из нетривиальных делителей числа 15841, который равен 73.
z0=5717264681, z1=15841,
z2=5717264681-15841·[5717264681/15841]=10166, …
z11=41-40·[41/40]=1, z12=40-1·[40/1]=0
НОД (а4, p)= НОД (5717264681, 15841)=1
z0=17239698439, z1=15841,
z2=17239698439-15841·[17239698439/15841]=1503, …
z10=9-4·[9/4]=1, z11=4-1·[4/1]=0
НОД (а5, p) = НОД (17239698439, 15841)=1
НОД (а, p) = НОД (а1, p) · НОД (а2, p) · НОД (а3, p) · НОД (а4, p) · НОД (а5, p) = 7·31·73·1·1=15841
Необходимо отметить, что при вычислении делителей тестируемого числа не всегда сразу будут находиться все простые делители. Поэтому потребуется применять известные методы: проверку найденных делителей на простоту, уменьшение тестируемого числа путем его деления на найденный делитель и тестирование на простоту полученного результата и тому подобных методов.
Из приведенной в данной статье и статье [1] информации следует, что, используя только Теорему 1, можно создать наиболее эффективные детерминированный универсальный тест простоты, алгоритм факторизации натуральных чисел и эффективно вычислимую формулу для простых чисел, способную генерировать все простые числа подряд в порядке их возрастания. Причем тест простоты и алгоритм факторизации могут выполняться параллельно в рамках одной процедуры точно так же, как, например, в методе пробных делений.
Числа аr должны вычисляться заранее только один раз по формуле для простых чисел [1], которая обеспечивает выполнение этой процедуры на постоянной основе. При этом даже если на вычисление чисел аr придется затратить несколько лет, это в дальнейшем никак не отразится на скорости выполнения тестирования на простоту и факторизацию чисел.
Кроме этого числа аr следует формировать с максимально возможной длиной, так как какое бы длинное ни было число аr после выполнения первого же цикла алгоритма Евклида все последующие циклы этого алгоритма уже будут выполняться с числами, длина которых не будет превышать длину тестируемого числа. Имеются и быстрые алгоритмы для работы с очень большими числами [5]. Так же чем большее число простых сомножителей будет содержать число аr тем меньшее число раз придется считывать тестируемое число.
В настоящее время разработано уже много алгоритмов факторизации длинных чисел [5], но все они мало пригодны для практического разложения больших чисел на простые множители в целях выполнения дешифровки, так как требуют для каждого числа использования значительных вычислительных мощностей и затрат времени.
При разложении же на простые множители больших натуральных чисел при помощи Теоремы 1 этих проблем можно избежать за счет того, что числа аr вычисляются заранее и только один раз, а в ходе факторизации конкретного числа все вычисления можно выполнять параллельно для каждого числа аr на отдельном процессоре. Разумеется, для организации такой схемы вычислений потребуется создать узко специализированное вычислительное устройство, которое будет постоянно вычислять по формуле для простых чисел [1] числа аr и заносить их в память самостоятельных процессоров. Эти же процессоры в свою очередь должны будут обеспечивать реализацию алгоритма Евклида для тестируемого числа и числа аr с передачей результатов своего вычисления на центральный процессор для выполнения их окончательного анализа.
Вообще то создание специализированного вычислительного устройства не является обязательным, так как параллельные вычисления можно организовать на большом количестве компьютеров объединенных в единую сеть. В этом случае вычислительные мощности таких компьютеров могут быть использованы как легально, так и тайно, например, путем заражения их соответствующими вирусными программами.
Таким образом, затратив один раз относительно большое время на формирование массива чисел аr и создание специализированного вычислительного устройства можно будет за разумное время дешифровать и прочесть все перехваченные сообщения зашифрованные с помощью криптографических алгоритмов основанных на предположении того, что задача факторизации больших чисел является вычислительно сложной. При этом работы по формированию массива чисел аr и созданию специализированного вычислительного устройства являются рутинными и не требуют разработки принципиально новых устройств, алгоритмов и программ.
Ожидается, что в будущем проблему разложения на простые множители больших чисел удастся решить за счет применения квантового алгоритма факторизации Шора [5], который будет способен на квантовом компьютере произвести факторизацию числа почти так же быстро, как происходит само шифрование. Однако для этого сначала необходимо создать, способный устойчиво работать, квантовый компьютер предположительно, как минимум, с несколькими тысячами логических кубитов. Эта задача не является тривиальной и не может быть тайно решена частными лицами или небольшими организациями. Так по разным оценкам на ее решение потребуется от 10-20 лет до, что она вообще не будет решена в обозримом будущем.
По этим причинам не следует просто ждать создания квантового компьютера с необходимыми характеристиками. Целесообразно проверить практическую возможность формирования массива чисел аr и создания специализированного вычислительного устройства, реализующего алгоритм факторизации натуральных чисел в соответствии с Теоремой 1. Ведь если такая возможность существует, то это означает реальную возможность взлома криптографических систем с открытым ключом и соответственно большей части современной криптографической защиты за приемлемые время и деньги. Причем в самом худшем случае такой взлом могут уже очень давно и тайно осуществлять частные лица и небольшие организации.
Октябрь 2022 года.
Литература:
1. А.М. Белов. Задание числовых рядов и последовательностей с простыми числами и формулы простых чисел [Электронный ресурс]. - Интернет адрес: http://stob2.narod.ru/40s.htm, 2022.
2. А. Белов. Великая мистификация Ферма. LAP LAMBERT Academic Publishing, 2017. – 100 с. - ISBN 978-3-659-79304-2.
3. А.М. Белов. Периодические импульсные функции на основе универсального уравнения [Электронный ресурс]. - Интернет адрес: http://stob2.narod.ru/16s.htm, 2005.
4. А.М. Белов. Теория чисел: простые числа и универсальное уравнение [Электронный ресурс]. - Интернет адрес: http://stob2.narod.ru/2s.htm, 2003.
5. Р. Крэндалл, К. Померанс. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. В.Н.
Чубарикова. – М.: УРСС: Книжный дом «ЛИБРОКОМ», 2011. – 664 с. - ISBN 978-5-453-00016-6, ISBN 978-5-397-02060-2.
6. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов.– Казань: Казан. ун. 2011.– 190 с.