Implementando Aritmética de Corpos Finitos em Rust

Introdução

Corpos finitos, também conhecidos como corpos de Galois, são estruturas algébricas que têm um número finito de elementos e seguem regras matemáticas específicas. Eles desempenham um papel fundamental em várias áreas da matemática, ciência da computação e criptografia.

Importância dos Corpos Finitos na Ciência da Computação e Criptografia:

1.Correção de Erros e Codificação de Dados:

• Corpos Finitos desempenham um papel crucial em códigos de correção de erros, onde são usados para codificar e decodificar dados a fim de detectar e corrigir erros durante a transmissão.

2.Criptografia:

• Na criptografia moderna, corpos finitos são usados para definir curvas elípticas, que formam a base da criptografia de curva elíptica (ECC). A ECC é amplamente usada em comunicações seguras e assinaturas digitais devido à sua forte segurança e eficiência.
• Corpos finitos também são usados no Bitcoin e em outras criptomoedas. Eles são usados como um componente fundamental em várias partes essenciais.

3.Teoria da Codificação:

• Corpos finitos são fundamentais na teoria da codificação, que lida com códigos de detecção e correção de erros usados no armazenamento de dados, comunicação e compressão.

4.Funções Hash Criptográficas:

• Corpos finitos são utilizados em funções hash criptográficas, que são funções unidirecionais que mapeiam dados de tamanho arbitrário para valores de hash de tamanho fixo. Essas funções são vitais para garantir a integridade e autenticidade dos dados.

5.Geração de Números Pseudoaleatórios:

• Corpos finitos são usados em certos algoritmos para gerar números pseudoaleatórios, que encontram aplicações em simulações, jogos e protocolos criptográficos.

6.Teoria de Galois:

• Corpos finitos estão intimamente ligados à teoria de Galois, um ramo da álgebra abstrata. A teoria de Galois fornece insights sobre as propriedades dos corpos finitos e suas extensões.

7.Processamento Digital de Sinais:

• Corpos finitos são usados em certas aplicações de processamento digital de sinais, como correção de erros em dados de áudio e imagem.

Neste blog, tentarei implementar corpos finitos em Rust.

Corpos Finitos

Definição de Corpo Finito

Formalmente, um corpo finito é definido como um conjunto de elementos juntamente com duas operações binárias, + (adição) e * (multiplicação), que satisfazem certas propriedades. O número de elementos em um corpo finito é chamado de sua ordem, representada por p, onde p é um número primo. O corpo finito é denotado como Fp.

Propriedades Básicas dos Corpos Finitos:

• Fechamento: O resultado da adição e multiplicação de quaisquer dois elementos no corpo finito também pertence ao corpo finito. Em outras palavras, corpos finitos são fechados sob adição e multiplicação.

ex:) Se a e b pertencem ao conjunto, a + b e a * b também pertencem ao conjunto.

• Adição: Corpos finitos formam um grupo abeliano sob adição. Isso significa que a adição é comutativa (a + b = b + a), associativa (a + (b + c) = (a + b) + c) e possui um elemento de identidade (0) tal que a + 0 = a para qualquer elemento a no corpo. Além disso, cada elemento possui um inverso aditivo (−a) tal que a + (−a) = 0.

• Multiplicação: Os elementos não nulos de um corpo finito formam um grupo abeliano sob multiplicação. Isso significa que a multiplicação é comutativa (a * b = b * a), associativa (a * (b * c) = (a * b) * c) e possui um elemento de identidade (1) tal que a * 1 = a para qualquer elemento não nulo a no corpo. Além disso, cada elemento não nulo possui um inverso multiplicativo (a^−1) tal que a * a^−1 = 1.

• Inverso aditivo: Se a pertence ao conjunto, -a pertence ao conjunto, o que é definido como o valor que torna a + (-a) = 0.

• Inverso multiplicativo: Se a pertence ao conjunto e não é igual a 0, a ^ -1 pertence ao conjunto, definido como o valor que torna a * a ^ -1 = 1.

Implementação de CorpoCampo Finito em Rust

Construção de Elemento de Corpo

Primeiramente, precisamos criar uma nova struct chamada FieldElement (Elemento de Corpo).

#[derive(Debug, Clone)]
pub struct FieldElement {
    pub num: u64,
    pub prime: u64,
}

impl FieldElement {
    pub fn new(num: u64, prime: u64) -> Self {

        // verifique se num está entre 0 e primo-1 inclusive.
        // se não, entrará em pânico.
        if num >= prime {
            panic!("Num {} not in field range 0 to {}", num, prime - 1);
        } 

        Self {
            num,
            prime
        }
    }
}

// use a característica PartialEq para verificar se dois corposcampos são iguais ou não
impl PartialEq for FieldElement {
    fn eq(&self, other: &FieldElement) -> bool {
        self.num == other.num && self.prime == other.prime
    }
}

impl Eq for FieldElement {}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_compare_two_field_elements() {
        let a = FieldElement::new(7, 13);
        let b = FieldElement::new(6, 13);

        assert_ne!(a, b);
        assert_eq!(a, a);
    }
}

Aritmética de Módulo

Uma das ferramentas que podemos usar para tornar um corpo finito fechado sob adição, subtração, multiplicação e divisão é algo chamado aritmética de módulo.

7 % 3 = 1

Acredito que você já tenha aprendido sobre essa operação. Sempre que a divisão não era exata, havia algo chamado "resto", que é a quantidade que sobra da divisão real.

Vamos ver algum código sobre como escrever a aritmética de módulo.

Em Python

print(7 % 3)
# 1
print(-27 % 13)
# 12

Em Rust, obteremos um resultado diferente ao calcular com números negativos.

println!("{:?}", (7 % 3));
// 1
println!("{:?}", (-27 % 13));
// -1

Portanto, precisamos usar uma dependência especial para lidar com a função de módulo.
Desta vez, usarei este crate de modulo.

[dependencies]
modulo = "0.1.2"

Adição e Subtração

Em seguida, adicionaremos a função de adição (add) e a função de subtração (sub).
Rust fornece certos aspectos para cada operação. Portanto, usaremos isso.

impl Add for FieldElement {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Ouput {

        // tem que garantir que os elementos sejam dos mesmos corposcampos finitos
        if self.prime != rhs.prime {
            panic!("cannot add two numbers in different Fields");
        }
    }

    // adição em um corpocampo finito é definida com o operador módulo
    let num = (self.num + other.num).modulo(self.prime);
    Self {
        num,
        prime: self.prime,
    }
}

impl Sub for FieldElement {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        if self.prime != rhs.prime {
            panic!("cannot subtract two numbers in different Fields");
        }

        let num = (self.num - other.num).modulo(self.prime);
        Self {
            num,
            prime: self.prime,
        }
    }
}


#[cfg(test)]
mod tests {
    use super::*;


...

    #[test]
    fn test_add() {
        let a = FieldElement::new(7, 13);
        let b = FieldElement::new(12, 13);
        let c = FieldElement::new(6, 13);

        assert_eq!(a + b, c);
    }
}

Multiplicação e Exponenciação

impl Mul for FieldElement {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        if self.prime != rhs.prime {
            panic!("cannot subtract two numbers in different Fields");
        }

        let num = (self.num * other.num).modulo(self.prime);
        Self {
            num,
            prime: self.prime,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;


...

    #[test]
    fn test_mul() {
        let a = FieldElement::new(3, 13);
        let b = FieldElement::new(12, 13);
        let c = FieldElement::new(10, 13);

        assert_eq!(a * b, c);
    }
}

Eu acho que o Rust não tem um aspecto de exponenciação, então definiremos a função pow dentro de impl FiniteField {}.

impl FieldElement {

...

    pub fn pow(&self, exponent: u32) -> Self {
        let num = self.num.pow(exponent).modulo(self.prime);
        Self {
            num,
            prime: self.prime,
        }
    }

}

#[cfg(test)]
mod tests {
    use super::*;


...

    #[test]
    fn test_pow() {
        let a = FieldElement::new(3, 13);
        let c = FieldElement::new(1, 13);

        assert_eq!(a.pow(3), c);
    }
}

Divisão

Quando se trata de divisão em corpo finito, pode ser um pouco difícil de entender à primeira vista.

Podemos implementar da seguinte forma.

impl Div for FieldElement {
    type Output = Self;

    fn div(self, rhs: Self) -> Self::Output {
        if self.prime != rhs.prime {
            panic!("cannot divide two numbers in different Fields");
        }

        // use o pequeno teorema de Fermat
        // self.num.pow(p-1) % p == 1
        // isso significa:
        // 1/n == pow(n, p-2, p) em Python
        let exp = rhs.prime - 2;
        let num_pow = rhs.pow(exp);
        let result = self.num * num_pow.num;
        Self {
            num: result % self.prime,
            prime: self.prime,
        }
    }
}


#[cfg(test)]
mod tests {
    use super::*;


...

    #[test]
    fn test_div() {
        let prime = 19;
        let mut a = FieldElement::new(2, prime);
        let mut b = FieldElement::new(7, prime);
        let mut c = FieldElement::new(3, prime);

        assert_eq!(a / b, c);

        a = FieldElement::new(7, prime);
        b = FieldElement::new(5, prime);
        c = FieldElement::new(9, prime);

        assert_eq!(a / b, c);
    }
}

Isso é tudo para todas as operações. Se você estiver perdido, pode ver o código completo aqui.

Conclusão

Neste blog, aprendemos sobre corpos finitos e como implementá-los em Rust. Vou usar a estrutura FieldElement no próximo blog.
Até a próxima postagem no blog.

Esse artigo é uma tradução feita por @bananlabs. Você pode encontrar o artigo original aqui