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

[maxal]

Батороев
Достоверность детерминированного теста Миллера зависит от обощённой гипотезы Римана, и числа Кармайкла тут не при чем.
И для вероятностного теста Миллера-Рабина числа Кармайкла (в том числе и вида $N=4n+1$) ничем не отличаются от остальных - для них также существует не менее $\varphi(N)/4$ свидетелей простоты.

[Батороев]

При условии выполнения обобщенной гипотезы Римана по тесту Миллера необходимо проверить числа $a$ от $2$ до $ 70\ln (N)^2 $.
Но коль скоро гипотеза Римана не доказана, то я предлагаю ( ) проверять $a$ от $2$ до $ p_{1max} $, где $p_{1max} $ - максимально допустимый меньший делитель числа Кармайкла.
То, что "противостоять" тесту Миллера (а также тесту Миллера-Рабина) могут лишь числа Кармайкла, как мне кажется, вполне доказуемо.

[maxal]

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

То, что "противостоять" тесту Миллера (а также тесту Миллера-Рабина) могут лишь числа Кармайкла, как мне кажется, вполне доказуемо.

Прежде чем доказывать, надо сформулировать четко, что такое "противостоять". С точки зрения свидетелей простоты, на которых основывается тест Миллера-Рабина, никакого "противостояния" тут нет.

[Батороев]

Сначала поясню, почему не подходит тест Миллера-Рабина.
К примеру, мы проверяем на простоту число $2701$.
Если по алгоритму Миллера-Рабина свидетель $a$ выбирается случайно, то не исключена вероятность того, что ГСЧ не выберет $ a = 16, 81, 1681, 1857, 1973 $. Если такая вероятность существует, то и достоверно о свойствах проверенного числа сказать ничего невозможно.

Если же мы число проверяем при помощи теста Миллера, то в качестве свидетелей простоты принимаются последовательные числа $a =2,3, 4,...70\ln(N)^2 $.
Допустим, какое-то число мы проверили тестом Миллера. Получен ответ: "число вероятно простое".
Можем ли мы в этом случае достоверно сказать, что проверенное число является либо простым, либо числом Кармайкла и никаким иным?
Вот это выделенное меня и интересует.
Если утверждение справедливо, тогда проверив число на делимость на числа от $2$ до $p_{1max}$ мы могли бы достоверно заявить, что число простое.
То, что $p_{1max}<\sqrt N $, надеюсь, очевидно.

[Skipper]

И все таки...
Может кто-нибудь подробно разжевать тест Миллера (детерминированный, доказывающий простоту числа если верна гипотеза Римана) ?

Я просто шокирован таким количеством противоречивых сведений! Здесь на форуме товарищ Батороев пишет, что нужно проверять до

70 ln (N ^ 2)
(^ - это возведение в степень)

а вот здесь
http://nature.web.ru/db/msg.html?mid=11 ... ode32.html
пишут что проверять нужно до
70 (log N)^2

т.е. в квадрат возводится логарифм, а у товарища Батороева - в квадрат возводится N. В итоге это не одно и то же. Ну вот зачем, товарищ Батороев, вводить людей в заблуждение, если вы не уверены в том что пишете??? И еще. Во втором случае log ... Извольте спросить - ПО КАКОМУ ОСНОВАНИЮ логарифм?? В школе учили, что только для натуральных логарифмов ln - мы не указываем основание!

А вот здесь пишут,
http://math.nsc.ru/~bogopolski/Articles/SpezkNumber.pdf
вообще
2 (log N)^2

Т.е. вместо 70 уже двойка появилась, и непонятно опять по какому основанию log. Я уже спрашивал у математиков, одни говорят - если не написано основание, то считать нужно десятичный (по основанию 10), (хотя непонятно, почему именно десятка а не пятерка например), а другие говорят, что если написано log - то считать нужно по основанию 2.

Далее, я нашел уже 4-й вариант -
http://geo.web.ru/db/msg.html?mid=11612 ... de161.html
здесь написано
2 (ln N)^2

Это просто какой то ужас. Кто нибудь может разжевать мне тест Миллера (алгоритм) проверки на простоту?

[ewert]

Насчёт семидесяти не в курсе, а логарифм без основания в забугорной традиции -- это натуральный. Запись $\ln(N^2)$, если и впрямь проскочила -- то, разумеется, просто по рассеянности, поскольку она довольно бессмысленна.

[maxal]

У самого Миллера была константа 70 перед $(\ln N)^2$. Впоследствие в работе Bach в 1990 году эта константа была понижена до 2.
см. http://en.wikipedia.org/wiki/Miller-Rab ... f_the_test

А $\log$ - это просто американский вариант записи $\ln$ (если не оговорено какого другого основания). То есть $2(\log N)^2$ - это то же самое, что и $2(\ln N)^2.$

[Skipper]

в забугорной традиции может и натуральный, а я вижу log - в русскоязычных материалах, следовательно не могу быть уверенным, что это натуральный. Вот это
2 (log N)^2
я бы еще предположил, что
2 (ln N)^2
если бы не видел где-то документ в интернете, в котором было написано, что именно log по основанию 2. Жаль, не сохранил вовремя, и теперь не могу его найти! он как сквозь землю провалился

[maxal]

Skipper
По предварительной доворенности $\log$ может означать $\log_2$. Но если этого не оговорено заранее, то $\log$ - это то же самое, что и $\ln$.

[Дима Тишков]

Насколько я знаю, у информатиков $\log$ по умолчанию значит $\log_2$.

[maxal]

Дима Тишков писал(а):

Насколько я знаю, у информатиков $\log$ по умолчанию значит $\log_2$.

Это не совсем так. В асимптотической записи совершенно неважно по какому основания берется логарифм. Например, $O(\log_2 n)$ и $O(\ln n)$ - это одно и то же. Поэтому можно использовать просто $\log$ без указания какого-либо основания.

[Skipper]

Ну хорошо... Пусть будет
2 (ln N)^2

если пробовать читать дальше предложенные описания алгоритма Миллера - полный бред получается. Вот одно из них -

http://www.wl.unn.ru/lab/Portals/0/RSA_system.pdf

Красиво все сделано, претендует на истину во всей своей красе, алгоритм (тест) Миллера описан на 13-й странице. Шаг iii просто поражает воображение...

Выяснить, верно ли, что при некотором k,
1 <= k <= 2 в степени (n - 1)
... выпоняется то-то...

n - это большое число, скажем порядка 10 в 500 степени которое я хочу проверить на простоту. А 2 в степени такого n - просто ЧУДОВИЩНО большое число, еще больше. И что, все k перебирать до него? До самого n не переберешь.
Далее... Тут написано что a в степени (n - 1) / (2k - 1), а у Василенко

http://www.ict.edu.ru/ft/002416/book.pdf -

a в степени (n - 1) / 2k . Это там, где НОД проверяется.
Спрашивается, кому верить. Какая степень все таки - делить на (2k - 1), или на 2k ?

[maxal]

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

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

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

[Skipper]

Спасибо. Хоть что-то начинает проясняться... Хочу этот тест Миллера испытать на компьютере для многих больших простых. Если найдется хоть один пример, где он не работает (если сравнивать найденные простые с найденными по другим алгоритмам), то великая гипотеза Римана будет опровергнута. Хотя в это и не верится.

[Батороев]

Skipper писал(а):

И все таки...
Может кто-нибудь подробно разжевать тест Миллера (детерминированный, доказывающий простоту числа если верна гипотеза Римана) ?

Я просто шокирован таким количеством противоречивых сведений! Здесь на форуме товарищ Батороев пишет, что нужно проверять до

70 ln (N ^ 2)

Все претензии - к авторам статьи.