RSA не всё

[beldmit]

Опровержение RSA, кажется, опровергают. В каком-то месте определитель матрицы подсчитан неправильно, и вместо квадрата там должен быть факториал. Из-за этого количество операций соответственно возрастает.

https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601

Comments

[vitus_wagner]

По-моему фигню он там пишет. С какой стати у детерминанта факториальная сложность? Даже банальный метод Гаусса для детерминанта дает O(n³).

[beldmit]

Там не сложность, а оценка.

[elglin]

Это если элементы матрицы имеют длину О(1).
А там что-то есть про перестановки [1, n] -> [1, n], которых как бы n!
Я вот не готов сейчас потратить много времени на то, чтобы въезжать в это совсем точно, но фокус, как мне кажется, в том, что n входит не только в число операций подсчета определителя, а еще и в сложность каждой операции. Как писали в другом комменте, если у тебя O(1) операций над числами длины O(n!), то результирующая сложность-то все равно O(n!)

[vitus_wagner]

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

В общем, как-то трудно поверить что Шнорр мог ТАК лажануться. В то что лажанулся комментатор на стэкэксчедже верится больше.

[elglin]

А вот лажанулся же, если говорить про оценку определителя.
det R(n,f) = det diag(N*f(1), N*f(2)... N*f(n), N*lnN) = N^(n+1) * lnN * (f(1)*...*f(n)) = N^(n+1) * lnN * n!
А в статье вместо n! идет n(n+1)/2 , то есть (f(1) + ... + f(n)). Дальше уже вопрос, насколько это ломает итоговую оценку сложности, на stackexchange указывают, что именно там дальше подламывается, но не дают полную цепочку до итоговой оценки сложности.
Но ошибка подсчета определителя налицо. Конец второй страницы препринта.
Ну и уже кто-то проверил: https://github.com/lducas/SchnorrGate и пришел к выводу, что в реальности метод не будет существенно быстрее имеющихся.