Группа RSA для модуля $N$ секретной факторизации просто является мультипликативная группа целых чисел по модулю $N$, часто отмечают $\mathbb Z_N^*$. Это можно рассматривать или определять как подмножество целых чисел $м$ в интервале $[0,N)$ с $\gcd(N,m)=1$. Групповой закон - умножение по модулю $N$, это $а*б$ это оставшаяся часть Евклидово деление из $а\раз б$, куда $\раз$ целочисленное умножение.
Эта группа имеет порядок Эйлер тотиент $\varphi(N)$. Эта величина неизвестна, так как факторизация $N$ является. Мы можем легко вычислить $\varphi(N)$ если мы знаем факторизацию $N$, и оказывается, мы можем факторизовать $N$ если мы знаем $N$ и $\varphi(N)$.
Примечание. Шифрование/дешифрование RSA часто работает на полную мощность. моноид $[0,N)$ при умножении по модулю $N$, а не его групповое подмножество $\mathbb Z_N^*$. Это требует, чтобы $N$ является квадратныйсвободный чтобы расшифровка работала надежно.
У Бенджамина Весоловски Эффективные проверяемые функции задержки (в материалы EuroCrypt 2019), $(\mathbf Z/N\mathbf Z)^Ã$ является $\mathbb Z_N^*$. Их обозначения отражают конструкцию этой группы как ограничения на обратимые элементы фактормножества классы эквивалентности в целых числах (что они отмечают $\mathbf Z$ скорее, чем $\mathbb Z$ выше) для отношения эквивалентности конгруэнтны² по модулю $N$, по закону $Ã$ что совместимо с этим отношением эквивалентности. Я понимаю, как это делают настоящие математики; Я не совсем один.
Видеть комментарий дополнительные ссылки на VDF.
¹ то есть, поскольку это конечное множество, это количество элементов.
² по определению, $a\equiv b\pmod N\iff\exists q,\,a=b+q\times N$, со всеми количествами в $\mathbb Z$.
