Регистрация Войти
Рейтинг:-2
C.S. avatar Crypto

Простая модульная арифметика для модулей степени двойки

флаг in
C.S.

Почему, если $q$ представляет собой целое число степени двойки, то выполнение арифметических операций по модулю $q$ (сложение и умножение) очень эффективно и просто?

44
0 + 0
forest avatar
флаг vn
forest
Я голосую за закрытие этого вопроса, потому что речь идет об эффективности простых математических операций в компьютерах, а не о криптографии.
0
Ответить
Mark avatar
флаг ng
Mark
стоит упомянуть, что это может иметь значение для криптографии --- одно (значительное) различие между финалистами NIST PQC Saber и Kyber заключается в том, что Sabre имеет модуль степени двойки $2^{13}$ (и быстрое модульное сокращение), в то время как Kyber использует дружественные к NTT модули, допускающие более эффективные (но более сложные) алгоритмы умножения. Это привело к криптографическим исследованиям, сравнивающим их, и даже к выяснению того, как внедрить умножение степени двойки в дружественное к NTT кольцо.
1
Ответить
Рейтинг:3
poncho avatar Crypto
флаг my
poncho

Почему, если $q$ представляет собой целое число степени двойки, то выполнение арифметических операций по модулю $q$ (сложение и умножение) очень эффективно и просто?

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

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.