Вступ
У Cairo одним із ключових понять, які ми зустрінемо, є тип felt252, також відомий як елемент поля.
Цей тип представляє цілі числа в межах певного діапазону, визначеного великим простим числом $P$.
У цій вправі ми будемо працювати виключно з типом felt252, який є важливою частиною програмування мовою Cairo.
Тип felt252 у Cairo є скалярним типом, який використовується для представлення цілих чисел від 0 до $P - 1$, де $P$ позначає велике просте число, яке наразі дорівнює $( 2^{251} + 17 \cdot 2^{192} + 1 )$.
Цей тип гарантує, що всі арифметичні операції виконуються за модулем $P$, що відрізняє його від стандартних цілочисельних типів, які ми можемо зустріти в інших мовах програмування.
Cairo підтримує базові арифметичні операції зі значеннями felt252:
-
Додавання (
+): додає два значення felt252.
Якщо результат перевищує $P$, його зводять за модулем $P$.
-
Віднімання (
-): віднімає одне значення felt252 від іншого.
Якщо результат відʼємний, його коригують, щоб він залишався в діапазоні, додаючи кратне $P$.
-
Множення (
*): множить два значення felt252, а результат обчислюється за модулем $P$.
-
Ділення (
/): ділить одне значення felt252 на інше, гарантуючи, що результат задовольняє рівняння $( \frac{x}{y} \cdot y = x \mod P)$.
Вказівки
У цій вправі ми допомагаємо криптографу керувати захищеною системою звʼязку та перевіряти її.
Система значною мірою покладається на елементи поля, зокрема на тип felt252 у Cairo, щоб усі арифметичні операції залишалися в межах визначеного діапазону.
1. Обчислити суму двох повідомлень
Два зашифровані повідомлення, кожне з яких представлено як felt252, потрібно додати одне до одного, щоб отримати обʼєднане повідомлення.
Однак через шифрування будь-який результат, що перевищує максимальне значення $P - 1$, потрібно загорнути за допомогою остачі від ділення на $P$.
Реалізуйте функцію, яка приймає два значення felt252 і повертає їхню суму, гарантуючи, що результат залишається в допустимому діапазоні:
add_messages(3618502788666131213697322783095070105623107215331596699973092056135007822949, 987654321)
// => 123456789
Примітка: Повернене значення має бути felt252.
2. Обчислити різницю між двома повідомленнями
Іноді повідомлення потрібно відняти, щоб відновити початкові дані.
Якщо результат віднімання відʼємний, система автоматично коригує його, додаючи $P$, щоб повернути в діапазон допустимого значення felt252.
Реалізуйте функцію, яка приймає два значення felt252 і повертає їхню різницю, гарантуючи, що результат залишається в допустимому діапазоні:
subtract_messages(123456789, 987654321)
// => 3618502788666131213697322783095070105623107215331596699973092056135007822949
Примітка: Повернене значення має бути felt252.
3. Обчислити допустимий добуток двох повідомлень
Щоб забезпечити цілісність зашифрованих даних, криптографічна система часто перемножує два повідомлення (felt252), щоб їхній добуток залишався в допустимому діапазоні.
Результат потрібно обчислити за остачею від ділення на $P$, щоб він залишався в допустимому діапазоні.
Реалізуйте функцію, яка приймає два значення felt252 і повертає їхній добуток, гарантуючи, що результат залишається в допустимому діапазоні:
multiply_messages(382927772233671078546147897004315551461400594453673204174697055647611, 9449570)
// => 123456789
Примітка: Повернене значення має бути felt252.
Навчальна вправа
