Сколько существует определений простых чисел?

[ArtemKim]

Именно в контексте данной темы

[Батороев]

p-h-o-e-n-i-x писал(а):

Именно в контексте данной темы

Определение, вытекающее из решета Эратосфена и инерпретации p-h-o-e-n-i-x'а :

"Любое целое число, взаимнопростое с примориалом $ \prod\limits_{i=2}^{p_k} $, непревышающее
$ {p_k}^2 $, является простым".

[Батороев]

Вроде, немного разобрался с методами факторизации: по Ферма и при помощи треугольных чисел.
Оказывается, что это "звенья одной цепи", а именно:
Проверка методом Ферма осуществляется путем проверки:
$ N = a^2 - b^2 $, откуда $ N = pq = (a - b)(a +b) $, $ p = a - b $, $ q = a + b $,

а проверка методом треугольных чисел - путем проверки выражений:
$ N = \frac{a(a + 1)}{2} - \frac{b(b + 1)}{2} $ или $ N = pq = \frac{(a - b)(a + b + 1)}{2} $, откуда получаем два варианта:
- либо $ p = \frac{(a - b)}{2} $, $ q = a + b + 1 $,
- либо $ p = a - b $, $ q = \frac{(a + b + 1)}{2} $.

Эти два метода можно объединить в один:
$ N = a(a + k) - b(b + k) $, где $ k $ - целое число, или $ N = pq = (a - b)(a + b + k) $, где
$ p = (a - b) $, $ q = a + b + k $.
Для метода Ферма $ k = 0 $,
для метода треугольных чисел $ k = 1 $ (для "экономии" получаемые четные числа (при любых k нечетных) делятся на 2).

Но ведь можно пойти по пути дальнейшего изменения $ k $, при каждом из которых проводить по одному раунду (пока не дойдем до того k, которое соответствует соотношению делителей числа N).

[juna]

Вот, кстати, интересная статья

[Батороев]

Хочу предложить еще один способ факторизации чисел.
Алгоритм его реализации следующий:

Дано число $ N = ab $ $ a < b $.
Выбираем квадрат числа, превышающий $ N $, например, $ C^2 $.
Определяем остаток $ C^2\equiv c (mod N) $
Далее:
1. Проверяем не является ли полученный остаток квадратом какого-либо числа. Если – да, то проводим факторизацию аналогично методу Ферма. Если – нет, переходим к следующему пункту.
2. Проверяем, не имеют ли $ c, N $ общих делителей. Если – нет, то переходим к следующему пункту.
3. Производим последовательную проверку на наличие общих делителей у чисел $ N $ и $ [(D+i)^2-c] $, где $ i = 0, 1, 2, 3,… $, а $ D^2 $ - ближайший квадрат числа, превосходящий $ c $.

Естественно, что для реализации данного способа потребуется промежуточная факторизация большого количества чисел, но на мой взгляд, общая трудоемкость может быть меньше, чем у способов факторизации с применением решета Эратосфена и метода Ферма.
Преимущество заключается в следующем:
1.Если отношение $ \frac{b}{a} $ близко к единице, то должна получиться факторизация по Ферма (п. 1).
2.Если отношение $ \frac{b}{a} $ отлично от упомянутого, то количество проверяемых чисел меняется периодически от $ 1 $ до $ (a-1) $, т.е. в любом случае не превосходит количество чисел, проверяемых решетом Эратосфена. Эта периодичность зависит от того, какое число $ C^2 $ выбрал дешифровальщик для проверки, поэтому бОльшая или меньшая трудоемкость не может быть заранее запрограммирована шифровальщиком.

[iig]

Вот я когда-то занимался прайм числами в комплексной области.
Потом на форуме кто-то сказал, что это вроде числа Галуа.
К примеру, 5 уже не простое, поскольку сумма двух квадратов.
Дальше перейти в кватернионы поленился.
А вообще надо заниматься теорией непрерывных квазигрупп.
Там много интересного для математика и физиков тем более.

[Busy_Beaver]

Батороев в сообщении #62782 писал(а):

Какие определения простых чисел существуют (или могли быть сформулированы на основании существующих знаний) в теории чисел?

Назову определения, которые мне известны:
1. Простое число p – это то число, которое делится только на 1 или на само себя.
2. Простое число p – это нечетное натуральное число, не являющееся квадратом другого числа, и которое можно выразить в виде разности квадратов чисел не более, чем единственным способом, а именно:
$ p = [\frac{(p+1)}{2}]^2 - [\frac{(p-1)}{2}]^2 $.
Исключение – простое число 2.
3. Простое число p – это число, которое удовлетворяет условию сравнения:
$ a^{p-1}\equiv{1(mod p)}$,
где a – любое целое число, не превосходящее p.

Определение - вещь весьма и весьма субъективная. Скажем, я могу определить простое число, как натуральное число, в восьмеричной записи которого имеется не более пяти различных цифр. Другое дело, что моё определение диссонирует с конвенциональными (общепринятыми) определениями (и, заметьте, противоречит им). Но данное обстоятельство не лишает меня права на собственное определение простого числа .
Любая математическая теория строится на определениях, аксиомах и правилах вывода. И те, и другие, и третьи могут задаваться произвольно (по желанию автора теории). Помните анекдот, в котором звучит фраза "определим пустой дом, как дом, в котором не более одного человека"? Если не помните (или (быть может) не знаете), попытайтесь найти в Сети.
Удачи Вам!

[iig]

Вот тут непонятно, относится этот вопрос к комбинаторике(сколько) или к теории чисел.
Возможно, опять повторяюсь, но сначала надо определить, с чем имеем дело.
Обычно имеется в виду натуральные - целые положительные.
Далее можно обобщить до целых комплексных(там отпадают которые сумма квадратов), кватернионов и октав.
С другой стороны, подозреваю, что-то подобное в числах Галуа и далее перейти на группы, забыл как там простые называются, но это уже классификация и далеко не арифметика.