Прогресс в теории простых чисел

[B3LYP]

Если я нигде не путаю (прошу поправить если что), современная криптография основывается на том, что перемножить числа проще, чем разложить их на простые множители; теоретически вторую задачу можно решить, если развить теорию простых чисел. Также вторую задачу можно решить на квантовом компьютере, тут работает квантовое превосходство. Хочу спросить, как вы оцениваете шансы, что будут сделаны фундаментальные открытия в математике в области простых чисел, и даже классический компьютер сможет решать такую задачу?
Посмотрел видео “Почему простые числа образуют спирали”:

https://youtu.be/DxntHp7-wbg

Я смотрел на английском и очень много не понимал. И мне вспоминается, что в книге Мартина Гарднера тоже было про спирали, но в другом смысле: если числами по спирали заполнять клеточки дискретной шахматной доски, то появится некий узор, по-моему линии. Всё так? Этому факту ещё не нашли объяснения?

[iifat]

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

[wrest]

B3LYP в сообщении #1623795 писал(а):

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

Как исчезающе малые.

[B3LYP]

Я вот подумал: а как много может дать использование позиционной системы счисления? Речь о том, что если мы пишем число например в десятичной системе, то по последней цифре можно сразу много сказать - если это 0, 2, 4, 5, 6, 8, то число точно не простое. Может, если использовать кроме десятичной системы также другие, можно добиться ещё большего?

[wrest]

B3LYP в сообщении #1623918 писал(а):

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

В компьютерах используется двоичная, в основном.
Система счисления тут не при чем.
Вернее как... что то ускоряется, да. Типа умножения и деления на степени двойки становится проще. Но суть не меняется, т.к. ускорять надо на много порядков а не во много раз.

[Dmitriy40]

B3LYP в сообщении #1623918 писал(а):

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

Можно, и это даже широко используется в программах решета. Например в системе с основанием 30 лишь 8 младших цифр допустимы для простых чисел (больших 30). В системе с основанием 30030 допустимых младших цифр 5760. В системе с основанием $p_1^a p_2^b p_3^c p_4^d \ldots$, где $p_i$ простые числа, младших допустимых цифр будет $a(p_1-1)b(p_2-1)c(p_3-1)d(p_4-1)\ldots$. Конечно неединичные коэффициенты $a,b,c,d,\ldots$ никакого выигрыша не дают, привёл для общности.
В программах решета это используется чтобы уменьшить количество проходов по вычёркиванию малых простых из массива правильной его инициализацией с уже вычеркнутыми малыми простыми. И выигрыш от каждого следующего простого $\frac{p-1}{p}$ быстро уменьшается и обычно ограничиваются первым (полу)десятком простых.
А в программах не решета это можно использовать для уменьшения количества делений - если делить не на каждое простое, а на произведения их пары-тройки (или больше) и проверять остаток по списку запрещённых для этих пар-троек. Деление уж очень медленная операция и замена её даже на десяток других всё равно выгодна. Правда практического смысла это не имеет: пробные деления занимают обычно ничтожно малую часть времени, а всё остальное тратится на возведение в степень по модулю (или другие операции).

-- 26.12.2023, 19:39 --

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

-- 26.12.2023, 19:51 --

И опять же, практического смысла в этом снова слишком мало: для чисел около 3e46 реально простым окажется лишь каждое $\ln(3\cdot10^{46})\approx 84$-е, а кандидатом в простые будет каждое 8.713-е. И думаю проще будет банально поделить кандидата на эти 30 простых чем заморачиваться с вычислением китайской теоремы об остатках. Хотя для первых 6-8 простых (праймориалы примерно 3e4-9.7e6) можно и взять с правильными остатками.

[vicvolf]

B3LYP в сообщении #1623795 писал(а):

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

Здесь два вопроса. Один из теории простых чисел (ТПП), другой из теория алгоритмов, которые конечно связаны. Dmitriy40 дал достаточно подробный ответ на вопрос из теории алгоритмов.
В отношении ответа на вопрос по ТПП можно сказать, что действительно ТПП содержит наверно наибольшее число гипотез, чем другие разделы теории чисел. В свое время значительный прогресс ТПП (доказательство закона простых чисел) было связано с переходом от элементарных методов к аналитическим методам ТФКП.
Вот и сейчас проблемы с доказательством гипотезы Римана и других, я думаю, также связаны с подходом. Необходима смена подхода к доказательству этих гипотез. Обратите внимание, что еще в начале прошлого века Харди и Литтлвуд (с помощью вероятностных методов) определили достаточно точно количество простых кортежей (в частности простых близнецов) на конечном интервале натурального ряда, хотя до сих пор не доказана гипотеза о бесконечности количества простых близнецов.

[mathpath]

В конце 19-го века Чебышев в своей книге привел алгоритм для разложения 7-значного числа, и по тем временам это было событием
На текущий момент, по прошествии более 100 лет, компьютерные программы в состоянии разложить практически любое 100-значное число
И при этом используется общий метод решета числового поля (gnfs), который мало чем отличается от того алгоритма, который описал еще Чебышев
Я недавно с помощью программы cado-nfs попробовал разложить RSA260, в котором 260 знаков, но чуда не случилось
Мощность компьютеров будет расти, и вместе с ними будет происходить медленное наступление на факторизацию больших чисел
Теория простых чисел последние лет 100 практически топчется на месте
И не только - теоретическая физика тоже уже давненько топчется на месте
И я думаю, что пока в мире будет бардак, который наблюдается сейчас, до теории чисел вряд ли в ближайшее время кому-то будет дело

[Dmitriy40]

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

Но за криптографию переживать не стоит: есть много других "однонаправленых" (простых в одну сторону и сверхсложных в обратную) операций кроме разложения на множители, и они уже тоже применяются. Причём вроде бы для некоторых существуют даже теоретические доказательства отсутствия быстрых алгоритмов, в том числе и квантовых, так что и квантовые компы не всесильны. Впрочем про такие доказательства могу и ошибаться.

[B3LYP]

Пользуясь случаем, хочу поспрашивать, как вообще работает современная криптография, какие у неё принципы.
Раньше письмо отправляли в запечатанном конверте; если печать вскрыта, значит письмо кто-то ещё прочитал. Аналогом этому в современной криптография является только квантовая криптография?
С другой стороны, когда сообщения передавали по радио, там в принципе невозможно было утаить сам сигнал, можно было только его зашифровать. Немцы пытались (Энигма) и у них не вышло. Насколько я понимаю, общий принцип шифрования должен быть такой, чтобы как можно сильнее сжимать сообщение, например лучше передавать его не по буквам, а по словам. Неясно как это пересекается с математикой с которой я начал.
Эти вопросы имеют большое практическое значение, например мне хочется знать, насколько сейчас возможно перехватывать смс-ки.

[mihaild]

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

Причём вроде бы для некоторых существуют даже теоретические доказательства отсутствия быстрых алгоритмов, в том числе и квантовых, так что и квантовые компы не всесильны

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

B3LYP в сообщении #1624109 писал(а):

С другой стороны, когда сообщения передавали по радио, там в принципе невозможно было утаить сам сигнал, можно было только его зашифровать

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

B3LYP в сообщении #1624109 писал(а):

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

Нет такого принципа.
Фундаментальный принцип - при любом распределении на входе и случайном ключе, на выходе должно быть равномерное распределение. Прямо такое на практике не реализуемо полезным образом, но есть разные приближения.

[EUgeneUS]

mihaild в сообщении #1624114 писал(а):

B3LYP в сообщении #1624109

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

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

[B3LYP]

EUgeneUS в сообщении #1624137 писал(а):

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

По-моему то что я написал - вполне самоочевидная истина, не думал что кто-то тут будет с этим спорить. Это как факт, что файл из полностью случайных байт невозможно сжать.
Предположим, у нас есть текст на русском языке, который нам надо зашифровать. Мы можем перевести все буквы текста в другие буквы по любому алгоритму; но дешифратор всё равно сможет наш текст расшифровать, зная словарь русского языка. Это похоже на расшифровку древних языков - историки давно справились с этой задачей. Если же мы каждое слово в тексте закодируем числом, характеризующим номер этого слова в словаре - возможностей у дешифратора будет намного меньше.

[mihaild]

EUgeneUS в сообщении #1624137 писал(а):

Но не с целью именно сжать сообщение, а с целью получить во входном (для шифрования) сообщении распределение, близкое к равномерному.

А каким алгоритмам шифрования это важно?

B3LYP в сообщении #1624183 писал(а):

Мы можем перевести все буквы текста в другие буквы по любому алгоритму; но дешифратор всё равно сможет наш текст расшифровать, зная словарь русского языка

Ну вот допустим у нас шифр - одноразовый блокнот по модулю 34 (буквы и пробел). Он "переводит буквы в буквы"?

[warlock66613]

B3LYP в сообщении #1624183 писал(а):

Мы можем перевести все буквы текста в другие буквы по любому алгоритму; но дешифратор всё равно сможет наш текст расшифровать

Не сможет. Потому что "перевод" зависит от ключа, а ключ неизвестен. Возьмите например базовый и простейший метод шифрования под названием "одноразовый блокнот", сделайте "побуквенное" шифрование и попробуйте как-то обратить шифрование без знания ключа. Никакого сжатия при этом не происходит: каждая буква исходного текста превращается в ровно одну букву шифротекста.