有限域 $F_{2^{131}}$ 上的运算实现

本仓库存放的是中山大学计算机学院 2024 年秋季学期现代密码学实验课程实验 2-1 有限域运算的 C 语言实现。详细的代码讲解请移步我的博客：有限域运算实现

实验描述

实验背景

有限域 $F_{2^{132}}$ ，给定不可约多项式 $f(x)=x^{131}+x^{13}+x^2+x+1$。

$F_{2^{132}}$ 中的每个元素形如 $a_0+a_1x+a_2x^2+\dots+a_{130}x^{130}$ ，其中 $a_i\in{0, 1}$ 。

所以在计算机中，我们只需要 131 位的比特串即可表示该有限域中的一个元素。用一个uint64_t[3]表示时，如下所示：

uint64_t[2]	uint64_t[1]	uint64_t[0]
$000\dots0a_{130}a_{129}\dots a_{128}$	$a_{127}a_{126}\dots a_{64}$	$a_{63}a_{62}\dots a_{0}$

考虑到两个多项式运算的结果，最多用 262 位就可以表示。所以本次实验中，全部使用uint64_t[5]来进行存储。

输入输出

实验的输入输出均为小端序的二进制数据。

输入：

1. 首先是一个uint32_t，表示需要进行的运算数量

2. 接下来是若干个运算操作，每个运算操作由以下两个部分组成：

   • 一个uint8_t，表示要进行的运算的类型：
     • 0x00 表示对两个多项式做加法
     • 0x01 表示对两个多项式做乘法
     • 0x02 表示对第一个多项式平方
     • 0x03 表示对第一个多项式求逆
   • 一个uint64_t[2][3]，表示两个多项式

例如：

04 00 00 00

00
05 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
21 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

01
05 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
21 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

02
05 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
21 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

03
05 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
21 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

注：为了方便查看，这里以 16 进制书写，且加入了换行。实际输入文件是二进制数据，且除了数据外，不存在换行符等。

真实的样例可以查看input1.bin和input2.bin两个文件。

输出：

每一个运算操作都需要输出一个uint64_t[3]结果，未使用的高位需要全部设为 0，不需要输出换行符。

上面的样例对应的输出是：

24 20 00 00 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

AB 10 04 02 00 00 00 00
00 00 00 00 00 00 00 00
04 00 00 00 00 00 00 00

11 00 00 04 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00

7F 01 DD 8A ED DA 46 92
42 EF 37 99 F4 D0 F9 0D
03 00 00 00 00 00 00 00

对应的输出可以查看output1.bin和output2.bin两个文件

使用到的库

• <stdio.h>：标准输入输出库，用于文件操作和打印输出。
• <stdint.h>：标准整数类型库，定义了固定宽度的整数类型，如本代码中频繁使用的uint64_t。
• <immintrin.h>：包含了 Intel 的 SIMD 指令集（SSE2 和 PCLMULQDQ）的头文件，用于加速计算。
• <time.h>：时间库，用于获取当前时间戳，进行性能分析。

函数介绍

• gf_print()：以形如 $x^{130} + x^{129} + \dots$ 格式输出多项式。
• gf_add()：有限域下的加法。
• gf_mul()：有限域下的乘法，共有gf_mul_trivial(), gf_mul_bit(), gf_mul_smid()三种实现，可以通过宏进行选择最终使用的版本。
• gf_pow()：有限域下的乘方运算，共有gf_pow_trivial(), gf_pow_fast()两种实现，可以通过宏进行选择最终使用的版本。
• gf_pow2()：有限域下的平方运算，共有gf_pow2_bit(), gf_pow2_mul(), gf_pow2_simd()三种实现，可以通过宏选择最终使用的版本。
• gf_inv()：有限域下的求逆运算，共有gf_inv_euclid(), gf_inv_fermat()两种实现，可以通过宏选择最终使用的版本。
• degree()：计算多项式的度数。多项式为 0 时，返回-1。
• left_shift()：实现以 64 位整数数组表示的二进制数的左移。
• now()：获取当前时间戳。用在test_mul_time(), test_pow2_time(), test_inv_time()三个函数中，进行性能分析。以上四个函数仅供参考，在不同环境和语言标准下可能需要修改。

常量

• M：该有限域元素的最大项数
• F[3]：该有限域的不可约多项式