Проблема с более высокой остаточной плотностью

В криптографии большинство криптосистем с открытым ключом основаны на проблемах, которые считаются неразрешимыми. Проблема с более высокой остаточностью (также называемая проблемой n -го остатка ^[1] ) является одной из таких проблем. Эту проблему решить легче, чем целочисленную факторизацию , поэтому предположение о том, что эту проблему трудно решить, сильнее предположения о том, что целочисленная факторизация трудна.

Если n — целое число , то целые числа по модулю n образуют кольцо . Если n = pq , где p и q — простые числа , то китайская теорема об остатках говорит нам, что

${\displaystyle \mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z} }$

Единицы любого кольца образуют группу при умножении, и группа единиц в традиционно обозначается .${\displaystyle \mathbb {Z} / n\mathbb {Z} }$${\displaystyle (\mathbb {Z} /n\mathbb {Z})^{\times }}$

Из изоморфизма колец выше следует, что

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }}$

как изоморфизм групп . Поскольку p и q предполагались простыми, группы и являются циклическими порядков p −1 и q −1 соответственно. Если d является делителем p −1, то множество d  -х степеней в образует подгруппу индекса d . Если gcd( d , q −1) = 1, то каждый элемент в является d  -й степенью, поэтому множество d  -х степеней в также является подгруппой индекса d . В общем случае, если gcd( d , q −1) = g , то существует ( q −1)/ g d  -х степеней в , поэтому множество d  -х степеней в имеет индекс dg . Чаще всего это наблюдается, когда d = 2, и мы рассматриваем подгруппу квадратичных вычетов ; хорошо известно, что ровно четверть элементов в являются квадратичными вычетами (когда n является произведением двух простых чисел, как здесь).${\displaystyle (\mathbb {Z} /p\mathbb {Z})^{\times }}$${\displaystyle (\mathbb {Z} /q\mathbb {Z})^{\times }}$${\displaystyle (\mathbb {Z} /p\mathbb {Z})^{*}}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z})^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z})^{\times }}$ ${\displaystyle (\mathbb {Z} /q\mathbb {Z})^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z})^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z})^{\times }}$

Важным моментом является то, что для любого делителя d числа p −1 (или q −1) множество d  -х степеней образует подгруппу${\displaystyle (\mathbb {Z} /n\mathbb {Z})^{\times}.}$

Если задано целое число n = pq , где p и q неизвестны, целое число d, такое что d делит p −1, и целое число x < n , то невозможно определить, является ли x степенью d  (или  вычетом d ) по модулю n .

Обратите внимание, что если известны p и q, то легко определить, является ли x d-ым  остатком по модулю n, поскольку x будет d-  ым остатком по модулю p тогда и только тогда, когда

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod {p}}}$

При d = 2 это называется проблемой квадратичных остатков .

Семантическая безопасность криптосистемы Бенало и криптосистемы Наккаш–Стерн основана на неразрешимости этой проблемы.