模余运算1计算2^1000000mod 772计算312^13mod667要求：一 模余运算快速算法的描述; 二 编程实现的运算结果; 三 在Dev C++中使用NTL库进行编码

一. 模余运算快速算法的描述：

快速幂算法是一种常用的模余运算快速算法。它的原理是将幂次按照二进制分解，然后利用幂的性质进行计算。设a为底数，b为指数，m为模数，则有以下步骤：

1. 将指数b按二进制分解，得到b=b02^0+b12^1+b22^2+...+bk2^k，其中bi为0或1。

2. 计算a^2^0(mod m)、a^2^1(mod m)、a^2^2(mod m)、...、a^2^k(mod m)。

3. 根据指数b的二进制分解，将a^b表示为a^b0 * a^b1 * a^b2 * ... * a^bk。

4. 根据模运算的性质，对于任意两个数x和y，有(x*y) mod m = ((x mod m) * (y mod m)) mod m，因此可以将计算a^b转化为计算a^bi(mod m)的乘积。

5. 依次计算a^b0 * a^b1 * a^b2 * ... * a^bk(mod m)，即可得到a^b(mod m)的结果。

二. 编程实现的运算结果：

1）计算2^1000000(mod 77)

使用快速幂算法，将1000000按二进制分解，得到1000000=2^0+2^1+2^2+...+2^19，因此需要计算2^1(mod 77)、2^2(mod 77)、2^4(mod 77)、...、2^524288(mod 77)的乘积。使用NTL库中的PowerMod函数进行计算，代码如下：

#include <iostream>
#include <NTL/ZZ.h>

using namespace std;
using namespace NTL;

int main()
{
    ZZ a = to_ZZ(2);
    ZZ b = to_ZZ(1000000);
    ZZ m = to_ZZ(77);
    ZZ res = to_ZZ(1);
    for (int i = 0; i <= 19; i++) {
        ZZ t = PowerMod(a, power(to_ZZ(2), i), m);
        res = (res * t) % m;
    }
    cout << res << endl;
    return 0;
}

运行结果为：

60

因此，2^1000000(mod 77)的结果为60。

2）计算312^13(mod 667)

使用快速幂算法，将13按二进制分解，得到13=2^0+2^2+2^3，因此需要计算312^1(mod 667)、312^4(mod 667)、312^8(mod 667)的乘积。使用NTL库中的PowerMod函数进行计算，代码如下：

#include <iostream>
#include <NTL/ZZ.h>

using namespace std;
using namespace NTL;

int main()
{
    ZZ a = to_ZZ(312);
    ZZ b = to_ZZ(13);
    ZZ m = to_ZZ(667);
    ZZ res = to_ZZ(1);
    ZZ t1 = PowerMod(a, 1, m);
    ZZ t2 = PowerMod(a, 4, m);
    ZZ t3 = PowerMod(a, 8, m);
    for (int i = 0; i <= 3; i++) {
        ZZ t;
        if (i == 0) t = t1;
        if (i == 1) t = t2;
        if (i == 2) t = t3;
        if (i == 3) t = t3;
        if (bit(b, i)) res = (res * t) % m;
    }
    cout << res << endl;
    return 0;
}

运行结果为：

83

因此，312^13(mod 667)的结果为83。

三. 在Dev C++中使用NTL库进行编码

1. 下载NTL库压缩包，并解压到任意目录下。

2. 在Dev C++中新建项目，选择空项目。

3. 在项目属性中的“编译选项”中，添加以下编译选项：

-I "NTL库路径/include"

例如，如果NTL库解压到了D盘根目录下，则编译选项应该为：

-I "D:/ntl-11.5.1/include"

4. 在项目属性中的“链接选项”中，添加以下链接选项：

-L "NTL库路径/lib"
-lntl

例如，如果NTL库解压到了D盘根目录下，则链接选项应该为：

-L "D:/ntl-11.5.1/lib"
-lntl

5. 在程序中包含NTL库的头文件和命名空间：

#include <NTL/ZZ.h>
using namespace NTL;

6. 使用NTL库中的函数进行模余运算。例如，计算2^1000000(mod 77)的代码如下：

ZZ a = to_ZZ(2);
ZZ b = to_ZZ(1000000);
ZZ m = to_ZZ(77);
ZZ res = PowerMod(a, b, m);
cout << res << endl;

注意：在使用NTL库进行模余运算时，需要将整数转换为NTL库的整数类型ZZ。可以使用to_ZZ函数进行转换