密码学考试计算器使用指南

0.前言

无论是何种加密体制，其加密和解密过程往往需要一定的计算量。考虑到这一点，密码学相关的考试一般允许携带计算器以辅助计算。然而，现在常见的科学计算器一般为计算连续函数设计，对密码学所需的离散数学计算支持甚少。并且密码学教学过程中常假定计算执行的平台是计算机而非考试使用的普通科学计算器，导致课程中提及的计算优化方法不一定适用于考试。考虑到上述种种困境，本文介绍了一些密码学考试中的计算器使用方法，希望能够减轻密码学考试带来的计算方面的痛苦。

本文基于广泛使用的Casio fx-991CN X计算器进行介绍，其官方说明书可以从这里获得。

1. 约定与基础知识

对于某个计算机算法，我们往往以其复杂度来衡量其优劣。若我们以相同的方法衡量算法在计算器上的执行效果，则会发现两个问题：

1. 复杂度衡量的是数据极大时计算量的增长情况，但我们的数据常常没有那么大。
2. 复杂度衡量的是计算机的计算次数，而我们更关心计算时需要输入的字符量，因为输入会占据计算的大部分时长。

因此，我们以输入的算式条数作为复杂度衡量依据。此处不适用字符数是考虑到字符数难以准确计数，且每个人使用习惯不同，相同的算式也有多种不同的方式进行输入。

计算器通常有一定精度的限制，超出部分会被省略，本文以10位有效数字为例。注意这并不意味着计算器只能处理10¹⁰以内的数字，过大的数字会被转化为科学计数法。

 ÷ R是一个一般不常用但在本文中十分重要的运算符，它类似于Python中的divmod函数，可以同时返回除法的商和余数，例如5 ÷ R3 = 1, R = 2.若无特殊说明，后文 mod  计算均使用此运算符实现。如果 ÷ R的结果需要进行下一步计算或被赋值到寄存器，它仅会返回商，例如(5÷R3) × 2 = 1 × 2 = 2。如果希望计算余数，则可以使用 $a =a-p(a ) $.

FACT可以将整数进行质因数分解。但需注意你需要先获得一个结果（按下等于按键），然后才能进行质因数分解,质因数分解的结果也不会被保存在历史记录中。

计算器常会提供寄存器以储存计算过程中的中间结果。本文以大写字母A至F表示这些寄存器，以a → A表示寄存器赋值操作。

:可以用于连接多个算式，计算时每个算式会被依次计算并输出结果。我们可以使用其与寄存器结合构造多条语句的循环。需要注意:在历史记录中会被保存为多条算式，导致无法被复用。同时输入时需要注意第一条算式不能是合法的语句，否则会被直接执行，可以通过在算式开头加一个 ×来绕过。

2.快速幂优化

在课程中，快速幂算法往往被等同于平方-乘算法，这事实上并不全面。我们也可以实现类似的“立方-乘算法”。

def cubic_exponentiation(base, exponent, modulus):
    result = 1
    base = base % modulus  # 先对底数取模
    
    while exponent > 0:
        # 如果当前最低位是1
        if exponent % 3 == 1:
            result = (result * base) % modulus
        elif exponent % 3 == 2:
            result = (result * base * base) % modulus
        
        # 指数右移（除以3）
        exponent = exponent // 3
        # 计算base的立方
        base = (base * base * base) % modulus
    
    return result

使用计算器计算时，我们可以使用“m次方-乘”算法，其中m可以被动态确定。我们希望用一条算式计算尽可能大的次方结果，但这受到有效数字位数的限制。容易知道，计算时，想要获得不损失精度的结果，需要一次计算的a^m < 10¹⁰即取$m = \lfloor\frac{10}{\log_{10}{a}}\rfloor$.当然我们并不需要真的使用上式进行计算，直接计算 a^k ,根据结果直接估算就可以获得较好的效果。

例如计算 13²⁰ mod  23

直接计算 13²⁰ ≈ 1.90 × 10²²

估算 13⁸ < 10¹⁰,计算13⁸ ÷ R23 = 35466553, R = 2

考虑 13²⁰ = 13^{8 * 2 + 4},计算 (13⁴*2²) ÷ R23 = 4976, R = 3

最终解得 13²⁰ mod  23 = 3

如果使用传统的“平方-乘”算法，则需要依次计算 13², 13⁴, 13⁸, 13¹⁶ ,无疑是费时费力的。

也可以使用多条算式连接进行快速暴力计算 $$C+1\to C:B\times a-p\times(B\times a \div R p)\to B:\sqrt{k-C-1}$$

其中 a是底数， k是指数， p是模数，初始时 0 → C, 1 → B.然后快速按动 =, 直到提示数学错误时，查看 B的值即为答案。如果确信不会多按或少按，也可以去掉用于计数的 C。

3.逆元计算优化

计算逆元通常使用扩展欧几里得算法，不幸的是计算器在此过程中几乎毫无用处。因此，我们考虑以下计算方法计算a在模n下的逆元。

考虑欧拉定理 a^ϕ(n) = 1 (mod  n)

稍作变换 a × a^{ϕ(n) − 1} = 1 (mod  n)

即 a⁻¹ = a^{ϕ(n) − 1} (mod  n)

其中欧拉函数常需要这样计算 $$\phi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\cdots(1-\frac{1}{p_m})$$ 其中，p₁, p₂, …, p_m 是 n 的所有不同质因数

计算时，先使用FACT功能分解质因数，然后计算欧拉函数值，最后计算a^{ϕ(n) − 1} mod  n（可能需要使用快速幂算法）

例如计算75⁻¹ mod  97

发现97是一个素数 ϕ(97) = 97 − 1 = 96

然后计算 75^{ϕ(97) − 1} = 75⁹⁵ (mod  97)

考虑 75 ≈ 10², 95 = 5 * 19,先计算 75⁵ mod  97 = 75

考虑 75⁹⁵ = (75⁵)¹⁹ = 75¹⁹ = (75⁵)³ × 75⁴ = 75³ × 75⁴ = 75⁵ * 75² = 75³ (mod  97)

再计算 75³ mod  97 = 22

因此 75⁹⁵ mod  97 = 22

校验 75 × 22 = 1 (mod  97),正确解得 75⁻¹ = 22 (mod  97)

对于a或n较小（不需要使用快速幂）的情况下，该算法固定需要三行算式，考虑快速幂的复杂度也仅为O(logn),与传统扩展欧几里得算法相当。

此外，我们也可以使用表格快速穷举找到逆元。使用表格计算以下函数 f(x) = a × x − p × ((a×x)÷Rp)

找到 $f(x)=1 $对应的 x即为答案。