Статья опубликована в №54 (февраль) 2018
Разделы: Математика
Размещена 22.02.2018. Последняя правка: 04.10.2018.
Просмотров - 3794

Алгоритм решета простых чисел

Соловьёв Виктор Григорьевич

ООО "Бизнескоп Консалтинг"

Математик-программист

УДК 511

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

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

Введение. Для поиска простых чисел, меньших некоторого заданного предела, математики используют, так называемый, метод решета простых чисел, суть которого состоит в вычеркивании (фильтрации) из натурального ряда составных чисел. Самым древним из всех методов считается Решето Эратосфена, который последовательно отфильтровывает все составные числа, кратные определенным простым на предыдущих этапах. Для реализации Решета Эратосфена разработаны различные алгоритмы, в частности, линейный [1]. Для оценки алгоритмов используют понятие вычислительной сложности, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Решето Эратосфена имеет вычислительную сложность , оцениваемую функцией  O(nlog(logn)). Следует также выделить среди наиболее известных алгоритмов Решето Сундарама [2], оцениваемого по функции вычислительной сложности O(nlogn), и многочисленные  модификации Решета Эратосфена, например [3], а также другие современные методы, так или иначе, основанные на построении решета простых чисел, например, методом исключений [4]. Однако они по вычислительной сложности принципиально не превосходят Решета Эратосфена. В настоящее время одним из самых быстрых алгоритмов определения простых чисел из массива чисел натурального ряда является Решето Аткина-Бернштайна [5] с вычислительной сложностью O(n). Основная идея алгоритма Решета Аткина-Бернштайна состоит в определении сравнения чисел по модулю 60 и в использовании неприводимых квадратичных форм, т.е. представлении чисел в виде ax²+by² в соответствии с теоремами Эйлера и Ферма. Основными недостатками Решета Аткина-Бернштайна является то, что использование рядов чисел по классу вычетов модулю 60 не позволяет использовать квадратичные формы с другими коэффициентами, нежели a=3 или a=4, а b=1 или b=-1, что практически и приводит к составлению для поиска решений квадратных уравнений достаточно громоздких матричных таблиц.

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

Теоретическое обоснование. В десятичной системе исчисления натуральное число P записывается в виде
 

где

 r - цифра соответствующего разряда числа,

а также записывается в виде краткой формы записи




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

- по цифре единичного разряда r₀ (последней цифре числа или по правому символу числа), которая не может быть четной и равной 0, 2,  4,  6,  8, иначе бы число по известному признаку делимости имело бы делитель равный 2,  а также нечетной равной 5, иначе число по известному признаку делимости имело бы делитель равный 5, следовательно

- по  сумме цифр r_i  всех разрядов числа

которая не может делиться на 3, 6, 9 по известным признакам делимости, иначе число имело бы соответствующие делители, из чего следует, что цифровой корень s₀ числа [6], который является последовательным суммированием цифр всех разрядов числа пока не останется одной цифры, например,



не может принимать значения, кратные 3, т.е.

Заметим, что цифровой корень s₀ простого числа может быть равен исключительно цифрам периода 1/7 = 0.142857 142857…

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

Теорема 1. Остаток R от деления числа P на 90 равен числу умноженной на десять разности цифрового корня и цифры единичного разряда числа плюс цифра единичного разряда. Для доказательства, запишем первое из выше указанных свойств в виде

а второе из выше указанных свойств в виде

Увеличив обе части первого уравнения в 9, а второго - в 10 раз, получим два уравнения

Вычитая из первого уравнения второе, получим

или

где 

 что и требовалось доказать. Можно заключить, что остаток R состоит из числа десятков 


и цифры r₀ единичного разряда. Следует заметить, если  s₀  <  r₀ , то


Следовательно, кандидаты в простые числа из ряда натуральных чисел разделяются на 24 типа по модулю сравнения 90 или, так называемым, классам вычетов [8], которые определяются всеми возможными сочетаниями цифрового корня  и последнего знака числа.

Для примера, вычислим один из типов числового ряда, содержащего простые числа:

пусть r₀ = 1, а s₀ = 8,  тогда R = (8 - 1) * 10 +1 = 71

 В результате определен один из типов простого числа в виде класса  вычетов по модулю 90:


где k - неполное частное.

Все типы чисел в виде рядов по модулю 90, в которых содержатся простые числа (выделены жирным шрифтом), в сочетании s₀ и r₀ распределены в таблице 1 по строкам в столбцах 2 и 3 соответственно. В столбце 4 представлены остатки  R при делении числа-кандидата на 90 для чисел меньших 1100. В столбцах 5 - 15 расположены по строкам 1 - 48 все типы исследуемых числовых рядов. Причем их число увеличено вдвое только для того, чтобы в дальнейшем (см. ниже) наглядно показать  отличия рассматриваемого метода от предшествующих, в частности, метода Аткина-Бернштайна. Следует отметить, что для каждого из 24 сочетаний  s₀ и r₀ в таблице 1 представлены ряды, распределенные по двум строкам в зависимости от четного или нечетного неполного частного k. Этот факт также влияет на дальнейшие теоретические рассуждения, для чего докажем еще одну теорему о быстром способе определения четности неполного частного k.

Теорема 2. Неполное частное k от деления числа на 90 является четным, если разность цифры r₁ десятичного разряда числа и числа десятков d₀ остатка R четна, и, наоборот, неполное частное k от деления числа на 90 является нечетным, если разность цифры  r₁ десятичного разряда числа и числа десятков   d₀ остатка R нечетна. Для доказательства запишем уравнение в виде

 

сократив в обеих частях уравнения r₀ , и поделив обе части на 10 имеем

 

Откуда следует, что разность r₁ - d₀ четна только в том случае, когда  9k четно и, следовательно, k четно, а в противном случае k нечетно, что и требовалось доказать.

Таким образом, построено решето чисел-кандидатов в простые на основе элементарных начальных вычислений трех параметров s₀,  r₀ и r₁ - d₀, которые создают основу для дальнейшего отсеивания не простых чисел.

Квадратичные формы. Следующий шаг отсеивания не простых чисел или распознавания простых чисел основан на использовании, так называемых, квадратичных форм. Основная идея алгоритма, разработанная еще Эйлером и Ферма [7], состоит в поиске параметров представления чисел P в виде  уравнения 



Число P = n является простым тогда и только тогда, когда количество решений указанного выше уравнения нечётно и само число не кратно никакому квадрату простого числа. Наилучший на сегодняшний день алгоритм Аткина-Бернштайна использует три квадратичных формы (первого, второго и третьего родов) для поиска простых чисел сравниваемых по модулю 60, а именно:




Все формы для 24 рассматриваемых новых типов чисел представлены в таблице 1 в столбце 15. Собственно говоря, поиск решения указанных уравнений и является наиболее трудоёмкой задачей в части количества вычислительных операций, а, следовательно, временных затрат. Непосредственно решение очень просто описывается алгоритмически и состоит в том, что строят двух координатную сетку по осям, на пересечении которых  вычисляют числа квадратных уравнений. Несложно убедиться в том, что размер сетки равен

Решето Аткина-Бернштайна оперирует с тремя размерами сетки:



Использование для поиска простых чисел сравнений по модулю 90 с четными и нечетными неполными частными позволило рассматривать сетки квадратичных форм со значительно уменьшенными размерами (или другими словами - увеличенным шагом сетки), что позволило, в конечном счете, для целого ряда чисел значительно уменьшить количество операций при решении квадратичных уравнений. Полученные новые уравнения представлены в столбце 17 таблицы 1. При этом в столбце 18 таблицы 1 показан эффект от применения нового уравнения в части количества операций по сравнению с решетом Аткина-Бернштайна. Например, рассмотрим квадратичную форму, дающую наибольший  двойной или 100%-ный эффект (см. таблицу 1, строки 4,  6, 7, 12, 13 и т.д.). В таблице 2 представлена матрица решений уравнения первого рода, которая применяется в алгоритме Аткина-Бернштайна. Очевидно, что если в указанном уравнении неизвестное y заменить на 2y, то получим новое уравнение квадратичной формы


решения которого представлены в таблице 3. Из сравнения таблиц 2 и 3 видно, что они соответствуют одним и тем же типам рассматриваемых чисел. Найденные единственные  решения в обеих таблицах  соответствуют простым числам, выделенным жирным шрифтом, т.к. их число нечетно и равно 1. Двойные решения, выделенные жирным и подчеркнутым шрифтом, соответствуют не простым числам, т.к.   их число четно и равное 2. В таблицах также отмечено жирным зачеркнутым шрифтом решения, соответствующие составным числам, имеющим один из множителей квадрат простого 847 = 7 * 11². Поскольку таблица 1 имеет размер 29 на 17 для чисел меньших 900, а таблица 3 для тех же чисел имеет вдвое меньший размер 17 на 14, применение новой квадратичной формы существенно сокращает объем вычислений. Следует уточнить, что не для всех рядов чисел подобрана новая квадратичная форма, например,  для рядов в строках 3, 15, 11, 14, 44, 46, 17, 24, 25, 32, 34, 39 таблицы 1 квадратичная форма соответствует форме Аткина-Бернштайна. Для указанных рядов преимущества нового уравнения нет. Но это только одна четверть всех рядов. Для всех остальных 3/4 рядов преимущества в виде объема вычисления квадратичных форм колеблется от 12% до 100%.

О решении квадратичных форм. Для  подбора значений x и y квадратичной формы необходимо и достаточно установить верхний предел равный целому из


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


определив число решений в целых числах, причем корень извлекается только только тогда, когда подкоренное выражение оканчивается на 2, 3, 5, 7 или 8. Очевидно, что количество операций не более

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

Описание алгоритма решета простых чисел. Алгоритм построения решета простых чисел состоит из следующих шагов:

• определяется правый символ r₀ числа и вычеркиваются все числа, которые не оканчиваются на 1, 3, 7, 9
• вычисляется цифровой корень s₀ числа и вычеркиваются все числа,  цифровой корень которых  не равен 1, 4, 2, 8, 5, 7
• вычисляется разность предпоследнего символа числа r₁ и числа d₀= s₀  - r_{0 ,} по которой определяют параметр четности h=0 или нечетности h=1 неполного частного от деления числа на 90 (не выполняя операций вычисления остатка по модулю 90)
• из оставшихся объявляются простыми (остальные вычеркиваются) все числа, которые содержат цифровой корень s₀, правый символ r₀  и параметр четности h равныe соответственно s₀-r₀-h
  • 2-1-0 , 2-9-1, 8-1-0, 8-9-1, 5-1-1, 5-9-0 и нечетным количеством решений уравнения 3x² - y² = n
  • 1-3-0, 1-7-0, 4-3-0, 4-7-1, 7-3-1, 7-7-1 и нечетным количеством решений уравнения  4x² + y² = n
  • 1-1-0, 1-9-1, 4-1-1, 4-9-0, 2-1-1, 2-9-0, 8-1-1, 8-9-0, 5-1-0, 5-9-1, 7-1-0, 7-9-1 и нечетным количеством решений уравнения 5x² + y² = n
  • 1-1-1, 1-3-1, 1-7-1, 1-9-0, 4-1-0, 4-3-1, 4-7-0, 4-9-1, 7-1-1, 7-3-0, 7-7-0, 7-9-0 и нечетным количеством решений уравнения 4x² + 3y² = n
  • 2-3, 2-7, 8-3, 8-7, 5-3, 5-7 (независимо от четности) и нечетным количество решений уравнения 5x² + 3y² = n
• вычеркиваются числа, кратные квадратам простых чисел, начиная с 7.
• все оставшиеся числа составляют решето простых

Пример. Определим простоту одного из  решета чисел Мерсенна [9]


Для этого:

-запишем правый символ r0 = 7

-запишем второй символ справа r1 = 4

- вычислим цифровой корень

-вычислим вычислим параметр четности

-выберем по параметрам s₀-r₀-d₀ = 1-7-1 квадратичную форму

-подсчитаем целый верхний предел по аргументу  квадратичной формы
 

-уменьшая каждый раз x на единицу вычислим аргумент


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

-получим единственное решение в целых числах

- не тратим время на поиск квадратов простых делителей числа P, т.к. числа Мерсенна их не имеют, во всяком случае, согласно известной гипотезе [10]

-делаем вывод, что исследуемое число P Мерсенна  простое!

 

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

Заключение. Предложенный алгоритм поиска простых чисел методом математического решета или фильтрации оценивается по вычислительной сложности как


где a и b суть коэффициенты квадратичной формы определенных типов представлений чисел, что делает его наиболее быстрым среди предшествующих аналогов. В статье представлено теоретическое обоснование алгоритма, приведены основные примеры расчетов.


Приложение

Таблица 1. Распределение простых чисел и их квадратичных форм

Номер столбца	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Номер строки	s0	r0	R	P = R + 90*k											Уравнение Аткина	Новое Уравнение	Уменьшение операций
1	1	1	1		181		361		541		721		901		p=3x2 + y2	p=5x2 + y2	29%
2				91		271		451		631		811		991	p=4x2 + y2	p=4x2 + 3y2	73%
3		3	73		253		433		613		793		973		p=4x2 + y2	p=4x2 + y2	0%
4				163		343		523		703		883		1063	p=3x2 + y2	p=4x2 + 3y2	100%
5		7	37		217		397		577		757		937		p=4x2 + y2	p=4x2 + y2	0%
6				127		307		487		667		847		1027	p=3x2 + y2	p=4x2 + 3y2	100%
7		9	19		199		379		559		739		919		p=3x2 + y2	p=4x2 + 3y2	100%
8				109		289		469		649		829		1009	p=4x2 + y2	p=5x2 + y2	12%
9	4	1	31		211		391		571		751		931		p=3x2 + y2	p=4x2 + 3y2	100%
10				121		301		481		661		841		1021	p=4x2 + y2	p=5x2 + y2	12%
11		3	13		193		373		553		733		913		p=4x2 + y2	p=4x2 + y2	0%
12				103		283		463		643		823		1003	p=3x2 + y2	p=4x2 + 3y2	100%
13		7	67		247		427		607		787		967		p=3x2 + y2	p=4x2 + 3y2	100%
14				157		337		517		697		877		1057	p=4x2 + y2	p=4x2 + y2	0%
15		9	49		229		409		589		769		949		p=4x2 + y2	p=5x2 + y2	12%
16				139		319		499		679		859		1039	p=3x2 + y2	p=4x2 + 3y2	100%
17	2	1	11		191		371		551		731		911		p=3x2 - y2	p=3x2 - y2	0%
18				101		281		461		641		821		1001	p=4x2 + y2	p=5x2 + y2	12%
19		3	83		263		443		623		803		983		p=3x2 - y2	p=5x2 + 3y2	37%
20				173		353		533		713		893		1073	p=4x2 + y2	p=5x2 + 3y2	94%
21		7	47		227		407		587		767		947		p=3x2 - y2	p=5x2 + 3y2	37%
22				137		317		497		677		857		1037	p=4x2 + y2	p=5x2 + 3y2	94%
23		9	29		209		389		569		749		929		p=4x2 + y2	p=5x2 + y2	12%
24				119		299		479		659		839		1019	p=3x2 - y2	p=3x2 - y2	0%
25	8	1	71		251		431		611		791		971		p=3x2 - y2	p=3x2 - y2	0%
26				161		341		521		701		881		1061	p=4x2 + y2	p=5x2 + y2	12%
27		3	53		233		413		593		773		953		p=4x2 + y2	p=5x2 + 3y2	94%
28				143		323		503		683		863		1043	p=3x2 - y2	p=5x2 + 3y2	37%
29		7	17		197		377		557		737		917		p=4x2 + y2	p=5x2 + 3y2	94%
30				107		287		467		647		827		1007	p=3x2 - y2	p=5x2 + 3y2	37%
31		9	89		269		449		629		809		989		p=4x2 + y2	p=5x2 + y2	12%
32				179		359		539		719		899		1079	p=3x2 - y2	p=3x2 - y2	0%
33	5	1	41		221		401		581		761		941		p=4x2 + y2	p=5x2 + y2	12%
34				131		311		491		671		851		1031	p=3x2 - y2	p=3x2 - y2	0%
35		3	23		203		383		563		743		923		p=3x2 - y2	p=5x2 + 3y2	37%
36				113		293		473		653		833		1013	p=4x2 + y2	p=5x2 + 3y2	94%
37		7	77		257		437		617		797		977		p=4x2 + y2	p=5x2 + 3y2	94%
38				167		347		527		707		887		1067	p=3x2 - y2	p=5x2 + 3y2	37%
39		9	59		239		419		599		779		959		p=3x2 - y2	p=3x2 - y2	0%
40				149		329		509		689		869		1049	p=4x2 + y2	p=5x2 + y2	12%
41	7	1	61		241		421		601		781		961		p=4x2 + y2	p=5x2 + y2	12%
42				151		331		511		691		871		1051	p=3x2 + y2	p=4x2 + 3y2	100%
43		3	43		223		403		583		763		943		p=3x2 + y2	p=4x2 + 3y2	100%
44				133		313		493		673		853		1033	p=4x2 + y2	p=4x2 + y2	0%
45		7	7		187		367		547		727		907		p=3x2 + y2	p=4x2 + 3y2	100%
46				97		277		457		637		817		997	p=4x2 + y2	p=4x2 + y2	0%
47		9	79		259		439		619		799		979		p=3x2 + y2	p=4x2 + 3y2	100%
48				169		349		529		709		889		1069	p=4x2 + y2	p=5x2 + y2	12%

Таблица 2. Решения квадратичных уравнений Актина-Бернштайна

X Y	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
1	4	13	28	49	76	109	148	193	244	301	364	433	508	589	676	769	868
2	7	16	31	52	79	112	151	196	247	304	367	436	511	592	679	772	871
3	12	21	36	57	84	117	156	201	252	309	372	441	516	597	684	777
4	19	28	43	64	91	124	163	208	259	316	379	448	523	604	691	784
5	28	37	52	73	100	133	172	217	268	325	388	457	532	613	700	793
6	39	48	63	84	111	144	183	228	279	336	399	468	543	624	711	804
7	52	61	76	97	124	157	196	241	292	349	412	481	556	637	724	817
8	67	76	91	112	139	172	211	256	307	364	427	496	571	652	739	832
9	84	93	108	129	156	189	228	273	324	381	444	513	588	669	756	849
10	103	112	127	148	175	208	247	292	343	400	463	532	607	688	775	868
11	124	133	148	169	196	229	268	313	364	421	484	553	628	709	796
12	147	156	171	192	219	252	291	336	387	444	507	576	651	732	819
13	172	181	196	217	244	277	316	361	412	469	532	601	676	757	844
14	199	208	223	244	271	304	343	388	439	496	559	628	703	784	871
15	228	237	252	273	300	333	372	417	468	525	588	657	732	813
16	259	268	283	304	331	364	403	448	499	556	619	688	763	844
17	292	301	316	337	364	397	436	481	532	589	652	721	796
18	327	336	351	372	399	432	471	516	567	624	687	756	831
19	364	373	388	409	436	469	508	553	604	661	724	793	868
20	403	412	427	448	475	508	547	592	643	700	763	832
21	444	453	468	489	516	549	588	633	684	741	804
22	487	496	511	532	559	592	631	676	727	784	847
23	532	541	556	577	604	637	676	721	772	829
24	579	588	603	624	651	684	723	768	819
25	628	637	652	673	700	733	772	817	868
26	679	688	703	724	751	784	823	868
27	732	741	756	777	804	837
28	787	796	811	832	859
29	844	853	868

 

Таблица 3. Решения квадратичных уравнений нового вида 

X Y	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	7	19	39	67	103	147	199	259	327	403	487	579	679	787
2	16	28	48	76	112	156	208	268	336	412	496	588	688	796
3	31	43	63	91	127	171	223	283	351	427	511	603	703	811
4	52	64	84	112	148	192	244	304	372	448	532	624	724	832
5	79	91	111	139	175	219	271	331	399	475	559	651	751	859
6	112	124	144	172	208	252	304	364	432	508	592	684	784
7	151	163	183	211	247	291	343	403	471	547	631	723	823
8	196	208	228	256	292	336	388	448	516	592	676	768	868
9	247	259	279	307	343	387	439	499	567	643	727	819
10	304	316	336	364	400	444	496	556	624	700	784
11	367	379	399	427	463	507	559	619	687	763	847
12	436	448	468	496	532	576	628	688	756	832
13	511	523	543	571	607	651	703	763	831
14	592	604	624	652	688	732	784	844
15	679	691	711	739	775	819	871
16	772	784	804	832	868
17	871

1. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers. 1978
2. V. Ramaswami Aiyar "Sundaram's Sieve for Prime Numbers". The Mathematics Student (Madras, India). ISSN 0025-5742. 1934
3. O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008
4. Саковцев В.П. Простые числа - алгоритм поиска. Научно периодический электронный рецензируемый журнал SCI-ARTICLE.RU, сентябрь 2016
5. A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023—1030.
6. Ghannam, Talal (4 January 2011), The Mystery of Numbers: Revealed Through Their Digital Root, CreateSpace Publications, pp. 68–73, ISBN 978-1-4776-7841-1
7. Harold M. Edwars Fermat's Last Theorem. A genetic introduction to Algebraic Number Theory. Springer-Verlag New York Heidelberg Berlin, 1977
8. Виноградов И.М. Основы теории чисел. М.: Наука, 1972
9. Деза Е.И. Специальные числа натурального ряда. М.: ЛИБРИКОМ, 2011, с.95-97
10. Серпинский В. Что мы знаем и чего не знаем о простых числах. Перевод с польского И.Г.Мельникова. М.: ГИФМЛ, 1963, с.80

Рецензии:

23.02.2018, 22:38 Поплавская Лидия Андреевна
Рецензия: На сегодня существует множество алгоритмов генерации простых чисел определенного размера, получивших свое второе дыхание с развитием компьютерной техники. Причем, все они являются модификацией либо следствием известных классических и неоклассических алгоритмов как отечественных, так и зарубежных авторов, обзор фундаментальных из которых в статье не коснулся. Единого алгоритма для определения всех простых чисел на сегодня не существует, также как и не существует анализа быстродействия известных и разрабатываемых алгоритмов, их сравнения в плане эффективности и целесообразности применения. Как правило, программисты создают, на их взгляд, более компактные алгоритмы нахождения простых чисел, в которых нуждается в данный момент разрабатываемый ими проект, не доказывая сходимость процесса и не прилагая научно-обоснованный расчет быстродействия и сравнения с существующими алгоритмами, что наблюдается и в статье автора. Тем не менее, изложенный автором метод имеет место быть. А вот о его широком применении, и, вообще, о применении в частности, рецензент сомневается. Также как и в вызове интереса к нему со стороны пользователей простых чисел. Полагаю, что в журнале данный материал может быть опубликован. С уважением, Л.Поплавская

12.03.2018, 21:49 Поплавская Лидия Андреевна
Рецензия: Уважаемый Виктор Григорьевич! Я бы выразилась следующим образом: "разложил на лопатки" один из быстрых алгоритмов поиска простых чисел. С небольшой модификацией. Но объем практической работы проделан достаточный. Полагаю, какое-то внимание Ваш материал все же привлечет. И статья имеет место на продление жизни. Рекомендую статью к опубликованию. Л.Поплавская



Комментарии пользователей:

4.10.2018, 14:39 Соловьёв Виктор Григорьевич Отзыв: Уважаемый Вадим Григорьевич! Благодарю Вас за отзыв к моей статье, к которой Вы очень внимательно отнеслись, судя по Вашим замечаниям и предложениям. Я рад, что моя статья пользуется вниманием специалистов, т.к. в отличие от сомнения рецензента о широком применении алгоритмов статьи, только просмотров с момента публикации уже больше тысячи. Что касается Вашего предложения об использовании рядов по классам вычетов по модулю 900, то отмечу следующее: безусловно можно использовать подобные классы вычетов в общем случае 90*к, в том числе и 900. Однако, в предложенном мною методе, основанном на принципе Ферма-Эйлера-Аткина, быстродействие алгоритма существенно зависит, главным образом, от скорости решения квадратичной формы, подобранной по определенным признакам к исследуемому на простоту числу. В отличие от известного метода Аткина мне удалось в работе показать, что использование не 3, а в общем виде 5-ти квадратичных форм да с еще повышенными коэффициентами, позволяет увеличить быстродействие алгоритма. Похоже, что использование классов вычета по модулю 90 исчерпывает все виды квадратичных форм, включающих все простые числа. Пока - это моя гипотеза - о достаточности использования классов вычетов по модулю 90 для построения решета простых чисел. Но мои исследования показали, что при любых других классах вычетов все равно количество квадратичных форм простых чисел ограничено 5-тью мною найденными. Еще раз Вас благодарю. С уважением, Виктор Соловьёв

5.10.2018, 9:27 Соловьёв Виктор Григорьевич Отзыв: Уважаемый Вадим Григорьевич! Ваши сомнения мне понятны и даже приятны, т.к. отвечая на Ваши вопросы и предложения, мне удастся найти определенные доказательства, о которых я порой и не предполагал. Что касается ответа на вопрос по быстродействию, то оно практически (очень незначительно) не зависит от выбора модуля сравнения, но напрямую зависит от скорости решения уравнения квадратичной формы, о чем я писал ранее. А вот применение модуля 30 создаст дополнительные проблемы следующего характера: числа сравнимые по одному и тому же модулю имеют разные квадратичные формы, например, 127 = 7 mod 30 и 277 = 7 mod 30, оба числа простые и одинаковые по модулю 30. Однако, первое число имеет коэффициенты квадратичной формы 4 и 3, а второе - 3 и 1. Т.е. при проверке на простоту мы должны искать различные квадратичные формы. В моей же работе показано, что числа одинаковые при сравнении по модулю относятся к одной той же группе квадратичных форм. С уважением, Виктор Григорьевич Соловьёв

Оставить комментарий