Загадки математики

[Demurg2000]

Напишите пожалйста в этот раздел какие нибудь интересные вопросы математики на которые пока не найдены ответы и теоремы которые не доказаны

[Sasha2]

Да, пожалуйста. Есть ли предел отношения всех простых чисел, заканчивающихся на 1 к произведению всех простых чисел заканчивающихся на 3. И если есть то какой?

То же самое для всех остальных пар, ну в смысле заканчивающихся на 1, 3, 7 и 9

[Brukvalub]

Одной из самых актуальных на настоящий момент является проблема существования алгоритмов, время выполнения которых полиномиально зависит от "объема исходных данных", для алгоритмически разрешимых задач, которые в настоящее время не имеют таких алгоритмов (то есть время выполнения общеизвестных для них алгоритмов растет существенно быстрее полинома). Эту проблему обычно записывают символами $P \ne NP$. Если для какой-нибудь из таких задач удастся доказать ее алгоритмическую неразрешимость полиномиальным алгоритмом, то многие криптографы проспят следующую ночь спокойным младенческим сном , и будут так спать и дальше (пока не построят реально работающий квантовый компьютер).

[Руст]

Алгоритм Шора для квантового компьютера ломает шифры, основанные на факторизации. Но есть задачи, для которых и квантовый компьютер бессилен.

[worm2]

Последовательность Коллатца для натурального числа N определяется следующим образом:

$a_1 = N$
если $a_n$ чётно, то $a_{n+1}=a_n/2$
если $a_n$ нечётно, то $a_{n+1}= 3 a_n + 1$.

Пример последовательности Коллатца для N=7:
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

Доказать, что для любого натурального числа N в его последовательности Коллатца рано или поздно встретится единица
(или опровергнуть, т.е. доказать существование такого N, что в его последовательности Коллатца никогда не встретится 1).

Источник (на англ. языке) с массой подробностей: http://mathworld.wolfram.com/CollatzProblem.html

[ИСН]

В конце концов, есть же http://mathworld.wolfram.com/UnsolvedProblems.html
так стоит ли переписывать.

[незваный гость]

Вы уверены, что количество нерешенных проблем сводится к 16? Если нет, то по принципу Дирихле существуют проблемы, не вошедшие в список Вейсштейна.

Из списка, действительно, переписывать неинтересно. Но можно добавить свои.

[Capella]

Нужно различать между
а) задачи, которые ещё не доказаны
б) задачи, в которых доказано не существование решения

[Brukvalub]

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

Алгоритм Шора для квантового компьютера ломает шифры, основанные на факторизации. Но есть задачи, для которых и квантовый компьютер бессилен.

Но нет задач, для которых доказана их полиномиальная по времени неразрешимость, так что пока и без квантового компъютера криптографам не гарантирован крепкий сон.

[Otez-osnovatel]

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

[Котофеич]

Otez-osnovatel писал(а):

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

Ну ясное дело, математика не ведает, а слесаря ведают

[Руст]

Brukvalub писал(а):

Но нет задач, для которых доказана их полиномиальная по времени неразрешимость, так что пока и без квантового компъютера криптографам не гарантирован крепкий сон.

Это не имеет особого значения. Пусть все полиномиально проверяемые задачи полиномиально решаемы (P=NP). Допустим, факторизовать можно пропорционально десятой степени от числа битов (гарантированная проверка на простоту, пока пропорционально степени двенадцатой + епсилон). Когда шифр имеет 1000 битов, этому шифру ничего не грозит (на шифровку тратится линейна зависящая от количества битов операций).

[незваный гость]

Решето Эратосфена? Медлено, но верно!

maxal писал(а):

Проверку на простоту можно осуществлять алгоритмом Миллера-Рабина, готовая реализация на Pascal есть тут (вопрос 2.3.3.1).

Эффективнее, но заметно сложнее!

[AVARY]

Цитата:

...то многие криптографы проспят следующую ночь спокойным младенческим сном , и будут так спать и дальше (пока не построят реально работающий квантовый компьютер)

Квантовый компьютер не решит проблему, по крайней мере факторизации, так как вместе с ним придут намного более длинные ключи. Использование высокой производительности это эволюционный путь. Необходимо найти революционный.

[Macavity]

AVARY писал(а):

Цитата:

...то многие криптографы проспят следующую ночь спокойным младенческим сном , и будут так спать и дальше (пока не построят реально работающий квантовый компьютер)

Квантовый компьютер не решит проблему, по крайней мере факторизации, так как вместе с ним придут намного более длинные ключи. Использование высокой производительности это эволюционный путь. Необходимо найти революционный.

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

Тот факт, что скорость факторизации увеличится заключается в том, что скорость факторизации увеличится настолько значительно (то есть там порядок изменений от десятко-сотен лет к секундо-минутам), что уже сам процесс шифрации на более длинных ключах и сама генерация столь длинных ключей станет настолько медленным, что алгоритмы, построенные по такому принципу, выйдут из употребления. Помимо этого, идеология квантового компьютера создает принципиально новый способ шифрации-дешифрации и аутентификации сообщений. Здесь вопрос именно в создании настоящего квантового компьютера достаточной мощности, существует ряд именно квантовых проблем реализации.

Криптография, мне кажется, с точки зрения рассматриваемой темы интересна тем, что основывается в ряде случаев на недоказанных в настоящее время гипотезах (например, отсутствие хорошего алгоритма факторизации). Другой пример относится к кодам Диффи-Хеллмана (система обмена ключами), которая основывается, на недоказанном в настоящее время (насколько мне известно) предположении Диффи-Хелмана:

Цитата:

Сложность вычисления g^{ab} по g^a и g^b чрезвычайно велика.

Где вычисления рассматриваются для некоторой конечной группы.

Кстати, когда-то на этом форуме видел задачу безопасного обмена задуманными числами, которая, вероятно, может быть решена системой Диффи-Хелмана, при условии истинности предположения Диффи-Хелмана.