Implementando un Campo Aritmético Finito en Rust

Introducción

Los Campos Finitos, también conocidos como los Campos Galois, son estructuras algebráicas que tienen un número finito de elementos y siguen reglas matemáticas específicas. Juegan un rol fundamental en diferentes áreas de las matemáticas, ciencias de la computación y criptografía.

Importancia de los Campos Finitos y Ciencias de la Computación y Criptografía:

1. Corrección de Errores y Codificación de Datos

   • Los Campos finitos juegan un rol crucial en los códigos de corrección de errores, donde son usados para codificar y decodificar datos y corregirlos durante la transmisión.

2. Criptografía:

   • En la criptografía moderna, los campos finitos son usados para definir curvas elípticas, las cuales forman la fundación de la criptografía elíptica curva (elliptic curve cryptography, ECC). ECC es enormemente usado en comunicaciones seguras y firmas digitales por su gran seguridad y eficiencia.
   • Los campos finitos también son usados en Bitcoin y otras criptomonedas. Estos usan campos finitos como bloques de construcción fundamentales para varios componentes cruciales.

3. Teoría de Códigos:

   • Los campos finitos son fundamentales en la teoría de códigos, los cuales resuelven errores de detección y corrección de códigos usados en el almacenamiento de datos, comunicación y comprensión.

4. Funciones Hash Criptográficas:

   • Los Campos Finitos son utilizados en las funciones hash criptográficas, las cuales son funciones de una vía que mapean los datos de tamaños arbitrarios a valores hash de tamaños fijos. Estas funciones son vitales para asegurar la integridad y autenticidad de los datos.

5. Generación de Números Pseudo Aleatorios:

   • Los campos finitos son usados en ciertos algoritmos para la generación de números pseudo aleatorios, los cuales son aplicados en simulaciones, juegos y en protocolos criptográficos.

6. Teoría Galois

   • Los Campos Finitos están conectados con la teoría Galois, una rama de álgebra abstracta. La teoría Galois provee una visión a las propiedades finitas y sus extensiones.

7. Proceso de Señales Digitales:

   • Los Campos Finitos son usados en ciertas aplicaciones en el proceso de señales digitales como la corrección de errores en los datos de audio e imágenes.

En este blog, intentaré implementar campos finitos en Rust.

Campos Finitos

Definición de Campos Finitos

Formalmente, un campo finito es definido como un conjunto de elementos junto a dos operaciones binarias, + (suma) y * (multiplicación), que satisface ciertas propiedades. El número de elementos en un campo finito es llamado por orden, denotado por p, donde p es un número primo. El campo finito es denotado por Fp.

Propiedades Básicas de los Campos Finitos:

• Cierre: el resultado de la suma y multiplicación de cualquiera de los elementos en el campo finito, también pertenece al campo finito. En otras palabras: los campos finitos están cerrados bajo la suma y multiplicación.

Por ejemplo: Si a y b están en el conjunto, a + b y a* b también están.

• Suma: los Campos Finitos forman un grupo Abeliano bajo la suma. Esto quiere decir que la suma es conmutativa (a+b=b+a), asociativa (a+(b+c)=(a+b)+c) y tiene un elemento de identidad (0) como a+0=a para cualquier elemento en el campo. Adicionalmente, cada elemento tiene una suma inversa (-a) como la de a+(-a)=0.

• Multiplicación: los elementos no-cero de un campo finito de un grupo forman un Abeliano bajo la multiplicación. Esto quiere decir que la multiplicación es conmutativa (a*b=b*a), asociativa (a*(b*c)=(a*b)*c), y tiene un elemento de identidad (1) como a*1=a para cualquier elemento no-cero en el campo. Adicionalmente, cada elemento no-cero tiene un inverso multiplicativo (a^-1) como el de a*a^-1=1.

• Suma inversa: si a está en el conjunto, -a está en el conjunto el cual es definido como el valor que hace a+(-a)=0.

• Multiplicación Inversa: si a está en el conjunto y nd no es 0, a^-1 está en el conjunto, el cual es definido como el valor que hace a*a^-a=1.

Implementación del Campo Finito en Rust

Elemento del Campo de Construcción

Primero, tenemos que crear una nueva estructura cuyo nombre es FieldElement.

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

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

// revisa que num esté entre 0 y el primo-1 inclusivo.
// si no, entrará en pánico.
if num >= prime {
panic!("Num {} not in field range 0 to {}", num, prime - 1);
}

Self {
num,
prime
}
}
}

// usa el rasgo PartialEq para revisar si dos campos son iguales o no
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);
}
}

Módulo de Aritmética

Una de las herramientas que podemos usar para hacer un campo finito cerrado bajo la suma, resta, multiplicación y división es algo llamado módulo de aritmética.

7%3=1

Creo que has aprendido en esta operación. Cuando la división no sea igual, habrá algo llamado el “recordatorio”, el cual es la cantidad restante sobre la división.

Veamos el código para saber cómo escribir el módulo de aritmética.

En Python:

print(7 % 3)
# 1

print(-27 % 13)
# 12

En Rust, generaremos otros resultados cuando calculemos con números negativos.

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

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

Así que necesitamos usar una dependencia especial para cuidar a la función módulo.

Esta vez, usaré esta caja módulo

[dependencies]
modulo = "0.1.2"

Suma y Resta

Luego, añadiremos la función add y la función sub.

Rust provee los rasgos de cada operación. Así que lo usaremos para eso.

impl Add for FieldElement {
type Output = Self;

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

// tienes que asegurarte que lo elementos están en los mismos campos finitos
if self.prime != rhs.prime {
panic!("cannot add two numbers in different Fields");
}
}

// la suma es el campo finito está definido con el operador del 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);
}
}

Multiplicación y Exponente

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);
}
}

Ya que Rust no tiene un rasgo de exponensión, definiremos la función 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);
}
}

División

Cuando viene la división del campo finito, es un poco difícil entenderlo la primera vez.
Podemos implementarlo así

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");
}

// usa el pequeño teorema de Fermat
// self.num.pow(p-1) % p == 1
// esto quiere decir:
// 1/n == pow(n, p-2, p) en 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);
}
}

Esas son todas las operaciones. Si te pierdes, puedes ver todo el código aquí.

Conclusión

En este blog, aprendimos sobre los campos finitos y cómo implementarlos en Rust. Usaré la estructura FieldElement en el siguiente Blog.

Te veo en el próximo Blog.

Este artículo es una traducción de aoi, hecha por Héctor Botero. Puedes encontrar el artículo original aquí.
Sería genial escucharte en nuestro Discord, puedes contarnos tus ideas, comentarios, sugerencias y dejarnos saber lo que necesitas.
Si prefieres puedes escribirnos a @web3dev_es en Twitter.