Числа Кармайкла.

[maxal]

Батороев
Никаких претензий. В статье написано написано ln(N)^2, а не ln(N^2).

[Батороев]

maxal писал(а):

Батороев
Никаких претензий. В статье написано написано ln(N)^2, а не ln(N^2).

И это следует читать, как (ln N)^2?
Тоды - "Ой"!

Добавлено спустя 17 минут 28 секунд:

maxal писал(а):

Skipper
Доверяйте только авторитетным источникам. У Василенко написано

$$a^{(n-1)/2^k}$$

и это правильно. Здесь $k$ пробегает значения от 1 до $v_2(n-1)$ (что не превосходит $\log_2 n$).

Как может $k$ зависеть от $\log_2 n$?

[maxal]

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

maxal писал(а):

Skipper
Доверяйте только авторитетным источникам. У Василенко написано

$$a^{(n-1)/2^k}$$

и это правильно. Здесь $k$ пробегает значения от 1 до $v_2(n-1)$ (что не превосходит $\log_2 n$).

Как может $k$ зависеть от $\log_2 n$?

$$k\leq v_2(n-1) \leq \log_2 n$$

[Батороев]

По-видимому, в разных источниках описаны разные алгоритмы Миллера или я что-то недопонимаю

Как я представляю себе детерминированный вариант теста Миллера-Рабина (алгоритм Миллера).

Согласно этого алгоритма первым делом выясняется степень четности $s$ числа $ N - 1 = 2^s\cdot t $, где $ t $ - нечетное.

Следующее - необходимо проверить первое число $a=2$ на выполнение сравнения
$ 2^t\equiv 1\pmod N $.
Если сравнение выполняется, то переходят к следующему $a=3$
(предварительно проверив делимость $N$ на $a$).
В противном случае (т.е. сравнение не выполняется) далее проверяют
$ a^{2^{1}\cdot t}\equiv (-1)\pmod N $, если это сравнение выполняется, то переходят к следующему $a$,
если не выполняется, то проверяют выполнение следующего сравнения
$ a^{2^{2}\cdot t}\equiv (-1)\pmod N $
и так до
$ a^{2^{s}\cdot t}\equiv (-1)\pmod N $.
Если и последнее сравнение не выполняется, то число объявляется "составным".
Согласно алгоритма Миллера, если число прошло проверку при $a$ от 2 до $ 2(\ln N)^2 $, то в случае выполнения обобщенной гипотезы Римана можно сделать вывод - "число простое".

Например, $N = 2465 $;
$2465-1=2^5\cdot77$, следовательно,
$ t = 77 $; $ s = 5 $.
Принимаем $a=2$.
$ 2^{77}\equiv 1902\pmod {2465} $,
следовательно, проверяем:
$ 2^{2^{1}\cdot 77}=2^{154}\equiv 1449\pmod {2465} $
$ 2^{2^{2}\cdot 77}=2^{308}\equiv 1886\pmod {2465} $
$ 2^{2^{3}\cdot 77}=2^{616}\equiv 1\pmod {2465} $
$ 2^{2^{4}\cdot 77}=2^{1232}\equiv 1\pmod {2465} $
$ 2^{2^{5}\cdot 77}=2^{2464}\equiv 1\pmod {2465} $,
делаем вывод: число $2465$ - составное.

Добавлено спустя 27 минут 35 секунд:

Если мое представление о тесте верное, то $ k_{max} = s $ - это степень четности выражения $ (N - 1) $ и от $ \log_2 N $ не зависит.

Добавлено спустя 43 минуты 17 секунд:

Хотя, коль скоро речь идет о максимальном значении $k$, то оно от логарифма зависит.
Я отдаленно понял, о чем речь. Спасибо.

[Skipper]

Кстати, у Василенко написано, что "для некоторого k", а не "для всех k". Поэтому, наверное, это k не "пробегает", а как-то однозначно определяется. Только вот как именно оно определяется, Василенко почему-то не пишет. А то что оно <= какого-то "ню" (греч.) ни о чем не говорит. Поэтому до сих пор этот пункт полностью не понятен.

[maxal]

Skipper
$k$ определяется перебором в указанном интервале (от верхнего предела к нижнему). Поэтому я и сказал, что оно пробегает значения из этого интервала.

[Батороев]

maxal писал(а):

Skipper
$k$ определяется перебором в указанном интервале (от верхнего предела к нижнему). Поэтому я и сказал, что оно пробегает значения из этого интервала.

Что-то больно сурово получается.
Перебирать $k$ от верхнего предела к нижнему - это извлекать корень из предыдущего выражения, а если перебирать снизу вверх - всего лишь возводить в квадрат остатки этого выражения.
Например, в моем примере проверки числа $2465$:
$ 2^{308} \equiv 1886 \pmod {2465} $
$ 2^{616}\equiv 1886^2\pmod {2465}\equiv 1\pmod{2465} $.

[maxal]

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

Перебирать $k$ от верхнего предела к нижнему - это извлекать корень из предыдущего выражения, а если перебирать снизу вверх - всего лишь возводить в квадрат остатки этого выражения.

С точностью до наоборот. Напомню: там речь идет о выражении $a^{(n-1)/2^k}$ переход от $k$ к $k-1$ осуществляется именно что возведением в квадрат:

$$a^{(n-1)/2^{k-1}} \equiv \left(a^{(n-1)/2^k}\right)^2\pmod{n}.$$

[Батороев]

Теперь со "множеством $k$" разобрался .
Спасибо.

[Батороев]

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

Можно ли составить выражение по ограничению величины наименьшего делителя числа Кармайкла в зависимости от величины самого числа, т.е. $ p_{min} \leq f(K) $, где $K $ - число Кармайкла?
На мой взгляд, проверяя числа на простоту по тестам, подобным тесту Миллера, мы тем самым достоверно можем определить простоту любого числа, кроме чисел Кармайкла.
Если это так, то для ОБЪЕКТИВНОЙ проверки необходимо проверить числа до $P_{min}$, что значительно меньше, чем $ \sqrt N $.

По ходу просмотра соседней темы возник вопрос:
Будет ли достоверным следующий двухэтапный поиск простых чисел:
1. Проверка чисел до $N$, аналогичная Решету Эратосфена, но только с использованием простых, не превышающих $\sqrt[4]{2N}$.
2. Числа, прошедшие проверку по п.1, подвергаются дополнительной однораундовой проверке ($r=1$), аналогичной тесту Миллера (Миллера-Рабина). При проверке используется один свидетель простоты $a=2$.

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

-- Вт сен 01, 2009 14:42:23 --

Сам мозгами пораскинул и получается, что на п. 2 дополнительно приходится много составных чисел.
Так что, данная проверка (с перестановкой пунктов), по-видимому, годится больше для проверки какого-нибудь конкретного числа, т.е.:
провести 1 раунд проверки тестом Миллера и в случае положительного результата проверить на делимость простых чисел до $\sqrt[4]{2N}$. Как мне видится, должно получиться достоверно.

[Батороев]

ha в сообщении #172344 писал(а):

Число $K=(6n+1)(12n+1)(18n+1)$ является числом Кармайкла, если все сомножители - простые. Отсюда видно, что кубическую оценку не улучшить. Ваши рассуждения верны только при выполнении (1). Но вообще-то чем больше отношение, тем больше может быть наименьший простой делитель.

ha
Вы оказались правы: кубическую оценку не улучшить.
Нашел контр-примеры своей оценке ($\sqrt [4] {2N} $):
252601 (41), 2508013 (53), 3828001 (101), 851703301 (179).