Comments 35
Для разложения простых чисел быстрых алгоритмов не существует.
Наверное потому что простое число и нельзя разложить на сомножители за исключением 1 и самого числа?
И именно потому, что простые числа так устроены для них как раз подобный алгоритм существует.
Это кто-то пытался сказать «попроще», а получилось… как получилось.
Разлагать на множители нужно всё-таки составное число, являющееся произведением двух простых… и вот это уже быстро сделать не получается.
P.S. И как раз если бы быстро искать простые было бы нельзя RSA и не работал бы. Так что в результате упрощения фраза изменила свой смысл на, фактически, противоположную…
Это кто-то пытался сказать «попроще», а получилось… как получилось.
Разлагать на множители нужно всё-таки составное число, являющееся произведением двух простых… и вот это уже быстро сделать не получается.
P.S. И как раз если бы быстро искать простые было бы нельзя RSA и не работал бы. Так что в результате упрощения фраза изменила свой смысл на, фактически, противоположную…
>>что по мере удлинения многочленов с коэффициентами 0 и 1 вероятность того, что их вообще можно будет разложить, становится все ниже
Странно…
— Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)
— И, с другой стороны, многочлен полученный из ключа RSA гарантированно раскладывается на ровно 2 множителя т.к. рассуждение описанное в (шаг четвертый) работает в обе стороны
К сожалению, препринта нет…
Странно…
— Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)
— И, с другой стороны, многочлен полученный из ключа RSA гарантированно раскладывается на ровно 2 множителя т.к. рассуждение описанное в (шаг четвертый) работает в обе стороны
К сожалению, препринта нет…
Есть, просто далековато лежит, т.к. это перевод простой поясняющей журалисткой статьи к журналисткой статьи более сложного уровня, написанной по мотивам исходной научной статьи математиков.
Первоисточник всей этой цепочки тут: Irreducibility of random polynomials of large degree
Первоисточник всей этой цепочки тут: Irreducibility of random polynomials of large degree
Спасибо!
В очередной раз журналисты такие журналисты…
" Suppose that the Riemann hypothesis holds… "
т.е. вероятно (но исходное предположение не доказано), что многочлен с коэффициентами 0 и 1, полученный из открытого ключа RSA, статистически неразложим если рассматривать его как случайный многочлен (допустимость чего не доказывалось — или я этого не вижу в статье).
В очередной раз журналисты такие журналисты…
" Suppose that the Riemann hypothesis holds… "
т.е. вероятно (но исходное предположение не доказано), что многочлен с коэффициентами 0 и 1, полученный из открытого ключа RSA, статистически неразложим если рассматривать его как случайный многочлен (допустимость чего не доказывалось — или я этого не вижу в статье).
Как минимум половина таких многочленов (любой длины) оканчивается на 0 и поэтому раскладывается (с ожидаемым корнем x=2)
У всех чисел, полученных перемножением двух больших простых чисел, не будет множителя 2. Значит все многочлены, полученные из ключей RSA будут оканчиваться на 1.
Между такими многочленами и числами взаимно-однозначное соответствие, т.е. в статье якобы есть утверждение, что доля простых чисел возрастает при повышении разрядности чисел.
Но она убывает.
Между многочленами и числами — взаимно-однозначное соответствие. А вот между неприводимыми многочленами и простыми числами — нет. Неприводимый многочлен может соответствовать составному числу.
> Неприводимый многочлен может соответствовать составному числу.
Очевидно, что нет.
Очевидно, что нет.
15
(x^2+1)(x+1)
Многочлен для 15 приводим, это даже в статье показано.
Прошу пардона, я допустил опечатку в 50% символов своего сообщения.
25.
25.
(x^2+1)(x^2+1)
25 — это x^4 + x^3 + 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 надо будет избавляться.
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 надо будет избавляться.
Чему будет соответствовать произведение многочленов, соответствующих простым множителям данного составного числа?
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Так как раз и ищут многочлен с коэффициентами 1 и 0, т.е. задача сводится к поиску системы счисления в котором число будет состоять только из 1 и 0. Вырожденный и очевидный вариант 2 не подходит из-за слишком большой длины многочлена.
Наверное предполагалось, что многочлен с единичными коефициентами разложить проще. 1 на 1 всегда поделится.
Если я правильно понимаю, то стоит оговариваться, что это не означает что решения нет, просто именно таким способом решить не получится.
Чтобы никто не подумал, что это окончательное доказательство надёжности алгоритма.
Чтобы никто не подумал, что это окончательное доказательство надёжности алгоритма.
На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…
> На самом деле полином любой степени можно разложить на одночлены с в общем случае комплексными коэффициентами. То есть и разложение любого числа возможно — на комплексные множители. И вопрос в том, можно ли затем эти комплексные множители так свернуть перемножением части из них, чтобы получить целые множители…
Конечно, можно. Если коэффициенты вещественны, то все комплексные корни будут попарно сопряжены. Проблема в том, что быстрых алгоритмов нахождения комплексных корней тоже мало. Когда вы говорите о нахождении комплексных корней многочлена с целыми коэффициентами, причем (очевидно из условий задачи) корни многочлена должны быть целые (и мнимая, и вещественная часть), то фактически вы пытаетесь решить диофантово уравнение с двумя переменными. А для них расстояние от корня до нуля может иметь экспоненциальную зависимость относительно степени многочлена.
Конечно, можно. Если коэффициенты вещественны, то все комплексные корни будут попарно сопряжены. Проблема в том, что быстрых алгоритмов нахождения комплексных корней тоже мало. Когда вы говорите о нахождении комплексных корней многочлена с целыми коэффициентами, причем (очевидно из условий задачи) корни многочлена должны быть целые (и мнимая, и вещественная часть), то фактически вы пытаетесь решить диофантово уравнение с двумя переменными. А для них расстояние от корня до нуля может иметь экспоненциальную зависимость относительно степени многочлена.
И если зашифрованное сообщение предназначалось не вам, и у вас нет ключа для его расшифровки, то попытки найти этот ключ могут занять добрую тысячу лет.
Условия вводят в заблуждение — будто для расшифровывания достаточно выполнения одного из двух условий: либо быть получателем либо иметь ключ.
придумывает сообщение и выполняет над ним определенные математические операции, включающие в себя умножение на очень большое число
Не умножение, а возведение в степень по модулю очень большого числа.
Единственный способ расшифровать сообщение — найти простые множители полученного результата
Не результата, а модуля, который известен из открытого ключа.
Sign up to leave a comment.
Математики доказали, что многочлены не помогут взломать RSA