Доказательство гипотезы Римана

[Nilenbert]

Ну, например число 33?

[Мат]

Вернее это конечно я упростил, также необходимо знать, содержит ли оно хоть один простой множитель вида $4p-1$.
Но и данную задачу можно решить, если постараться.

[Руст]

Как я понял, доказательство Julio Alcantara-Bode так же чушь. На самом деле там не используется ничего от операторов. Просто вычисляется минимум нормы $g_s=2Re(\frac 12 +i\gamma_s)sx^s$ в $L_2[0,1]$ двумя способами, где $s+1$ корень дзэта функции. Совпадение получилось только при $\sigma =-\frac 12$. На самом деле это из-за того, что в одном (по крайней мере в одном) имеется ошибка. Например мои выкладки для формулы (1) не совпали с выкладками автора. Выкладки громоздкие, поэтому не удивителен несовпадение результатов. Понятно, что тут не используется абсолютно ничего из свойств дзета функции а только арифметические выкладки. Поэтому эта работа не имеет отношения к доказательству ГР.

[shwedka]

A proof of the Riemann Hypothesis
Authors: Julio Alcantara-Bode
Comments: This paper has been withdrawn

[yk2ru]

Т. е. работа была отозвана и гипотезу Римана автор не доказал по собственному мнению?

[shwedka]

yk2ru
именно так

[VAL]

Мат писал(а):

Вернее это конечно я упростил, также необходимо знать, содержит ли оно хоть один простой множитель вида $4p-1$.
Но и данную задачу можно решить, если постараться.

Постарайтесь, пожалуйста!
Например, для чисел $3196589641537114858784046346833804236339623623421328936292001692542262809342224524600927968659000379132293322331956153645902634861777$ и $3196589641537114858784046346833804236339623623421328917162218834021001827967417629832887409311448585689747035165146457230075434099553$

[VAL]

vlad239 писал(а):

Мат писал(а):

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

Насколько я понимаю, новый алгоритм теста на простоту (который индусы придумали в 2003 году) имеет полиномиальную сложность (от количества цифр, разумеется, что-то в духе $O(\log^7 n)$) если верна гипотеза Римана и какой-то значительно худший результат если неверна.

Кажется, там получается полином 12-й степени.

PS: "Уж полночь близится, а Германа все нет"

[Someone]

http://primes.utm.edu/prove/prove4_3.html

Цитата:

Agrawal, Kayal and Saxena managed to reformulate this into the following algorithm which they proved would run in at most $O((\log n)^{12}f(\log\log n))$ time where $f$ is a polynomial.
...
AKS also showed that if Sophie Germain primes have the expected distribution [HL23] (and they certainly should!), then the exponent $12$ in the time estimate can be reduced to $6$

[Мат]

VAL
К сожалению не хочется искать решение задач "большой кровью", с помощью MathCada просмотрел первые 1000 простых множителей каждого из чисел. Ни на один ни первое, ни второе не делится. Попытался средствами MathCada сделать автоматический обработчик, который бы перебирал все возможные делители, что позволило бы дойти до миллиона, однако там ограничение на точность 16 знаков. Чтобы идти в глубь дальше, необходимо писать специализированный обработчик, который будет выполнять операции деления над числами до 137 знаков и затем методом перебора искать делители $4p-1$. Не хотелось бы решать задачу большой ценой, если конечно это имеет смысл.

[VAL]

Мат писал(а):

VAL
К сожалению не хочется искать решение задач "большой кровью", с помощью MathCada просмотрел первые 1000 простых множителей каждого из чисел. Ни на один ни первое, ни второе не делится. Попытался средствами MathCada сделать автоматический обработчик, который бы перебирал все возможные делители, что позволило бы дойти до миллиона, однако там ограничение на точность 16 знаков. Чтобы идти в глубь дальше, необходимо писать специализированный обработчик, который будет выполнять операции деления над числами до 137 знаков и затем методом перебора искать делители $4p-1$. Не хотелось бы решать задачу большой ценой, если конечно это имеет смысл.

Во-первых, необходимости писать специализированный обработчик нет. Их уже написано предостаточно.
А во-вторых, даже если Вы возьмете что-нибудь получше MathCad'а, это вряд ли приведет Вас к успеху.
Пример был приведен как опровержение Вашего опрометчивого заявления:

Цитата:

Я могу пояснить. Для того, чтобы определить является ли заданное число суммой двух квадратов (сколь угодно большое), потребуется лишь время пропорциональное числу его разрядов: для сдвига в бинарной системе на два разряда вправо и выяснении каков будет остаток $(1,2$ или $3)$. Что никак по времени не может сравниться ни с каким тестом простоты.

Действительно, время проверки числа на простоту никак не может сравниться со временем проверки его представимости в виде суммы двух квадратов.
Только трудность этих двух задач отличается совсем в другую сторону.
Например, с проверкой приведенных мной чисел на простоту Maple справляется менее чем за одну тысячную секунды.
А на проверку представимости их суммой двух квадратов времени уйдет побольше. Не берусь оценить сколько именно, но, думаю , в качестве грубой оценки вполне подойдет "столько не живут".
Это если считать Maple'ом или чем-то аналогичным. Не исключаю, что какая-нибудь специальная программа, предназначенная для тестирования криптостойкости RSA, запущенная на суперкомпьютере, упрвится всего за месяц. Но не уверен.

[Руст]

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

[VAL]

Руст писал(а):

Проверка представимости в виде суммы квадратов требует факторизации.

Ну, вообще говоря, не требует. Но это не спасает

Цитата:

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

Именно об этом я и толкую.

[Мат]

VAL писал(а):

А во-вторых, даже если Вы возьмете что-нибудь получше MathCad'а, это вряд ли приведет Вас к успеху.
Пример был приведен как опровержение Вашего опрометчивого заявления:

Заявление опрометчиво лишь наполовину. т.к. я равно могу вам привести два полупростых числа, тест которых на простоту также на самом мощном суперкомпьютере займет миллиарды лет, при этом, если они будут делиться на три, то тест на сумму квадратов выполнится моментально.
$3191435500578210244787198398894956245108075194333929494784205674910446715117586461538988820216718955484198317921$

[Руст]

если делится на три, то проверка на простоту так же моментально выполняется. Если число вида $N=3\mod 4$ действительно не проверяя на простоту убеждаемся, что хотя бы одно простое число $p=3\mod 4$ входит в разложение $N$ в нечётной степени, тем самым не представимо в виде суммы двух квадратов. Я готов допустит, что существует алгоритм проверки вхождения в разложении $N$ простого числа вида $p=3\mod 4$ в нечётной степени имеется алгоритм (использующий Гауссовы числа) такой же сложности (эта задача по сути есть ваша задача), что и проверка на простоту числа $N$. Только какое это имеет отношение к обсуждаемой теме ГР.