DK
так там не 256 бит
Size: a a a
2020 May 26
AR
Ага
DK
там больше
DK
там как RSA
AR
Там больше надо для той же секьюрити
DK
128 бит безопасности это 3000 бит RSA и дискретного логарифма, примерно
AP
Ух ты, т.е. умножение 256 битных чисел по модулю медленнее сложения точек на EC?
ну не совсем так, во первых 256 бит можно эмулировать и есть специфические платформы APU/sparc/risc/arm где оно работает куда быстрее.
AP
Интел в этом плане курит бамбук, да еще и замочили пару хороших 256bit math процов в процессе конкуренции. как раз эту тему сейчас копаю. мне нужна 256bit математика для расчетов.
AR
128 бит безопасности это 3000 бит RSA и дискретного логарифма, примерно
Про RSA понимаю (моё внутреннее ощущение почему так много битов - через плотность простых чисел среди целых, для записи k-го простого числа нужно битов гораздо больше чем в k, конечно не по этому, и рассуждение более сложное, но связь вроде есть), а вот про ДЛог - интересно почему. Догадываюсь что в случае модульной арифметики там тоже простые числа подкузьмили. Но покопаю, блин интересно
DK
Про RSA понимаю (моё внутреннее ощущение почему так много битов - через плотность простых чисел среди целых, для записи k-го простого числа нужно битов гораздо больше чем в k, конечно не по этому, и рассуждение более сложное, но связь вроде есть), а вот про ДЛог - интересно почему. Догадываюсь что в случае модульной арифметики там тоже простые числа подкузьмили. Но покопаю, блин интересно
битов нужно кстати столько же
DK
ну чуть чуть больше
AR
битов нужно кстати столько же
Вот как раз интереесно почему (будет моим домашним заданием)
DK
потому что плотность простых чисел это 1/ln n
AR
Так всё-таки в ДЛог тоже простые
DK
Длог и факторизация в поле Z_p имеют почти одинаковую субэкспоненциальную сложность, из за которой и нужно так много битов
DK
субэкспоненциальность потому что есть понятие гладкого числа, то есть такого у которого все множители небольшие.
DK
а в кривых такого понятия нет
AR
Спасибо! Пошел образовываться! -)
AR
Длог и факторизация в поле Z_p имеют почти одинаковую субэкспоненциальную сложность, из за которой и нужно так много битов
А я правильно понимаю, что именно внутренняя схожесть длога и факоризации числел - позволяют их решить Шоровской подпрограммой нахождения периода функции?