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

[Батороев]

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

Назову определения, которые мне известны:
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.

[esperanto]

Существует бесконечное множество, определений.

[незваный гость]

Увы, я не уверен, что Вы привели хотя бы одно определение.

Простым числом называется натуральное число $p$ большее 1, и не имеющее натуральных делителей, отличных от 1 и самого себя.

Вы, конечно, можете сказать, что подразумеваете то и это, но: это математика, а не филология или история. Здесь принято быть точным. Формально.

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

И еще вопрос, что такое определение, о котором Вы говорите? Я привел единственное определение, известное мне. Но очевидно, что существует бесконечно много теорем вида «Q(x) тогда и только тогда, когда x простое». Тогда любое из этих Q(x) можно принять за определение простоты числа, и рассматривать все остальное как теоремы. Только вот кому это нужно?!

[Батороев]

незваный гость писал(а):

:evil:
Увы, я не уверен, что Вы привели хотя бы одно определение.

Простым числом называется натуральное число $p$ большее 1, и не имеющее натуральных делителей, отличных от 1 и самого себя.

Вы, конечно, можете сказать, что подразумеваете то и это, но: это математика, а не филология или история. Здесь принято быть точным. Формально.

Признаю свои ошибки - прошу извинить меня за "дремучесть"

незваный гость писал(а):

: существует бесконечно много составных чисел, удовлетворяющих критерию три.

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

незваный гость писал(а):

:И еще вопрос, что такое определение, о котором Вы говорите? Я привел единственное определение, известное мне. Но очевидно, что существует бесконечно много теорем вида «Q(x) тогда и только тогда, когда x простое». Тогда любое из этих Q(x) можно принять за определение простоты числа, и рассматривать все остальное как теоремы. Только вот кому это нужно?!

Целью моего обращения за помощью и является получить хоть часть информации ( а лучше полную) об этих самых Q(x).
А нужно это мне для того, чтобы оценить - нова ли идея, меня посетившая.

[bot]

Третье вообще ничего не определяет - среди целых a, не превосходящих p есть, к примеру 0 и само число p. Можно сделать оговорку: a взаимно просто с p или без оговорки. но домножить сравнение на a. Но и это не поможет.

Батороев писал(а):

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

А что такое по Вашему число Кармайкла? Возьмём 561 - минимальное из них.

Можете сами проверить, что для всех $a$, взаимно простых с 561 справедливо сравнение:
$a^{560}-1 \equiv 0 (mod 561)$

[RIP]

Определение 3 можно поправить, потребовав $p>1$ и навесив на $a$ условие $1\leqslant a\leqslant p-1$.

[незваный гость]

Батороев писал(а):

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

Подумав, я тоже сомневаюсь . С уточнением RIP будет работать.

Батороев писал(а):

Целью моего обращения за помощью и является получить хоть часть информации ( а лучше полную) об этих самых Q(x).

Дурное это дело. Переписывать всё изданное по теории чисел (даже фрагментарно).

Батороев писал(а):

А нужно это мне для того, чтобы оценить - нова ли идея, меня посетившая.

Давайте проще: Вы напишите, и мы поможем оценить. Поскольку Вам надо написать всего одну идею, а нам бесконечно-много.

[Батороев]

незваный гость писал(а):

:Дурное это дело. Переписывать всё изданное по теории чисел (даже фрагментарно).

Батороев писал(а):

А нужно это мне для того, чтобы оценить - нова ли идея, меня посетившая.

Давайте проще: Вы напишите, и мы поможем оценить. Поскольку Вам надо написать всего одну идею, а нам бесконечно-много.

Проще - так проще...
Тогда не судите строго, если это - общеизвестно, "сыровато" или "вычурно чрезвычайно"
Продолжу список:

4. Простое число p - это нечетное натуральное число, которое может быть представлено в виде разности двух треугольных чисел не более, чем двумя способами, а именно:
$ 1. p = T_p - T_{(p -1)} $
$ 2. p = T_{\frac{(p + 1)}{2}} - T_{\frac{(p - 3)}{2}} $.
Исключение - простое число 2.

На основании указанного свойства, вряд ли, можно составить компактный тест проверки простоты числа, но в отношении факторизации составных чисел, как мне кажется, это свойство может быть достаточно полезным, особенно для чисел, у которых отношение делителей друг к другу невелико (по-моему, именно такие числа представлены на RSA Security, по крайней мере те, что уже расшифрованы).

Например, дано число $ N = 19235773 $
Ближайшее треугольное число $ T_m $ , превосходящее N:
$ \sqrt{2*19235773} = 6203 $
$ T_m = T_{6203} = \frac{m*(m+1)}{2} = \frac{6203*6204}{2} = 19241706 $
Проверяем, является ли разность$ (T_m - N) $ треугольным числом, т.е. целочисленно ли $ \sqrt{8(T_m - N) + 1} ?$
Оказалось, что нет.
Берем следующее треугольное число и проверяем.
И на шестидесятом шаге имеем:
$ T_{6262} = 19609453 $
$ 19609453 - 19235773 = 373680 $
$ \sqrt{(8*373680 + 1)} = 1729 $
$ \frac{1729 - 1}{2} = 864 $
НОД$ [(6262-864), 19235773] = 2699 $.
Итого, имеем $ N = 2699*7127 $.
Это - пример "ручной" работы. На компе, надеюсь, гораздо проще.

[neo66]

Надо ентот алгоритм в деле проверить ! Совершенно бесплатно даю ссылку http://www.rsa.com/rsalabs/node.asp?id=2093#RSA2048. Там предлагают за 200000$ разложить на множители число, состоящее из 617 десятичных цифр. Успехов

[Батороев]

neo66 писал(а):

Надо ентот алгоритм в деле проверить ! Совершенно бесплатно даю ссылку http://www.rsa.com/rsalabs/node.asp?id=2093#RSA2048. Там предлагают за 200000$ разложить на множители число, состоящее из 617 десятичных цифр. Успехов

Помилуйте, я даже не представляю, как "ворочить" такие числа.
Один раз я там был. "Завел" в свой калькулятор одно число - а корень не берется.
Пришлось возвращаться из ссылки

Вот, если кому-нибудь мастеровому удастся там что-нибудь взломать, да при этом ему в чем-то поможет упомянутый метод, то буду рад его благодарности

[незваный гость]

Да, можно доказать такую теорему. Насколько она нова - судить не берусь. Что же касается применения для факторизации, то зело сомневаюсь. С практической точки зрения извлечение квадратных корней дело куда более утомительное, чем деление.

[Батороев]

незваный гость писал(а):

:evil:
Да, можно доказать такую теорему. Насколько она нова - судить не берусь.

Вы правы, без доказательства факта - это не теорема, без доказательства новизны - это даже не "гипотеза Батороева"
Но, если "она" все же нова, то двери для сотрудничества в доказательстве открыты настежь.

незваный гость писал(а):

:Что же касается применения для факторизации, то зело сомневаюсь. С практической точки зрения извлечение квадратных корней дело куда более утомительное, чем деление.

Если под практическим применением понимать факторизацию чисел из RSA Lab, то Вы правы.
Но насклько мне представляется, в практической криптографии используются числа с 70-100 знаками, из которых корни все же можно извлекать.
Хотя, я могу и ошибаться, т.к. с большими числами работать не умею.

Я не утверждаю, что этот способ - панацея на все случаи. Он годится только для чисел с небольшим отношением делителей.
Но ведь, чем большим количеством приемчиков владеет дешифровальщик, тем сложнее шифровальщику

[незваный гость]

Рассмотрим произвольное нечетное натуральное $x$. Для любого представления в виде произведения $x = p \cdot q$ имеем $T(a)-T(b) = p q$. Но $T(a)-T(b) = \frac12(a-b)(a+b+1)$, то есть $(a-b)(a+b+1) = 2 p q$. Имеем 4 варианта: $a-b = p$, $a-b = 2p$, $a-b = q$, $a-b = 2q$. Каждому изтих вариантов соответствует решение: $a=q+\frac{p-1}2, b=q-\frac{p+1}2$, $a = p+\frac{q-1}2, b=\frac{q-1}2-p$, $a=p+\frac{q-1}2, b=p-\frac{q+1}2$, и $a = q+\frac{p-1}2, b=\frac{p-1}2-q$. Не все они удовлетворяют условию (некоторые отрицательные, некоторые могут совпадать, но важно, что они есть).

Названные Вами разложения соответствуют $p=1, q=x$. Тогда и только тогда, когда появляются дополнительные делители, появляются и дополнительные представления в виде разности.

Осталось некоторое количество технических деталей, но в целом утверждение доказано…

[Батороев]

незваный гость писал(а):

:evil:
Осталось некоторое количество технических деталей, но в целом утверждение доказано…

Интересно, приводил ли кто-нибудь до Вас подобное?
Если - нет, то мог бы Вас поздравить.

В предыдущих сообщениях я утверждал, что предлагаемый способ факторизации эффективен при небольших отношениях делителей составного числа, например $ S = a*b $, т.е. когда отношение $ \frac{a}{b} $ невелико.
Но это не совсем правильное утверждение, т.к. мои последующие "исследования" показали, что оптимальным отношением делителей является $ \frac{a}{b} = 2 $ (по-видимому, тоже требует доказательства). Эквивалент $ \frac{a}{b} = \frac{1}{2} $.

При отношении делителей, близком к указанному, проверка состоит всего из одного шага.
При отклонении от этого оптимума как вверх, так и вниз эффективность уменьшается.
Вполне приемлемыми, на мой взгляд, можно считать 2 диапазона
$ 1,33 < \frac{a}{b} < 3$
$ 0,33 < \frac{a}{b} < 0,75$


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

В чем смысл этого принципа:
Имеем составное число S, отношение делителей которого нас не устраивает, но мы об этом, естественно, не знаем.
Если усложнить число S, умножив его на другое, например на $ Q = {q_1}^2*{q_2}^2 $, то получим число $ (Q*S) $, одна из комбинации отношений делителей которого, может оказаться достаточно близкой к оптимальному (т.е. находиться в одном из "приемлемых" диапазонов), например:$ \frac{a*q_2}{b*{q_1}^2*q_2} $.
Квадраты в числе Q необходимы для того, чтобы не нарушить исходное отношение a/b, если оно само по себе было близким к оптимальному.
Каким (или какими) должно быть число Q ?
Для этого, по-видимому, требуется проведение настоящих серьезных исследований.

[juna]

Все это очень напоминает факторизацию по Ферма, и вычислительная сложность видимо такого же порядка.
Вот еще два очевидных следствия, которые можно приспособить для определений:
1. Если $p$ - простое число, то квадратное уравнение $x^2-bx+p=0$ не разрешимо в целых числах ни при каких целых $|b|<p$
2. Любое нечетное простое число не представимо в виде суммы последовательных нечетных чисел.