Introdução
Em Cairo, um dos conceitos centrais que vais encontrar é o tipo felt252, também conhecido como elemento de corpo.
Este tipo representa números inteiros dentro de um intervalo específico definido por um número primo grande $P$.
Neste exercício, vais trabalhar exclusivamente com o tipo felt252, que é uma parte essencial da programação em Cairo.
O tipo felt252 em Cairo é um tipo escalar usado para representar números inteiros de 0 até $P - 1$, em que $P$ é um número primo grande, atualmente definido como $( 2^{251} + 17 \cdot 2^{192} + 1 )$.
Este tipo garante que todas as operações aritméticas são efetuadas módulo $P$, o que o torna diferente dos tipos inteiros habituais que podes encontrar noutras linguagens de programação.
O Cairo suporta operações aritméticas básicas com valores felt252:
-
Adição (
+): soma dois valores felt252.
Se o resultado exceder $P$, é reduzido módulo $P$.
-
Subtração (
-): subtrai um valor felt252 a outro.
Se o resultado for negativo, é ajustado para se manter dentro do intervalo, somando-lhe um múltiplo de $P$.
-
Multiplicação (
*): multiplica dois valores felt252, com o resultado calculado módulo $P$.
-
Divisão (
/): divide um valor felt252 por outro, garantindo que o resultado satisfaz a equação $( \frac{x}{y} \cdot y = x \mod P)$.
Instruções
Neste exercício, vais ajudar um criptógrafo a gerir e a verificar um sistema de comunicação seguro.
O sistema depende fortemente de elementos de corpo, mais concretamente do tipo felt252 em Cairo, para garantir que todas as operações aritméticas se mantêm dentro de um intervalo definido.
1. Calcular a Soma de Duas Mensagens
Há duas mensagens encriptadas, cada uma representada como um felt252, que têm de ser somadas para criar uma mensagem combinada.
No entanto, por causa da encriptação, qualquer resultado que ultrapasse o valor máximo $P - 1$ tem de dar a volta com o módulo $P$.
Implementa uma função que recebe dois valores felt252 e devolve a respetiva soma, garantindo que o resultado se mantém dentro do intervalo válido:
add_messages(3618502788666131213697322783095070105623107215331596699973092056135007822949, 987654321)
// => 123456789
Nota: O valor devolvido deve ser um felt252.
2. Calcular a Diferença Entre Duas Mensagens
Por vezes, é preciso subtrair mensagens para recuperar os dados originais.
Se o resultado da subtração for negativo, o sistema ajusta automaticamente o resultado somando $P$, para o trazer de volta ao intervalo de um valor felt252 válido.
Implementa uma função que recebe dois valores felt252 e devolve a respetiva diferença, garantindo que o resultado se mantém dentro do intervalo válido:
subtract_messages(123456789, 987654321)
// => 3618502788666131213697322783095070105623107215331596699973092056135007822949
Nota: O valor devolvido deve ser um felt252.
3. Calcular um Produto Válido de Duas Mensagens
Para garantir a integridade dos dados encriptados, o sistema criptográfico multiplica muitas vezes duas mensagens (felt252), de modo a garantir que o produto se mantém dentro de um intervalo válido.
O resultado tem de ser calculado módulo $P$, para garantir que permanece dentro do intervalo válido.
Implementa uma função que recebe dois valores felt252 e devolve o respetivo produto, garantindo que o resultado se mantém dentro do intervalo válido:
multiply_messages(382927772233671078546147897004315551461400594453673204174697055647611, 9449570)
// => 123456789
Nota: O valor devolvido deve ser um felt252.
Exercício de aprendizagem
