Como funciona a redução de Montgomery?

Oct 03 2020

Eu quero reduzir um número inteiro de precisão múltipla $x$ modulo a prime $p$, muito rápido. Executar a divisão euclidiana tradicional para calcular apenas o módulo é ineficiente e a redução modular está no coração de muitas primitivas criptográficas como a criptografia de curva elíptica. Existem outros métodos para realizar a tarefa mencionada, como redução de Barret, etc, mas eu gostaria de aprender sobre a redução de Montgomery e suas peculiaridades primeiro, por causa de seu significado prático. Algoritmo:

     Input : Integer x, n, k 
     Output : (2^(-k) * x) mod n
    1. for t from 1 to k do
        1.1 if x is odd then
            1.1.1     x <- x+n
        1.2 x <- x/2
    2 Return x

Existem restrições sobre $x$ gostar, $0$ <= $x$ < $n^2$, e também, $n$deve ser estranho. O livro do qual tomei emprestado o algoritmo acima, afirma dois fatos:

Fato 1 : Adicionar n a x não muda o resíduo, pois, na verdade, adiciona um ao quociente ⌊x / n⌋. Outra maneira de explicar isso é que n é (ou múltiplos de n são) congruentes com o módulo nulo n. Adicionar zero não mudará o valor do resíduo.

Fato 2 : se$x$ é par, então realizando uma divisão por dois em $Z$ é congruente com $x · 2^{−1} \mod n$. Na verdade, esta é uma aplicação do fato de que se x é igualmente divisível por qualquer$k$ ∈ $Z$, então a divisão em Z será congruente com a multiplicação por $k^{−1}$ modulo $n$ .

Não entendo o significado do Fato 2 . Na verdade, estou tendo problemas em compreender como o autor transcende da aritmética regular para a aritmética modular. Por que essa divisão de$x$ por dois em $Z$ (inteiros) é congruente com a multiplicação por $2^{-1}$ no módulo $n$. Depois de tudo$2^{-1}\mod n$ pode ser facilmente calculado pelo algoritmo euclidiano estendido: Visto que, $n = 2*q + r$. Desde a$n$ é estranho, $r$ deveria estar $1$. Portanto, na transposição, obtemos:$n - 2*q = 1$. Se tomarmos este módulo de equação anterior$n$, Nós temos $-q$ como o inverso multiplicativo de $2$ wrt mod n.

Seria muito apreciado, em primeiro lugar, se eu pudesse obter uma boa explicação de como a redução de Montgomery funciona. Por que continuamos adicionando$n$ para $x$ , E se $x$ é estranho?

Estou perdendo uma grande clareza em meu entendimento! Quais são os princípios sólidos por trás da multiplicação Montgomery com redução? Visto que venho principalmente de experiência em programação, parece que não tenho algum conhecimento matemático neste contexto.

Cada ajuda será muito apreciada!

Respostas

5 kelalaka Oct 03 2020 at 20:07

Em 1985, Montgomery introduziu uma nova maneira inteligente de representar os números $\mathbb{Z}/n \mathbb{Z}$ de modo que a aritmética, especialmente as multiplicações modulares, se tornam mais fáceis.

Peter L. Montgomery ; Multiplicação modular sem divisão experimental , 1985

Precisamos do módulo $n$ estamos trabalhando e um inteiro $r$ de tal modo que $\gcd(r,n) =1$ e $r>n$

Definição: A representação Montgomery de$x \in [0,n-1]$ é $\bar{x} = (xr) \bmod n$

Definição: A redução de Montgomery de$u \in [0,rn-1]$ é $Redc(u) = (ur^{-1}) \bmod n$. Isso também é chamado$n$-resíduo em relação a $r$. Na verdade, pode-se mostrar que este conjunto$$\{i\cdot r \bmod n | 0 \leq i \leq n\}$$ é um sistema de resíduos completo.

Na criptografia, geralmente trabalhamos com módulo principal, portanto, podemos escolher $r = 2^k$. Neste caso, o$\gcd(r,n) = \gcd(2^k,n) = 1$ é satisfeito.

Fato 1:

Já que estamos trabalhando módulo $n$, este é um resultado elementar.

Fato 2: se $x$ é par, então realizando uma divisão por dois em $\mathbb{Z}$ é congruente com $x\cdot 2^{−1} \bmod n$. Na verdade, esta é uma aplicação do fato de que se$x$ é igualmente divisível por qualquer $k \in \mathbb{Z}$, então a divisão em $\mathbb{Z}$ será congruente com a multiplicação por $k^{−1} \bmod n$.

O que eles tentam dizer é

Deixei $k$ divide $x$ então $u \cdot k = x$ pegue o módulo $n$ em ambos os lados. $$u \cdot k = x \bmod n$$ Desde a $n$ é principal do que $k^{-1}$ existe no módulo $n$e isso pode ser encontrado com o Algoritmo Euclidiano Estendido. Para Montgomery, isso é necessário apenas uma vez para$r$. Agora temos;

$$u \cdot k \cdot k^{-1} = x \cdot k^{-1} \bmod n$$

$$u = x \cdot k^{-1} \bmod n$$

1,2 x <- x / 2

Quando o $r = 2^k$isso geralmente é executado por operações de turno. Este é um truque do Montgomery. A divisão experimental é transferida em turnos.

x = x >> 2

Quais são os princípios sólidos por trás da multiplicação Montgomery com redução?

Redução de Montgomery Esta é a versão da Wikipedia.

input: Integers r and n with gcd(r, n) = 1,
       Integer n′ in [0, r − 1] such that nn′ ≡ −1 mod r,
       Integer T in the range [0, rn − 1]
output: Integer s in the range [0, n − 1] such that s ≡ Tr^−1 mod n

m = ((T mod r)n′) mod r
t = (T + mn) / r
if t ≥ n then
    return t − n
else
    return t

Agora, a vantagem é clara. Desde a$r= 2^{k}$ a divisão e $\bmod$ as operações são baratas por deslocamento ou mascaramento.

o $n'$ é definido como $rr^{-1} -n n' =1$

A correção pode ser vista por

observe que se $m = (( T \bmod r )n^{'}) \bmod r$ então $T + mn$ é divisível por $r$.

$$T + mn \equiv T + (((T \bmod r)n') \bmod r)n \equiv T + T n' n \equiv T - T \equiv 0 \pmod{R}$$ Lá para o $t$ é um número inteiro, não um ponto flutuante.

A saída então é $y$ ou $t-n$(lembre-se do fato 1). Agora vamos ver porque a saída é$Tr^{-1}$. Nós novamente usamos o que sabemos

$$t \equiv ( T + mn )r^{-1} \equiv Tr^{-1} + (mr^{-1})n \equiv Tr^{-1} \pmod{n)}$$

Portanto, a saída tem o resíduo correto como desejamos.

Por que a substrução? Precisamos acompanhar o$t$tamanho de.

$m \in [0,r-1]$
$T+mn$ então fica entre $0$ e $(rn-1) + (r-1)n < 2rn$. Desde que foi divido por$r$ então $0 \leq t \leq 2n-1$. Uma única subtração pode reduzir o$t$ no intervalo desejado.

Produto Montgomery

Vamos definir uma função que será muito poderosa. Lembrar$\bar{a} = ar \bmod n$

$MonPro(\bar{a},\bar{b},r,n)$

// saídas $t = MonPro(\bar{a},\bar{b},r,n) = \bar{a}\bar{b}r^{-1} \pmod{n}$
- $ T = \bar{a}\bar{b}$
- $m = T n' \bmod r$
- $t = (T+mn)/r$
- E se $t \geq n$ $\text{return}(t-n)$
- $\text{return}(t)$

Vamos simplificar o $MonPro(\bar{a},\bar{b},r,n)$ para $MonPro(\bar{a},\bar{b})$ uma vez que os mantemos constantes e $r^{}$ pode ser calculado como constante antes das operações.