Segment 4：Introduction Number Theory——Arithmetic algorithms【算术算法】：链接

这是整个数论简介的内容，下面是这个的主目录如下，其链接为：https://blog.csdn.net/qq_43479839/article/details/119079620

Segment 4目录@xyi

• Segment 4：Introduction Number Theory——Arithmetic algorithms【算术算法】：链接
• • 4.1 第一个问题：如何在计算机里表示大整数【Representing bignums】？
  • • 1、看算术【Arithmetic】操作会花多少时间
    • 2、求幂的问题【Exponentiation】
    • 3、The repeated squaring alg.【重复平方算法】
    • 4、小结一下在ZN中n位加法减法，乘法，指数运算运行时间

这节我们会讨论质数模与合数模的加法、乘法个指数算法【addtion and multiplication and exponentiation alorithms, modulo primes and composites】

4.1 第一个问题：如何在计算机里表示大整数【Representing bignums】？

假设我们有一台64位的计算机，想在这64位的机器上表示一个n位大整数（如 n=2048）；
1> 我们把想表示的大数进行分割，32位一组，然后我们就有n/32个分组，它们可以表示这个数，我们想把它存储在计算机上，【一般情况下你会使用长于32位的分组】，在这里使用32位，是因为想限制到32位，因为这样你可以把来个分组乘在一起而结果小于64位，

1、看算术【Arithmetic】操作会花多少时间

1、 Addition和Subtraction【加法和减法】：O(n);注意加法有进位，减法有借位；
2、 Multipication:O(n^2);不过Karatsuba发现其实乘法的运时间是O(n1.585);大致的想法如下，不过最好的算法时间可以降至位nlognD

3、 Division with remainder【带余除法】

2、求幂的问题【Exponentiation】

1> 假设我们有一个有限循环群【the finite cyclic group】，这意味着这个群是由生成元g的各个幂生成的；该群的阶数的幂记作为g^q；我们的目标是，给定这个生成元g以及某个指数x；我们的目标是计算gx；【一般x是一个很巨大的数，所以一个一个去乘显然不成熟】
2> 当x很大的时候，我们是否也能很快的计算出gx；显然是可以的；有一个算法叫做：重复平方算法【a repeated squaring algorithm】；算法的大概步骤如下：

g⁵³通过5次平方，再加上4次乘法；所以通过9步乘法，就算出了它；

3、The repeated squaring alg.【重复平方算法】

1> 这个算法需要说明一下的是：我们需要俩个寄存器，y叫做平方运算的寄存器；z叫做累加寄存器
2> 其中这个算法循环的次数是log2X；【取决于x的位数】；但是时间复杂度如下：

4、小结一下在ZN中n位加法减法，乘法，指数运算运行时间

在这个里面只要提一个地方：就是对于指数，需要logX次循环，我们说过乘法的时间是n的平方，因为这个算法里面有俩个乘法，所以运行时间将会是n2logx【指数运算其实很慢】