Aritmética de campo finito - Finite field arithmetic

Em matemática , a aritmética de campos finitos é a aritmética em um campo finito (um campo contendo um número finito de elementos ), ao contrário da aritmética em um campo com um número infinito de elementos, como o campo dos números racionais .

Existem infinitamente muitos campos finitos diferentes. O seu número de elementos é necessariamente da forma de p ⁿ em que p é um número primo e n é um número inteiro positivo , e duas áreas finitas do mesmo tamanho são isomorfos . O primo p é chamado de característica do campo, e o inteiro positivo n é chamado de dimensão do campo sobre seu campo primo .

Os campos finitos são usados em uma variedade de aplicações, incluindo na teoria de codificação clássica em códigos de bloco lineares , como códigos BCH e correção de erros Reed-Solomon , em algoritmos de criptografia como o algoritmo de criptografia Rijndael ( AES ), na programação de torneios e no desenho de experimentos .

Representação polinomial efetiva

O corpo finito com p ⁿ elementos é denotado GF ( p ⁿ ) e também é chamado de campo de Galois , em homenagem ao fundador da teoria de campos finitos, Évariste Galois . GF ( p ), onde p é um número primo, é simplesmente o anel de inteiros módulo p . Ou seja, pode-se realizar operações (adição, subtração, multiplicação) usando a operação usual em inteiros, seguida do módulo de redução p . Por exemplo, em GF (5), 4 + 3 = 7 é reduzido para 2 módulo 5. A divisão é a multiplicação pelo módulo inverso p , que pode ser calculado usando o algoritmo Euclidiano estendido .

Um caso particular é GF (2), onde a adição é OR exclusivo (XOR) e a multiplicação é AND . Como o único elemento invertível é 1, a divisão é a função de identidade .

Elementos de GF ( p ⁿ ) podem ser representados como polinômios de grau estritamente menor que n em GF ( p ). As operações são então executadas no módulo R, onde R é um polinômio irredutível de grau n sobre GF ( p ), por exemplo, usando a divisão longa do polinômio . A adição de dois polinômios P e Q é feita normalmente; a multiplicação pode ser feita da seguinte maneira: calcule W = P ⋅ Q como de costume, então calcule o módulo R restante (existem maneiras melhores de fazer isso).

Existem outras representações dos elementos de GF ( p ⁿ ), algumas são isomórficas à representação polinomial acima e outras que parecem bastante diferentes (por exemplo, usando matrizes).

Quando o primo é 2, é convencional expressar os elementos de GF ( p ⁿ ) como números binários , com cada termo em um polinômio representado por um bit na expressão binária do elemento correspondente. Chaves ("{" e "}") ou delimitadores semelhantes são comumente adicionados a números binários, ou a seus equivalentes hexadecimais, para indicar que o valor é um elemento de um campo. Por exemplo, a seguir estão representações equivalentes do mesmo valor em um campo finito de característica 2:

Polinomial	x ⁶ + x ⁴ + x + 1
Binário	{01010011}
Hexadecimal	{53}

Polinômios primitivos

Existem muitos polinômios irredutíveis (às vezes chamados de polinômios redutores ) que podem ser usados para gerar um corpo finito, mas nem todos dão origem à mesma representação do campo.

Um polinômio mônico irredutível de grau $n$ tendo coeficientes no campo finito GF ( $q$ ), onde $q = p t$ para algum primo $p$ e inteiro positivo $t$ , é chamado de polinômio primitivo se todas as suas raízes forem elementos primitivos de GF ( $q n$ ) Na representação polinomial do corpo finito, isso implica que $x$ é um elemento primitivo. Há pelo menos um polinômio irredutível para o qual $x$ é um elemento primitivo. Em outras palavras, para um polinômio primitivo, as potências de $x$ geram todos os valores diferentes de zero no campo.

Nos exemplos a seguir, é melhor não usar a representação polinomial, pois o significado de $x$ muda entre os exemplos. O polinômio monic irredutível $x 8 + x 4 + x 3 + x + 1$ sobre GF (2) não é primitivo. Seja $λ$ a raiz desse polinômio (na representação polinomial seria $x$ ), ou seja, $λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Agora $λ 51 = 1$ , então $λ$ não é um elemento primitivo de GF (2 ⁸ ) e gera um subgrupo multiplicativo de ordem 51. Considere o elemento de campo $λ + 1$ (na representação polinomial seria $x$ + 1). Agora $(λ + 1) 8 + (λ + 1) 4 + (λ + 1) 3 + (λ + 1) 2 + 1 = λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Como todas as raízes deste polinômio primitivo são elementos primitivos, $λ + 1$ é um elemento primitivo de GF (2 ⁸ ) ( $(λ + 1) 255 = 1$ e nenhuma potência menor o faz). GF (2 ⁸ ) tem 128 geradores (consulte Número de elementos primitivos ). Ter $x$ como um gerador para um campo finito é benéfico para muitas operações matemáticas computacionais.

Adição e subtração

A adição e a subtração são realizadas adicionando ou subtraindo dois desses polinômios juntos e reduzindo o módulo de resultado da característica.

Em um corpo finito com característica 2, módulo de adição 2, módulo de subtração 2 e XOR são idênticos. Assim,

Polinomial	( x ⁶ + x ⁴ + x + 1) + ( x ⁷ + x ⁶ + x ³ + x ) = x ⁷ + x ⁴ + x ³ + 1
Binário	{01010011} + {11001010} = {10011001}
Hexadecimal	{53} + {CA} = {99}

Sob adição regular de polinômios, a soma conteria um termo 2 x ⁶ . Este termo torna-se 0 x ⁶ e é eliminado quando a resposta é reduzida módulo 2.

Aqui está uma tabela com a soma algébrica normal e a soma do campo finito 2 característico de alguns polinômios:

p ₁	p ₂	p ₁ + p ₂ sob ...
p ₁	p ₂	K [x]	GF (2 ⁿ )
x ³ + x + 1	x ³ + x ²	2 x ³ + x ² + x + 1	x ² + x + 1
x ⁴ + x ²	x ⁶ + x ²	x ⁶ + x ⁴ + 2 x ²	x ⁶ + x ⁴
x + 1	x ² + 1	x ² + x + 2	x ² + x
x ³ + x	x ² + 1	x ³ + x ² + x + 1	x ³ + x ² + x + 1
x ² + x	x ² + x	2 x ² + 2 x	0

Em aplicações de ciência da computação, as operações são simplificadas para campos finitos de característica 2, também chamados de campos GF (2 ⁿ ) de Galois , tornando esses campos escolhas especialmente populares para aplicações.

Multiplicação

A multiplicação em um campo finito é o módulo de multiplicação, um polinômio de redução irredutível usado para definir o campo finito. (Ou seja, é a multiplicação seguida pela divisão usando o polinômio redutor como divisor - o resto é o produto.) O símbolo "•" pode ser usado para denotar a multiplicação em um corpo finito.

Campo finito de Rijndael (AES)

Rijndael (padronizado como AES) usa o campo finito característico 2 com 256 elementos, que também pode ser chamado de campo de Galois GF (2 ⁸ ). Ele emprega o seguinte polinômio de redução para multiplicação:

x ⁸ + x ⁴ + x ³ + x + 1.

Por exemplo, {53} • {CA} = {01} no campo de Rijndael porque

	( x ⁶ + x ⁴ + x + 1) ( x ⁷ + x ⁶ + x ³ + x )
=	( x ¹³ + x ¹² + x ⁹ + x ⁷ ) + ( x ¹¹ + x ¹⁰ + x ⁷ + x ⁵ ) + ( x ⁸ + x ⁷ + x ⁴ + x ² ) + ( x ⁷ + x ⁶ + x ³ + x )
=	x ¹³ + x ¹² + x ⁹ + x ¹¹ + x ¹⁰ + x ⁵ + x ⁸ + x ⁴ + x ² + x ⁶ + x ³ + x
=	x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x

e

	x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x mod x ⁸ + x ⁴ + x ³ + x ¹ + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (decimal)

O último pode ser demonstrado por meio de divisão longa (mostrado usando notação binária, uma vez que se presta bem à tarefa. Observe que OR exclusivo é aplicado no exemplo e não subtração aritmética, como se pode usar na divisão longa de escola primária.):

                        
          11111101111110 (mod) 100011011
         ^100011011     
          01110000011110
          ^100011011    
           0110110101110
           ^100011011   
            010101110110
            ^100011011  
             00100011010
              ^100011011  
               000000001

(Os elementos {53} e {CA} são inversos multiplicativos um do outro, pois seu produto é 1. )

A multiplicação neste campo finito particular também pode ser feita usando uma versão modificada do " algoritmo do camponês ". Cada polinômio é representado usando a mesma notação binária acima. Oito bits são suficientes porque apenas os graus 0 a 7 são possíveis em termos de cada polinômio (reduzido).

Este algoritmo usa três variáveis (no sentido de programação de computador), cada uma contendo uma representação de oito bits. a e b são inicializados com os multiplicandos; p acumula o produto e deve ser inicializado em 0.

No início e no final do algoritmo, e no início e no final de cada iteração, esta invariante é verdadeira: a b + p é o produto. Obviamente, isso é verdade quando o algoritmo é iniciado. Quando o algoritmo termina, a ou b será zero, portanto, p conterá o produto.

Execute o seguinte loop oito vezes (uma vez por bit). Não há problema em parar quando a ou b for zero antes de uma iteração:
1. Se o bit mais à direita de b for definido, exclua OR o produto p pelo valor de a . Esta é uma adição polinomial.
2. Mova b um bit para a direita, descartando o bit mais à direita e fazendo com que o bit mais à esquerda tenha o valor zero. Isso divide o polinômio por x , descartando o termo x ⁰ .
3. Verifique se o bit mais à esquerda de a está definido como um e chame esse valor de carry .
4. Mudar a um pouco para a esquerda, descartando a pouco mais à esquerda, e fazer a nova extrema direita bit zero. Isso multiplica o polinômio por x , mas ainda precisamos levar em conta o transporte que representou o coeficiente de x ⁷ .
5. Se o transporte tiver o valor um, exclusivo ou a com o número hexadecimal 0x1b(00011011 em binário). 0x1bcorresponde ao polinômio irredutível com o termo alto eliminado. Conceitualmente, o termo alto do polinômio irredutível e o carry adicionam o módulo 2 a 0.
p agora tem o produto

Este algoritmo generaliza facilmente para multiplicação sobre outros campos de característica 2, alterando os comprimentos de a , b e p e o valor de forma 0x1badequada.

Multiplicativo inverso

Consulte também o algoritmo de inversão Itoh – Tsujii .

O inverso multiplicativo para um elemento a de um corpo finito pode ser calculado de várias maneiras diferentes:

Multiplicando a por cada número no campo até que o produto seja um. Esta é uma busca de força bruta .
Como os elementos diferentes de zero de GF ( p ⁿ ) formam um grupo finito com respeito à multiplicação, a ^{p ⁿ −1} = 1 (para a ≠ 0 ), então o inverso de a é a ^{p ⁿ −2} .
Usando o algoritmo Euclidiano estendido .
Fazendo tabelas de logaritmo e exponenciação para o corpo finito, subtraindo o logaritmo de p ⁿ −1 e exponenciando o resultado.
Fazendo uma tabela inversa multiplicativa modular para o campo finito e fazendo uma consulta.
Mapeando para um campo composto onde a inversão é mais simples e mapeando de volta.
Construindo um inteiro especial (no caso de um corpo finito de ordem primo) ou um polinômio especial (no caso de um corpo finito de ordem não-primo) e dividindo-o por a .

Truques de implementação

Tabelas baseadas em gerador

Ao desenvolver algoritmos para computação de campo de Galois em pequenos campos de Galois, uma abordagem comum de otimização de desempenho é encontrar um gerador ge usar a identidade:

{\ displaystyle ab = g ^ {\ log _ {g} (ab)} = g ^ {\ log _ {g} (a) + \ log _ {g} (b)}}

para implementar a multiplicação como uma sequência de pesquisas na tabela para as funções log _g ( a ) e g ^y e uma operação de adição de inteiro. Isso explora a propriedade de que todo campo finito contém geradores. No exemplo de campo de Rijndael, o polinômio x + 1 (ou {03}) é um desses geradores. Uma condição necessária, mas não suficiente, para que um polinômio seja um gerador é ser irredutível .

Uma implementação deve testar o caso especial de a ou b sendo zero, pois o produto também será zero.

Essa mesma estratégia pode ser usada para determinar o inverso multiplicativo com a identidade:

{\ displaystyle a ^ {- 1} = g ^ {\ log _ {g} \ left (a ^ {- 1} \ right)} = g ^ {- \ log _ {g} (a)} = g ^ {| g | - \ log _ {g} (a)}}

Aqui, a ordem do gerador, | g |, é o número de elementos diferentes de zero do campo. No caso de GF (2 ⁸ ), é 2 ⁸ - 1 = 255 . Ou seja, para o exemplo de Rijndael: (x + 1) ²⁵⁵ = 1 . Portanto, isso pode ser executado com duas tabelas de pesquisa e uma subtração de inteiro. Usar essa ideia para exponenciação também traz benefícios:

{\ displaystyle a ^ {n} = g ^ {\ log _ {g} \ left (a ^ {n} \ right)} = g ^ {n \ log _ {g} (a)} = g ^ {n \ log _ {g} (a) {\ pmod {| g |}}}}

Isso requer duas pesquisas de tabela, uma multiplicação de inteiro e uma operação de módulo de inteiro. Novamente, um teste para o caso especial a = 0 deve ser executado.

No entanto, em implementações criptográficas, deve-se ter cuidado com tais implementações, uma vez que a arquitetura de cache de muitos microprocessadores leva a um tempo variável para o acesso à memória. Isso pode levar a implementações que são vulneráveis a um ataque de sincronismo .

Carryless multiply

Para campos binários GF (2 ^ n ), a multiplicação de campo pode ser implementada usando uma multiplicação carryless como o conjunto de instruções CLMUL , que é bom para n <= 64. Uma multiplicação usa uma multiplicação carryless para produzir um produto (até 2 n - 1 bits), outra multiplicação sem transporte de um inverso pré-calculado do polinômio de campo para produzir um quociente = ⌊ produto / (polinômio de campo) ⌋, uma multiplicação do quociente pelo polinômio de campo, então um xor: resultado = produto ⊕ ( (polinômio de campo) ⌊ produto / (polinômio de campo) ⌋). As últimas 3 etapas (pclmulqdq, pclmulqdq, xor) são usadas na etapa de redução de Barrett para cálculo rápido de CRC usando a instrução pclmulqdq X86.

Campo composto

Quando $k$ é um número composto , existirão isomorfismos de um campo binário GF (2 ^k ) para um campo de extensão de um de seus subcampos, ou seja, GF ((2 ^m ) ⁿ ) onde k = m n . Utilizar um desses isomorfismos pode simplificar as considerações matemáticas, pois o grau de extensão é menor com a desvantagem de que os elementos agora são representados em um subcampo maior. Para reduzir a contagem de portas para implementações de hardware, o processo pode envolver múltiplos aninhamentos, como mapeamento de GF (2 ⁸ ) para GF (((2 ² ) ² ) ² ). Existe uma restrição de implementação, as operações nas duas representações devem ser compatíveis, então o uso explícito do isomorfismo é necessário. Mais precisamente, o isomorfismo será denotado por map (), é uma bijeção que mapeia um elemento de GF (2 ^k ) para GF ((2 ^m ) ⁿ ), satisfazendo: map (a + b) = map (a) + map (b) e map (ab) = map (a) map (b), onde as operações do lado esquerdo ocorrem em GF (2 ^k ) antes do mapeamento e as operações do lado direito ocorrem em GF ((2 ^m ) ⁿ ) após o mapeamento. O isomorfismo é geralmente implementado com uma matriz de k linhas por k bits, usada para realizar uma multiplicação da matriz sobre GF (2) de um elemento de GF (2 ^k ) tratado como uma matriz de k linhas por 1 bit. Defina α como um elemento primitivo de GF (2 ^k ) e β como um elemento primitivo de GF ((2 ^m ) ⁿ ). Então β ^j = map (α ^j ) e α ^j = map ⁻¹ (β ^j ). Os valores de α e β determinam a matriz de mapeamento e sua inversa. Como a matemática real é realizada em GF ((2 ^m ) ⁿ ), o polinômio redutor para GF ((2 ^m ) ⁿ ) é geralmente primitivo e β = x em GF ((2 ^m ) ⁿ ). Para atender à restrição de compatibilidade para adição e multiplicação, é feita uma busca para escolher qualquer elemento primitivo α de GF (2 ^k ) que atenderá a restrição. No caso em que o polinômio de redução para GF (2 ^k ) é primitivo, um método de mapeamento alternativo é possível: os coeficientes de 1 bit do polinômio de redução para GF (2 ^k ) são interpretados como m elementos de bit 0 ou 1 de GF (2 ^m ), e haverá m fatores primitivos de grau n , qualquer um dos quais pode ser usado como o polinômio redutor para GF ((2 ^m ) ⁿ ). O mapeamento para um campo composto pode ser generalizado para mapear GF ( p ^k ) para um campo composto como GF (( p ^m ) ⁿ ), para p um número primo maior que 2, mas tais campos não são comumente usados na prática.

Exemplos de programas

Exemplo de programação C

Aqui está um código C que adicionará e multiplicará números no campo finito característico 2 de ordem 2 ⁸ , usado por exemplo pelo algoritmo de Rijndael ou Reed-Solomon, usando o algoritmo de multiplicação camponês russo :

/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the polynomial x^8 + x^4 + x^3 + x + 1 = 0
 * using the Russian Peasant Multiplication algorithm
 * (the other way being to do carry-less multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* the product of the multiplication */
	while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x11b; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
	}
	return p;
}

Este exemplo tem vazamentos de canal lateral de cache, tempo e previsão de ramificação e não é adequado para uso em criptografia.

Exemplo de programação D

Este programa em D multiplicará os números no campo finito de Rijndael e gerará uma imagem PGM :

/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}

Este exemplo não usa ramificações ou pesquisas de tabela para evitar canais secundários e, portanto, é adequado para uso em criptografia.

Veja também

Logaritmo de Zech

Referências

Fontes

Lidl, Rudolf; Niederreiter, Harald (1983), Finite Fields , Addison-Wesley, ISBN 0-201-13519-1(reeditado em 1984 pela Cambridge University Press ISBN 0-521-30240-4 ).
Mullen, Gary L .; Panario, Daniel (2013), Handbook of Finite Fields , CRC Press, ISBN 978-1-4398-7378-6

links externos

Gordon, G. (1976). "Método muito simples para encontrar o polinômio mínimo de um elemento arbitrário diferente de zero de um corpo finito". Cartas de eletrônicos . 12 (25): 663–664. doi : 10.1049 / el: 19760508 .
da Rocha, VC; Markarian, G. (2006). "Método simples para encontrar vestígios de elemento arbitrário de um corpo finito". Cartas de eletrônicos . 42 (7): 423–325. doi : 10,1049 / el: 20060473 .
Trenholme, Sam. "Campo Galois de AE" .
Planck, James S. (2007). "Biblioteca Aritmética de Campo Galois Rápida em C / C ++" .
Wikiversidade: Reed – Solomon for Coders - Aritmética de Campos Finitos

Languages

In other projects