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

Простое число формы, позволяющей быстрое модульное сокращение.

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

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

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

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

Пусть – монический многочлен степени с коэффициентами в и предположим, что это простое число Солинаса. Учитывая число , содержащее до бит, мы хотим найти число, соответствующее модулю только с таким количеством битов, как , то есть с не более чем битами. ${\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}}$

Затем сгенерируйте матрицу, пошагово умножая регистр сдвига с линейной обратной связью , определенный полиномом : начиная с целочисленного регистра , сдвигайте вправо на одну позицию, вводите слева и добавляйте (покомпонентно) выходное значение раз. вектор на каждом шаге (подробнее см. [1]). Позвольте быть целым числом в регистре th на шаге th и обратите внимание, что первая строка задается как . Тогда, если мы обозначим целочисленным вектором, заданным формулой: ${\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}]}$ ${\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}$

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

Примеры

Четыре из рекомендованных простых чисел в документе 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}$

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

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

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

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

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