$Z_p$上 2048bit 大数运算的实现

本仓库存放的是中山大学计算机学院 2024 年秋季学期现代密码学实验课程实验 0-3 大数运算的 C++ 实现。详细的代码讲解请移步我的博客：大数运算实现

bigint.cpp是以uint32_t[]来存储大数的版本。bigint_v2.cpp是以uint64_t[]来存储大数的版本，且只保留效率最高的运算实现。

实验描述

实验背景

大数指的就是大小超过了 uint64_t 这样的基础类型的数。在密码学中使用上百甚至上千 bit 的数进行运算是非常常见的。

本次实验需要实现 $Z_p$ 下的大数加法、减法、乘法、求逆和模幂运算。

输入输出

大数输入输出均以十进制给出。

输入

1. 首先是输入数据的组数 $n$
2. 然后是一个大素数 $p$ ，二进制下不超过 2048bit
3. 接下来若干组 $a, b$ 的值，表示要运算的数。

例如：

2
1145141919810517

128014342154867
73305753838378

2945478099466
881966433589367

输出

对于每一组 $a, b$ ，要依次输出 $a+b, a-b, a*b, a^{-1}, a^b \mod p$ 的值。每个结果占一行，每组结果之间要以一个空行间隔。

例如：

201320095993245
54708588316489
708748188613332
728762940246710
653941837266743

884911911688833
266120964320616
557591223743365
148811383706628
1089569121185614