немного о делителях составных чисел

[GogalNikolay]

tolstopuz в сообщении #1736627 писал(а):

Даже еще проще:

Пусть $n=pq>1$

а если н простое...Всё правильно, мы с вами ограничиваем один и тот же интервал, и разница при а в районе 40 на сотые идёт, а дальше и вообще... Доказательство верное, правда, считать придётся корни вплоть до копейки, и эти копейки редко, но будут появляться, и только для одного значения это а-2, тут можно было поставить, что р меньше или =, и тогда считать только целое значение... Да и теорема не столько о составных числах сколько))) Когда n простое или составное — это неважно, важен вывод... Другой, как вы считаете? Какой?

[lel0lel]

Стартовый пост напомнил тему:
post1708931.html#p1708931
Пункт 1 ("У него существует простой делитель $p\leq\tau$")
непосредственно следует из пункта 2 ("Не существует простого делителя $\tau<q<a$").
Ведь если число составное, а делителей на интервале $(\tau,a)$ нет, то, очевидно, что все делители меньшие корня квадратного из заданного числа меньше либо равны $\tau$. Кстати, в пункте 2 необязательно говорить про простой делитель. Метод Ферма гарантирует, что на интервале $(\tau,a)$ нет никаких делителей.

[GogalNikolay]

GogalNikolay в сообщении #1736673 писал(а):

Да и теорема не столько о составных числах сколько))) Когда n простое или составное — это неважно, важен вывод... Другой, как вы считаете? Какой?

Известно, что для проверки составности числа $m$ достаточно искать простые делители до $\sqrt{m}$: если делитель не найден в этом диапазоне, число простое. Мы показываем, что для любого составного $m$, лежащего строго между соседними квадратами $a^2$ и $(a+1)^2$ (то есть $a = \lfloor \sqrt{m} \rfloor$), граница поиска может быть существенно снижена — при условии, что $m$ не представимо в виде разности квадратов $(a+1)^2 - k^2$ с малым $k$. Поскольку каждое натуральное число лежит между какими-то соседними квадратами, теорема применима ко всем составным числам без исключения (с указанной оговоркой).

Теорема. Пусть $a \geq 5$ и $m \in \left(a^2,\; (a+1)^2\right)$ — составное число, не представимое в виде $(a+1)^2 - k^2$ ни при каком целом $k \leq \sqrt{2a}$. Тогда $m$ имеет простой делитель $p < \tau$, где $\tau = a - \sqrt{2a} + 2$.

Доказательство (от противного). Положим $\tau = a - \sqrt{2a} + 2$. Предположим, что все простые делители $m$ не меньше $\tau$.

1. Поскольку $\tau^3 > (a+1)^2$ при $a \geq 5$, число $m$ не может иметь трёх и более простых делителей (с учётом кратности). Следовательно, $m = p \cdot q$, где $p \leq q$ — простые.
2. Оба делителя нечётны, поэтому $s = \frac{p+q}{2}$ и $d = \frac{q-p}{2}$ — целые, и $m = s^2 - d^2$.
3. Из $m > a^2$ следует $s \geq a+1$. Из $p \geq \tau$ следует $d \leq s - \tau = s - a + \sqrt{2a} - 2$.
4. Если $s = a+1$, то $m = (a+1)^2 - d^2$ с $d \leq \sqrt{2a}$ — это противоречит условию теоремы.
5. Если $s \geq a+2$, то из $m < (a+1)^2$ следует $d > \sqrt{s^2 - (a+1)^2}$. При $s = a+t$ ($t \geq 2$):

$$ \sqrt{2a(t-1) + t^2 - 1} > t + \sqrt{2a} - 2 = s - a + \sqrt{2a} - 2 \geq d, $$

что даёт противоречие.

Таким образом, предположение неверно: у $m$ обязательно есть простой делитель $p < \tau$. Это означает, что для чисел указанного вида не требуется проверять делители до $\sqrt{m}$ — достаточно ограничиться существенно меньшей границей $\tau = a - \sqrt{2a} + 2$, которая асимптотически значительно меньше $\sqrt{m}$.

[Dmitriy40]

GogalNikolay в сообщении #1737959 писал(а):

Это означает, что для чисел указанного вида не требуется проверять делители до $\sqrt{m}$ — достаточно ограничиться существенно меньшей границей $\tau = a - \sqrt{2a} + 2$, которая асимптотически значительно меньше $\sqrt{m}$.

С чего бы "значительно меньше"? Перепишем $\tau = a - \sqrt{2a} + 2 = a \left (1 - \frac{\sqrt{2}}{\sqrt{a}} \right ) + 2$ и увидим что выражение в скобках уменьшается с ростом $a$, т.е. асимптотика оказывается такой же $O(a)=O(\sqrt{m})$, а не меньше. Абсолютное количество меньше, но относительное почти столько же, и с ростом $m$ относительная выгода снижается.
Например для $m=10^{30}$ вместо 29844570422669 простых до квадриллиона можно проверить лишь 29844569127319 простых, всего на 1295350 меньше. Уменьшение времени менее $10^{-7}$. Чисто теоретически может и интересно, практически смысла ровно ноль.

[GogalNikolay]

Dmitriy40 в сообщении #1737970 писал(а):

исто теоретически может и интересно, практически смысла ровно ноль.

Да, я не говорю об эффекте пользы, эффект в том, что мы отсекаем хвост самых больших делителей, самый трудозатратный и дорогой тест, да, эффект небольшой. .. : выигрыш аддитивный, порядка $m 1/4$

проверок, причём именно самых затратных по каждой операции. Для чисел, где триальный перебор вообще применим, это ощутимая экономия; для 100-значных гигантов — капля в море, но там и без нашей теоремы перебором никто не занимается.

[Dmitriy40]

GogalNikolay в сообщении #1737972 писал(а):

Для чисел, где триальный перебор вообще применим, это ощутимая экономия;

Это для каких это?
Для чисел до триллионов перебор идёт по простым до миллионов, экономия всего сотни чисел из сотни тысяч, это ни о чём.
А для чисел более триллионов выгоднее тест Миллера, он для таких чисел (ну может ошибся на пару порядков, не суть) быстрее триального перебора и гарантирует простоту чисел вплоть до $10^{36}$ (с проверкой до 20 оснований).
А для чисел более $10^{36}$ триальный перебор и непременим - слишком медленный.
Так для каких же чисел будет ощутимая выгода от предлагаемой идеи? До тысячи что ли? Или до миллиона? Такие вообще вычислять не надо, достаточно битовой маски в сотню кБ.

[GogalNikolay]

Dmitriy40 в сообщении #1737982 писал(а):

Это для каких это?

Да, с вами согласен, я, пожалуй, с перебором загнул.


Соглашусь — по практической части претензия справедливая, спорить не буду. Честная раскладка:

- при $m \sim 10^{12}$ экономия — порядка сотни простых из 78498 проверяемых ($\approx 0{,}1\%$);
- при $m \sim 10^{15}$ — около 460 из примерно 2 млн ($\approx 0{,}02\%$);
- при $m \sim 10^{18}$ — около 2000 из 50 млн ($\approx 0{,}004\%$).

Для простоты-теста это действительно ни о чём: пока число влезает в машинное слово, все деления стоят одинаково, никакого «дорогого хвоста» нет; а если не влезает — триальный перебор мёртв и без всякой теоремы. Малые числа закрываются решетом и битовой маской, как вы и написали.

Так что снимаю практическую формулировку и оставляю теоретическую. Содержание результата — в разборе случаев: любое составное $m$ из интервала $(a^2, (a+1)^2)$ либо представимо как $(a+1)^2 - k^2$ с $k \leq \sqrt{2a}$ — и тогда раскладывается на множители прямым перебором $O(m^{1/4})$ кандидатов, — либо обязано иметь простой делитель меньше $a - \sqrt{2a} + 2$. Иначе говоря, составное число между соседними квадратами либо почти разность квадратов, либо у него есть относительно небольшой делитель. Это элементарное утверждение о структуре делителей, а не инструмент факторизации — и претензий на практическую пользу я при такой формулировке не заявляю.

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

Итого: как ускорение — нет, как уточнение структуры — да. Теорема верна, скромна и практически бесполезна. Бывает и такое.

[venco]

Dmitriy40 в сообщении #1737982 писал(а):

гарантирует простоту чисел вплоть до $10^{36}$ (с проверкой до 20 оснований)

А можно узнать эти основания? Что-то я не могу найти.

[Dmitriy40]

venco в сообщении #1738005 писал(а):

А можно узнать эти основания? Что-то я не могу найти.

Пожалуйста:

рувики про тест Миллера писал(а):

Вышеописанные условия проверки определены для сколь угодно больших простых чисел, а для фиксированных чисел, известны (на 2016 год), результаты, по которым числа $n\le10^{36}$, можно проверять на простоту, ещё быстрее. Ниже в качестве примера даны некоторые из них (для них используем тот же классический алгоритм Миллера, но с очень малым количеством оснований):

число n < 2 047 простое, если оно сильно псевдопростое по основаниям a = 2;
число n < 1 373 653 простое, если оно сильно псевдопростое по основаниям a = 2, 3;
число n < 25 326 001 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5;
число n < 3 215 031 751 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7;
число n < 2 152 302 898 747 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11;
число n < 3 474 749 660 383 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13;
число n < 341 550 071 728 321 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17;
число n < 3 825 123 056 546 413 051 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
число n < 318 665 857 834 031 151 167 461 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
число n < 3 317 044 064 679 887 385 961 981 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41;
…
число n < 1 543 267 864 443 420 616 877 677 640 751 301 простое, если оно сильно псевдопростое по всем простым основаниям от 2 до 61 включительно;
число $n\le10^{36}$ простое, если оно сильно псевдопростое по всем простым основаниям от 2 до 71 включительно.
Первое составное число $n$, которое является сильно псевдопростым по всем простым основаниям до 71 включительно, пока не найдено, но известно, что $n>10^{36}$.
То есть известно (на 2016 год), что все числа, меньшие чем $10^{36}$, являющиеся сильно псевдопростыми, по первым 20-ти основаниям (до 71 включительно), являются также, простыми.

Пруф есть в англовики.

Для чисел до $2^{64}$ количество проверок можно ещё чуть уменьшить (до 7 разных оснований), табличка "The best known SPRP bases sets" (ссылка есть тоже в англовики под сноской 21).
Там же чуть ниже есть ссылка "Bradley Berg found very dense hashes up to $2^{64}$. Latest version can be found on his website http://www.techneon.com/" вычисления (частично таблично) оснований в зависимости от числа, так удаётся ещё уменьшить их количество, до трёх: "32 bit numbers are checked with a single SPRP test, two are used for 49 bit numbers, and three for 64 bit numbers.". Табличка не сказать чтобы большая, 32кБ. Почти аналогичный результат (на одну 4кБ табличку больше) чуть ниже и ранее: "Dana Jacobsen posted his own hashes up to $2^{64}$: http://probableprime.org/download/example-primality.c".

-- добавлено через 25 минут --

Кстати там же ниже в разделе Links есть ссылка на 200МБ архив 2-SPRP-2-to-64.zip со списком всех 33млн сильных псевдопростых по основанию 2 до $2^{64}$ (630МБ текста). Если как-то его хранить и проверять, то до $2^{64}$ можно обойтись вообще проверкой по одному основанию 2.

[venco]

От $2^{64}$ до $10^{36}$ далеко, и, насколько я понял, те 20 оснований - оценка, причём, похоже, при условии, что расширенная гипотеза Римана верна - статья слишком сложная для меня.

[Dmitriy40]

venco
ГуглИИ утверждает что в той статье GRH не используется, может Вам будет понятнее:

Цитата:

Связь с GRH в смежной литературе. Обобщённая гипотеза Римана часто упоминается во введениях или обзорах к подобным статьям как исторический и теоретический контекст — именно GRH позволяет гарантировать детерминированность полиномиального теста Миллера при проверке оснований до $2\ln^2 n$. Однако для получения конкретных числовых границ до $10^{36}$ в данной работе используется исключительно элементарная теория чисел (китайская теорема об остатках, символы Якоби и биквадратичных вычетов в кольце гауссовых целых чисел $\mathbb{Z}[i]$) и прямой компьютерный перебор.
Итоговый статус результатов. Найденные в статье границы применимости детерминированного теста Миллера–Рабина для конкретных классов чисел не опираются на недоказанные гипотезы,

Я не компетентен и ничего утверждать не могу.

[venco]

Почитал статью. Они на известных псевдопростых до $10^{12}$ заметили закономерность, что все рекорды относятся к двум классам чисел, и посчитали эти два класса до $10^{36}$. Все они проваливают тест по первым 20 простым, из этого делается вывод, что скорее всего этого ну точно достаточно.

[Dmitriy40]

Походу строго доказано только это:

Цитата:

число n < 3 317 044 064 679 887 385 961 981 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41;

А всё что больше - гипотезы.