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

В математике простое число Солинаса или обобщенное простое число Мерсенна - это простое число , имеющее форму , где - многочлен низкой степени с малыми целыми коэффициентами . ^{[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]). Пусть будет целым числом в -м регистре на -м шаге и обратите внимание, что первая строка имеет значение . Тогда, если мы обозначим целочисленным вектором, заданным как:${\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.}$

См. Также [ править ]

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

Ссылки [ править ]