Как стать автором
Обновить

Комментарии 35

Для разложения простых чисел быстрых алгоритмов не существует.

Наверное потому что простое число и нельзя разложить на сомножители за исключением 1 и самого числа?
И именно потому, что простые числа так устроены для них как раз подобный алгоритм существует.

Это кто-то пытался сказать «попроще», а получилось… как получилось.

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

P.S. И как раз если бы быстро искать простые было бы нельзя RSA и не работал бы. Так что в результате упрощения фраза изменила свой смысл на, фактически, противоположную…
НЛО прилетело и опубликовало эту надпись здесь
Разлагать на множители нужно всё-таки составное число, являющееся произведением двух простых… и вот это уже быстро сделать не получается.

Почему двух? Или вы частный случай берете?
Потому что на этом случае основан шифр RSA.
>>что по мере удлинения многочленов с коэффициентами 0 и 1 вероятность того, что их вообще можно будет разложить, становится все ниже
Странно…
— Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)
— И, с другой стороны, многочлен полученный из ключа RSA гарантированно раскладывается на ровно 2 множителя т.к. рассуждение описанное в (шаг четвертый) работает в обе стороны
К сожалению, препринта нет…
Есть, просто далековато лежит, т.к. это перевод простой поясняющей журалисткой статьи к журналисткой статьи более сложного уровня, написанной по мотивам исходной научной статьи математиков.

Первоисточник всей этой цепочки тут: Irreducibility of random polynomials of large degree
Спасибо!
В очередной раз журналисты такие журналисты…
" Suppose that the Riemann hypothesis holds… "
т.е. вероятно (но исходное предположение не доказано), что многочлен с коэффициентами 0 и 1, полученный из открытого ключа RSA, статистически неразложим если рассматривать его как случайный многочлен (допустимость чего не доказывалось — или я этого не вижу в статье).
Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)

У всех чисел, полученных перемножением двух больших простых чисел, не будет множителя 2. Значит все многочлены, полученные из ключей RSA будут оканчиваться на 1.

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

Между многочленами и числами — взаимно-однозначное соответствие. А вот между неприводимыми многочленами и простыми числами — нет. Неприводимый многочлен может соответствовать составному числу.
> Неприводимый многочлен может соответствовать составному числу.

Очевидно, что нет.
15
(x^2+1)(x+1)
Многочлен для 15 приводим, это даже в статье показано.
Прошу пардона, я допустил опечатку в 50% символов своего сообщения.

25.
(x^2+1)(x^2+1)
Я почти правильно написал:

25 = 5 * 5 = (x^2+1)(x^2+1) [при x = 2] = x^4 + 2 x^2 + 1

но поскольку коэффициент 2 недопустим, то его надо заменить на x, и получаем

x^4 + x^3 + 1

этот многочлен, действительно неприводим над Z.

Sorry, затупил, забыл, что от коэффициентов неравных 0 и 1 надо будет избавляться.

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

Ничему. Оно вообще не будет многочленом нужного вида.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Я полагаю, за неуклюжее выражение очевидной мысли. Если что, я не минусовал.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь

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

Наверное предполагалось, что многочлен с единичными коефициентами разложить проще. 1 на 1 всегда поделится.
Если я правильно понимаю, то стоит оговариваться, что это не означает что решения нет, просто именно таким способом решить не получится.
Чтобы никто не подумал, что это окончательное доказательство надёжности алгоритма.
Это точно. Для постквантовой криптографии RSA всё равно не годится, потому что существует алгоритм Шора.
На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…
> На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…

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

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

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

Не умножение, а возведение в степень по модулю очень большого числа.
Единственный способ расшифровать сообщение — найти простые множители полученного результата

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