Солинас Прайм

В математике простое число Солинаса или обобщенное простое число Мерсенна — это простое число , имеющее вид $f(2^{m})$, где $f(x)$ – низкой степени полином с малыми целыми коэффициентами . Эти простые числа позволяют использовать быстрые алгоритмы модульного сокращения и широко используются в криптографии . Они названы в честь Жерома Солинаса.

Этот класс чисел включает в себя несколько других категорий простых чисел:

• Простые числа Мерсенна , имеющие вид $2^{k}-1$,
• Простые числа Крэндалла или псевдо-Мерсенна, имеющие вид $2^{k}-c$ за небольшую нечетность $c$.

алгоритм

Позволять $f(t)=t^{d}-c_{d-1}t^{d-1}-...-c_{0}$ быть моническим многочленом степени $d$ с коэффициентами в $\mathbb {Z}$ и предположим, что $p=f(2^{m})$ является простым числом Солинаса. Учитывая число $n<p^{2}$ с до $2md$ бит, мы хотим найти число соответствующее , $n$ против $p$ только с таким количеством битов, как $p$ – то есть не более чем $md$ биты.

Сначала представьте $n$ в базе $2^{m}$:

$n=\sum _{j=0}^{2d-1}A_{j}2^{mj}$

Далее сгенерируйте $d$-к- $d$ матрица $X=(X_{i,j})$ шагнув $d$ раз регистр сдвига с линейной обратной связью, определенный $\mathbb {Z}$ полиномом $f$: начиная с $d$-целочисленный регистр $[0|0|...|0|1]$, сдвиг вправо на одну позицию, впрыскивание $0$ слева и добавляя (покомпонентно) выходное значение, умноженное на вектор $[c_{0},...,c_{d-1}]$ на каждом шаге (подробнее см. [1]). Позволять $X_{i,j}$ быть целым числом в $j$й регистр на $i$шаге и обратите внимание, что первая строка $X$ дается $(X_{0,j})=[c_{0},...,c_{d-1}]$. Тогда если мы обозначим через $B=(B_{i})$ целочисленный вектор, заданный формулой:

$(B_{0}...B_{d-1})=(A_{0}...A_{d-1})+(A_{d}...A_{2d-1})X$,

можно легко проверить, что:

$\sum _{j=0}^{d-1}B_{j}2^{mj}\equiv \sum _{j=0}^{2d-1}A_{j}2^{mj}\mod p$.

Таким образом $B$ представляет собой $md$-битное целое число, соответствующее $n$.

Для разумного выбора $f$ (опять же см. [1]), этот алгоритм включает в себя лишь относительно небольшое количество сложений и вычитаний (и никаких делений!), поэтому он может быть гораздо более эффективным, чем наивный алгоритм модульной редукции ( $n-p\cdot (n/p)$).

Примеры

Четыре из рекомендованных простых чисел в : документе NIST «Рекомендуемые эллиптические кривые для использования федеральным правительством» являются простыми числами Солинаса

• р-192 $2^{192}-2^{64}-1$
• р-224 $2^{224}-2^{96}+1$
• р-256 $2^{256}-2^{224}+2^{192}+2^{96}-1$
• р-384 $2^{384}-2^{128}-2^{96}+2^{32}-1$

Curve448 использует простое число Солинаса. $2^{448}-2^{224}-1.$

См. также

• Мерсенн премьер