RSA не всё
Mar. 4th, 2021 09:47 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
beldmitОпровержение RSA, кажется, опровергают. В каком-то месте определитель матрицы подсчитан неправильно, и вместо квадрата там должен быть факториал. Из-за этого количество операций соответственно возрастает.
https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601
https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur/88601#88601
no subject
Date: 2021-03-04 10:28 am (UTC)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 и пришел к выводу, что в реальности метод не будет существенно быстрее имеющихся.