Солинас Прайм - Solinas prime

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

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

• Простые числа Мерсенна, которые имеют вид ${\displaystyle 2^{k}-1}$
• Простые числа Крэндалла или псевдомерсена, которые имеют вид ${\displaystyle 2^{k}-c}$ для небольших странностей ${\displaystyle c}$^[3]

Модульный алгоритм редукции

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

Во-первых, представляем ${\displaystyle n}$ в базе ${\displaystyle 2^{m}}$:

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

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

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

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

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

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

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

Примеры простых чисел Solinas

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

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

Подкрутка448 использует простое число Солинаса ${\displaystyle 2^{448}-2^{224}-1}$

Смотрите также

• Мерсенн прайм

Рекомендации

1. Солинас, Джером А. (1999). Обобщенные числа Мерсенна (PDF) (Технический отчет). Центр прикладных криптографических исследований, Университет Ватерлоо. КОРР-99-39.
2. Солинас, Джером А. (2011). «Обобщенное прайм Мерсенна». В Тилборге - Хенк К. А. ван; Jajodia, Sushil (ред.). Энциклопедия криптографии и безопасности. Springer США. стр.509 –510. Дои:10.1007/978-1-4419-5906-5_32. ISBN  978-1-4419-5905-8.
3. Патент США 5159632, Ричард Э. Крэндалл, «Метод и устройство для обмена открытыми ключами в криптографической системе», выпущенный 1992-10-27, переуступлен NeXT Computer, Inc.