О “слабых” ключах задачи Диффи–Хеллмана в поле $\mathbf F_{p^m}$

Задача Диффи–Хеллмана в циклической группе $G$ порядка $n$ заключается в определении по заданным элементам $a$ – образующему группы $G$, $b=a^k$, $c=a^l$ (для некоторых $k$, $l\in\mathbf Z_n\setminus0$) элемента $s=a^{kl}$. В случае когда $G$ является подгруппой мультипликативной группы поля $\mathbf F_{p^m}$, $p$ – простое, $n$ – большое простое число, эта задача имеет важные приложения в криптографии, поскольку предположение о ее вычислительной сложности является обоснованием стойкости ряда криптографических схем на основе эффективно вычисляемых невырожденных билинейных отображений конечных групп. Единственными известными на сегодняшний день примерами таких отображений являются спаривания Вейля и Тейта, отображающие декартов квадрат подгруппы порядка $n$ группы точек эллиптической кривой над конечным полем характеристики $p$ в подгруппу того же порядка группы $\mathbf F_{p^m}$. При этом, если кривая определена над простым полем, то $m$ – порядок $p$ в $\mathbf Z_n^*$ и по известной теореме Хассе $n\le p+2\sqrt p+1$, поэтому на практике обычно $n\sim p$ или $n=o(p)$ при $p\to\infty$.
В 2005 г. в работе индийских математиков А. Калеле и В. Суле были определены некоторые множества “слабых” ключей задачи Диффи–Хеллмана в подгруппе произвольного порядка $n$ группы $\mathbf F_{p^m}^*$, т.е. значений $k$, для которых при заданных $a$ и $l$ задача решается за полиномиальное время. В настоящей работе рассматривается случай, когда $n$ – простое, $n>2$, $m$ – порядок $p$ в $\mathbf Z_n^*$, $m>1$. Доказано, что при $m=2$ указанные “слабые” ключи, за исключением нескольких тривиальных значений, отсутствуют. Сформулированы необходимые и достаточные условия тривиальности множеств “слабых” ключей при заданных $p$, $m$, $n$. С их помощью при некотором эвристическом предположении вероятностного характера показано, что для любого фиксированного $m>2$ вероятность существования нетривиальных “слабых” ключей стремится к нулю при $p\to\infty$ как в случае $n\sim p$, так и в случае $n=o(p)$, за исключением случая $m=3$, $n\sim p$, когда эта вероятность стремится к $1-e^{-1/36}\approx0.0274$.