Сумма коэффициентов, кроме первого и второго, сокращённых на P

Усовершенствование методов: поиска и алгоритмов генерации простых чисел

Даная работа рассматривает проблематику не совершенство методов: поиска и алгоритмов генерации простых чисел. А именно: поиск простых чисел, на данный момент времени, осуществляется либо путём оценки и исследовании малой теоремы Ферма (МТФ), обобщенной до теорем: Кармайкла и Лангража для конечных циклических групп. Либо путём оценки и исследовании теста Агравала-Каяла-Саксены (AKS-тест). Что влечёт за собой: в первом случае полиномиальность вычислений, т. е. сложность вычисления растёт в зависимости от входных данных, но количество которых находится в разумных пределах. Во втором же случае, полиномиальность т. е. сложность вычисления, слабо зависима от входных данных, однако количество которых растёт, в зависимости от величины проверяемого числа. Что автоматически усложняет алгоритмы генерации простых чисел.

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

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

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

Для усовершенствования методов: поиска и алгоритмов генерации простых чисел нам потребуются: AKS (истинный тест простоты), бином Ньютона и МТФ.

Сперва рассмотрим и осознаем, как работает и что на может дать, тест Агравала-Каяла-Саксены (AKS-тест)

Тест Аграва́ ла — Кая́ ла — Саксе́ ны ( тест AKS ) — единственный известный на данный момент универсальный (то есть применимый ко всем числам) полиномиальный, детерминированный и безусловный (то есть не зависящий от недоказанных гипотез) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.

Формулировка Теста Аграва́ ла — Кая́ ла — Саксе́ ны

Здесь и далее or(n) обозначает показатель числа n по модулю r, log — двоичный логарифм и φ (⋅ ) — функция Эйлера.
Сравнение по двум модулям вида a(x)≡ b(x)(modh(x), n) для многочленов a(x), b(x)∈ \Z[x] означает, что существует g(x)∈ \Z[x] такой, что все коэффициенты многочлена a(x)− b(x)− g(x)h(x) кратны n, где \Z[x] — кольцо многочленов от x над целыми числами.

Т. е. Возведённый многочлен вида (x-1) в степень P. Даст все коэффициенты, за исключением стоящих при наивысших степенях равных P, делящиеся без остатка на P.

Для удобства работы с AKS-тестом, используем Бином Ньютона.
Пере формулировка теста простоты (истинного), при помощи
формулы бинома Ньютона

Бином Ньютона

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

(P-1)/2 – Количество уникальных биномиальных коэффициентов.

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

Тогда, сперва определим сумму всех биномиальных коэффициентов

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

(1+ +( * +( * * ... ( * * ... =>
1 + = 2*x₁ =>

+ * * => (x₁₊ x₂) = 2 x₃=> 2(2(2(…(X_P) = 2^P =>

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

1+ +( * +( * * ... ( * * ... =

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

+ ( * +( * * ... ( * * ... =

Сумма коэффициентов, кроме первого и второго, сокращённых на P

( +( * ... ( * ... = ? N

В зависимости от количества уникальных биномиальных коэффициентов , количество элементов, оказывающих влияние на итоговый результат проверки числа на простоту, растёт. Количество которых равно, количеству уникальных биномиальных коэффициентов
1+( +( * ... ( * ... = ? N

– = 0

Т. е. Количество элементов, переносимых в правую часть уравнения, для сохранения истинности теста простоты, равняется .

Рассмотрим несколько простых чисел P=3; 5

Для P=3

( ( * ... ( * ... = = 0

Для P=5

( * ... = = 0

Зная число вычитаемых элементов, для обнуления уравнения, найдем (P_(п)) - число проходящее тест простоты

Поскольку количество вычитаемых элементов равно, количеству уникальных биномиальных коэффициентов, перепишем формулу.

= b

2b + 1=P₍_п₎

= =1+( ) + ( ) +…

Формула максимального значения уникального коэффициента, сокращённого на P_(п)

Зная всё выше перечисленное, выведем общую формулу простого числа

формула простого числа

( ) = P

b = (2N+1) + ( )

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

«Формальная» формула простого числа

( ) = P_ф

b = N + Ф_с+ Ф_п

Ф_с~ ; Ф_п

Где N – порядковый номер простого числа, Ф_{с –}количество чисел не удовлетворяющих малой теореме Ферма, на интервале от 1 до N. 3-отношения количества всех чисел, (на интервале от 1 до N) к количеству чисел вида
. Ф_{п -}количество псевдо-простых чисел, удовлетворяющих МТФ. []-округление вверх.

Выявим фактор простоты числа Ф_с

Для этого из количества чисел, проходящих проверку Фактора простоты, вычтем те, что её заведомо не пройдут.

Ф_с~

= 3

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

Выявим фактор псевдо-простоты числа Ф_п

d – порядковый номер числа

N	Pп=b+1	Уровень проверки	=	b=
				2d
				4d
				6d
				8d
				10d
				12d
				340d

P_(п)₌3

= -1=0

P_(п)=5

- = =0

P_(п)=7

- =

P_(п)=9

P_(п)=11

- = 5 -15 -30-42=0

P_(п)=13

(2¹-1)(2¹+1)(2²+1)(2²-2+1) (2²+2+1)(2⁴-2²+1) - =

1-6-22-55-99-132=0

Вывод: все поставленные задачи были решены в ходе данной работы.

Примечание:
Ф_с– точность вычисления, количества чисел не удовлетворяющих малой теореме Ферма, на интервале от 1 до N, может быть повышена до абсолютной.
Вычисление P_{ф –} может быть существенно облегчено, путём взаимного сокращения, частного и делителя

Список литературы и интернет источников:

https: //ru. wikipedia. org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%90%D0%B3%D1%80%D0%B0%D0%B2%D0%B0%D0%BB%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%8F%D0%BB%D0%B0_%E2%80%94_%D0%A1%D0%B0%D0%BA%D1%81%D0%B5%D0%BD%D1%8B

https: //ru. wikipedia. org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0

https: //ru. wikipedia. org/wiki/%D0%9C%D0%B0%D0%BB%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

12 3 4 5 6 7 8 9 10 Следующая ⇒