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

[Батороев]

Артамонов Ю.Н. писал(а):

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

Учитывая специфику раздела форума, хочу попросить Вас напомнить суть факторизации по Ферма.

Ранее я писал, что "вряд ли можно составить компактный тест проверки на простоту числа на основе рассматриваемого свойства".
Но, с другой стороны:
У существующих "быстрых" тестов есть одни соперники - числа Кармайкла, которые либо сами являются треугольными числами, либо довольно легко проверяются на основе рассматриваемого свойства (для проверки, на мой взгляд, можно последовательно использовать $ Q = 1,2,3,4... $). Наверное, можно совместить две проверки?
По крайней мере, мне так казтца...
(чисел Кармайкла у меня маловато)

[RIP]

Батороев
Почитайте вот это

[juna]

Да, я имел в виду именно то, на что указал RIP

[Батороев]

RIP писал(а):

Батороев
Почитайте вот это

С удовольствием посмотрел по Вашей ссылке. Спасибо RIP'у и Ю. Н. Артамонову.
Подобный метод факторизации приходил и мне на ум, что может подтвердить
ссылка.

Но на мой взгляд, это несколько иной метод: суть его можно определить, как
проверка на повторяемость остатков квадратов чисел.
Такая проверка (факторизация) начинается с чисел $ a > \sqrt{N} $ и определяется: не является ли остаток $ a^2\equiv{b^2(modN)} $, т.е. не повторил ли он остаток квадрата числа $ b < \sqrt{N} $, либо не повторяются ли уже проверенные, либо $ a^2\equiv{a(modN)} $,
Для метода Ферма важным является приближенность отношения $ \frac{a}{b} = 1$.
Именно поэтому, я хотел далее предложить совместно применять оба метода, т.к. метод Ферма некоторым образом "заполняет" пробел в указанных мной ранее "приемлемых" диапазонах рассматриваемого способа:
$ 0,33 < \frac{a}{b} < 0,75 $
$ 1,33 < \frac{a}{b} < 3 $
Тем более, что и тот, и другой метод предполагают использование множителей $ Q $.

p.s.1 Условием выполнения факторизации методом Ферма с первого шага
числа $ N = a*b $ по моим тогдашним выводам являлось выполнение неравенства:
$ (a - b)^2 < 8 \sqrt{N} $.
p.s.2 Дополнения к списку определений простых чисел, которые высказал Ю. Н. Артамонов, для меня новы и интересны (не смотря на то, что один из них является производной от предлагаемого, тем не менее является интересным сам по себе). Отдельное спасибо за это Ю. Н. Артамонову

[dmd]

Уместно ли далее развить идею Батороева, рассматривая множитель факторизуемого числа как разность k-угольных чисел? Формула для m-ного k-угольного числа:
$T_{m}^{k}=m+(k-2)m(m-1)/2$
Интересно то, что для некоторых k ответ получаем вообще за 1 шаг:

fc = Compile[x,
  S = 2699*7127;
  For[k = 3, k < 1000,
    m = IntegerPart[(k - 4 + (8(S - 1)(k - 2) + k^2)^0.5)/(2 (k - 2))] + 1;
    a = 1; mm = m;
    While[a ≠ 0 && m - mm < 1000,
      T = m + (k - 2)(m - 1)m/2;
      U = (8(T - S - 1)(k - 2) + k^2)^0.5;
      a = FractionalPart[U];
      m++
    ];
    If[a == 0, Print["k= ", k, " шагов= ", m - mm, " нод= ", GCD[2(k - 2)(m - 1) - (k - 4 + U), S]]];
    k++
  ]];

fc[1]

k= 3 шагов= 60 нод= 2699
k= 4 шагов= 528 нод= 2699
k= 5 шагов= 306 нод= 7127
k= 7 шагов= 638 нод= 7127
k= 9 шагов= 24 нод= 7127
k= 14 шагов= 73 нод= 2699
k= 16 шагов= 201 нод= 7127
k= 30 шагов= 803 нод= 2699
k= 32 шагов= 31 нод= 2699
k= 50 шагов= 462 нод= 2699
k= 65 шагов= 1 нод= 2699
k= 68 шагов= 548 нод= 2699
$Aborted

Для $S = 898423*112303$ получилось

k= 842 шагов= 10 нод= 898423
k= 1742 шагов= 10 нод= 898423
k= 3629 шагов= 81 нод= 898423

Для $S = 6334969*2402537$ уже не дождался.
Но зато при дополнительных множителях $S = 6334969*2402537*3^2*5^2*7^2*11^2$ решение нашлось:

k= 122 шагов= 886 нод= 1742116475
FactorInteger[1742116475]
{{5, 2}, {11, 1}, {6334969, 1}}

[Батороев]

dmd писал(а):

Для $S = 6334969*2402537$ уже не дождался.
Но зато при дополнительных множителях $S = 6334969*2402537*3^2*5^2*7^2*11^2$ решение нашлось:

k= 122 шагов= 886 нод= 1742116475
FactorInteger[1742116475]
{{5, 2}, {11, 1}, {6334969, 1}}

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

При этом наличие в числе $ Q = q_1*q_2*q_3*... $ подмножителей во второй степени - требование отнюдь не обязательное, особенно, если Вы уже знаете, что отношение множителей искомого числа друг к другу далеко от оптимального.

Важнее, чтобы возможных отношений подмножителей $ q $ друг к другу было, как можно больше.
Например, при факторизации по Ферма, указанное выше условие выполнения факторизации с первого шага при умножении проверяемого числа на дополнительный множитель трансформируется в следующее:
$ (a*q_2*q_3*... - b*q_1*...)^2 < 8\sqrt{Q*N} $.

[dmd]

Сам собою напрашивается вопрос: какой набор подмножителей даст наибольшее количество их соотношений?

[Батороев]

dmd писал(а):

Сам собою напрашивается вопрос: какой набор подмножителей даст наибольшее количество их соотношений?

Именно на этом вопросе я чуть не потянул головные связки
Чрезмерно большие Q (относительно проверяемого числа N) могут не подойти, по крайней мере для факторизации по Ферма.
В таком случае кажется, что лучше использовать, степени 2 (выше 2-ой) и 3, постепенно добавляя следующие простые числа. Как вариант, по-видимому, можно использовать факториалы чисел ( > 3!).

Если сравнить к примеру два числа
$ Q_1 = 302400 = 2^6*3^3*5^2*7 $
и $ Q_2 = 301687 = 29*101*103 $, то при примерном их равенстве мы получаем для $Q_1$ 61 комбинацию целочисленных соотношений, а для $ Q_2 $ - всего 4.
Хотя, еще раз повторюсь, что здесь требуются серьезные исследования.

[Батороев]

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

[У существующих "быстрых" тестов есть одни соперники - числа Кармайкла...
...(чисел Кармайкла у меня маловато)

Интересно, а можно ли доказать, что составное число, преодолевшее хотя бы один раунд проверки тестом Миллера-Рабина, является именно числом Кармайкла, а не каким-либо другим псевдопростым?
Если это возможно, то добавив к тесту Миллера-Рабина последующую проверку на делимость проверяемого числа m на числа
от $ 3 $ до $ \sqrt{\frac{4m}{1+ \sqrt{1 + 8m}} $ можно было бы получить точный тест с числом операций меньшим, чем у классического (проверка делимости числа m на числа от $ 3 $ до $ \sqrt{m} $).

p.s. А какие другие точные тесты еще существуют?
Насколько я слышал, что детерминированный полиномиальный тест еще не доведен до состояния "точный"?

[Батороев]

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

Интересно, а можно ли доказать, что составное число, преодолевшее хотя бы один раунд проверки тестом Миллера-Рабина, является именно числом Кармайкла, а не каким-либо другим псевдопростым?

Действительно, если множители составного числа $ m = p*q*r*... $ представить в виде:
$ p = x2^f + 1 $
$ q = y2^g + 1 $
$ r = z2^h + 1 $,
. . . . .
(где x, y, z - нечетные целые числа, f, g, h - целые числа)
то условие $ a^{{2^k}{t}}\equiv{-1} (mod m) $ теста Миллера-Рабина (см. здесь) выполнимо, если $ k $ нацело делится на x, y, z...(минимальное требование), что невозможно без свойства, которое присуще только числам Кармайкла, а именно:
"$ (m -1) $ без остатка делится на $ (p - 1) $, $ (q - 1) $, $ (r - 1) $...".

Остается только изменить определение раунда



p.s. Еще одно определение простых чисел:
5. Простое число - это число, которое не удовлетворяет условию сравнения:
$ (\frac{N}{3})!\equiv{0} (mod N) $
К этому свойству я прибегаю тогда, когда необходимо быстро выяснить простое ли число до 100000 (максимум возможностей инженерного калькулятора Windows).

[Батороев]

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

Например, дано число $ 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_m - N) $ не удовлетворяет условию одного из сравнений:
$ (T_m - N) \equiv{0}(mod 7) $
$ (T_m - N) \equiv{1}(mod 7) $
$ (T_m - N) \equiv{3}(mod 7) $
$ (T_m - N) \equiv{6}(mod 7) $,
то это - не треугольное число.
Исходя из этого свойства, в рассматриваемом примере можно было сократить 26 шагов.

[Батороев]

Тем, кто пользуется методом факторизации по Ферма, по-видимому, может пригодиться следующее мое предположение (естественно, если оно верно):

Для всех нечетных составных чисел m = p*q (где p и q - числа, взаимнопростые с числом 144), имеющих по основанию 144 одинаковые остатки,
остатки чисел $ (\frac{p + q}{2})^2 $ и $ (\frac{p - q}{2})^2 $ определены единственным образом.

В виду корявости формулировки приведу пример:
Дано число $ m = 4 398 693 379 $
$ m\equiv{115}(mod 144) $
На малых числах (в данном случае, на числе 115) можно видеть, что числа с таким остатком имеют
$ (\frac{115 + 1}{2})^2\equiv{52}(mod 144) $ или
$ (\frac{23 + 5}{2})^2\equiv{52}(mod 144) $.

Остаток $ {52}(mod 144) $ имеют квадраты чисел $ (72*k\pm{14}) $, где $ k $ - целое число.

Проверяя методом Ферма только такие числа, мы на 135-м ходу получим положительный результат (против 4827 шагов по обычному пути метода Ферма) в виде
$ 71150^2\equiv{25761^2}(mod 4 398 693 379) $.

[Батороев]

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

Тем, кто пользуется методом факторизации по Ферма, по-видимому, может пригодиться следующее мое предположение (естественно, если оно верно):

Для всех нечетных составных чисел m = p*q (где p и q - числа, взаимнопростые с числом 144), имеющих по основанию 144 одинаковые остатки,
остатки чисел $ (\frac{p + q}{2})^2 $ и $ (\frac{p - q}{2})^2 $ по основанию 144 определены единственным образом.

Не научился я доказывать что-либо математически, но попытаюсь:
Имеются два числа $ m = pq $ и $ n = ab $, имеющие одинаковый остаток по основанию 144, где
$ a, b, p, q $ - числа, взаимнопростые с числом $ 144 = 2^4*3^2 $.
Представление этих чисел в виде разности квадратов следующее:
$ m = (\frac{pq +1}{2})^2 - (\frac{pq - 1}{2})^2 = (\frac{p + q}{2})^2 - (\frac{p - q}{2})^2 $
$ n = (\frac{ab +1}{2})^2 - (\frac{ab - 1}{2})^2 = (\frac{a + b}{2})^2 - (\frac{a - b}{2})^2 $
Т.к. рассматриваемые числа имеют одинаковые остатки по основанию 144, то одинаковые остатки имеют и выражения:
$ (\frac{pq +1}{2})^2\equiv{s}(mod 144) $
$ (\frac{ab +1}{2})^2\equiv{s}(mod 144) $,

Аналогично:
$ (\frac{pq - 1}{2})^2\equiv{t}(mod 144) $
$ (\frac{ab -1}{2})^2\equiv{t}(mod 144) $

Т.к. $ [(\frac{pq +1}{2})^2 - (\frac{p + q}{2})^2] = \frac{(p^2 - 1)(q^2 - 1)}{4}\equiv{0}(mod 144) $
$ [(\frac{ab +1}{2})^2 - (\frac{a + b}{2})^2] = \frac{(a^2 - 1)(b^2 - 1)}{4}\equiv{0}(mod 144) $,
то
$ (\frac{p + q}{2})^2\equiv{s}(mod 144) $
$ (\frac{a + b}{2})^2\equiv{s}(mod 144) $.

Т.к. $ [(\frac{pq - 1}{2})^2 - (\frac{p - q}{2})^2] = \frac{(p^2 - 1)(q^2 - 1)}{4}\equiv{0}(mod 144) $
$ [(\frac{ab - 1}{2})^2 - (\frac{a - b}{2})^2] = \frac{(a^2 - 1)(b^2 - 1)}{4}\equiv{0}(mod 144) $,
то
$ (\frac{p - q}{2})^2\equiv{t}(mod 144) $
$ (\frac{a - b}{2})^2\equiv{t}(mod 144) $.

Не уверен, что это - хорошее доказательство (а может и не доказательство вообще),
но важнее другое:

Аналогичным образом можно рассматривать и другие основания, такие как
$ 14400 = 2^6*3^2*5^2 $
$ 7056 = 2^4*3^2*7^2 $
$ 66585600 = 2^{10}*3^2*5^2*17^2 $ и т.д.

Это утверждение дает возможность оптимизировать метод факторизации Ферма, имея в виду, что:

$ (pq)^{n} = (\frac{p^n + q^n}{2})^2 - (\frac{p^n - q^n}{2})^2 $.

[ArtemKim]

Строим полуокружность на ее диаметре AB.
Все следующие ломаные имеют начальную точку A и конечную точку B.
k(1)=2.
В полуокружность вписываем равносторонний k(1)-сторонник.
Вписываем в ту же полуокружность равносторонний k(2)-сторонник с наименьшим периметром такой, что k(2)-сторонник не имеет общих вершин с k(1)-сторонником кроме A и B.
Вписываем в ту же полуокружность равносторонний k(3)-сторонник с наименьшим периметром такой, что k(3)-сторонник не имеет общих вершин с k(1)-сторонником и k(2)-сторонником кроме A и B.
Вписываем в ту же полуокружность равносторонний k(4)-сторонник с наименьшим периметром такой, что k(4)-сторонник не имеет общих вершин с k(1)-сторонником, k(2)-сторонником и k(3)-сторонником кроме A и B.
...
Пусть таким образом построены все k(1)-,...,k(n-1)-сторонники.
Сколько сторон будет у k(n)-сторонника?

[ИСН]

Боян. http://dxdy.ru/viewtopic.php?p=67394
С другой стороны, если рассматривать в контексте данной темы, то может, и не боян...