4. 工具函数 (Utility Functions)

本文档中的算法使用下述工具函数，外加标准算术运算（加法、乘法、模约减等）和椭圆曲线点运算（点的加法和标量乘法）。

出于安全性考虑，这些函数的实现 SHOULD 为常量时间（constant time）：简而言之，这意味着执行时间和内存访问模式 SHOULD NOT 依赖于秘密输入、中间值或输出的值。对于这类常量时间实现，所有算术运算、比较和赋值 MUST 也以常量时间实现。第 10.3 节简要讨论了常量时间安全性问题。

关于实现底层操作（无论是常量时间还是其他）的指导超出了本文档的范围；读者应查阅标准参考资料 [MOV96] [CFADLNV05]。

CMOV(a, b, c)：如果 c 为 False，CMOV 返回 a；否则返回 b。对于常量时间实现，该操作必须在与 c 的值无关的时间内运行。
AND、OR、NOT 和 XOR 是标准按位逻辑运算符。对于常量时间实现，必须避免短路运算符。
is_square(x)：当值 x 在域 F 中是平方元时，该函数返回 True。根据欧拉准则，该函数可在常量时间内计算为

is_square(x) := { True,  若 x^((q - 1) / 2) 在 F 中为 0 或 1；
                { False, 否则。

在某些扩张域中，is_square 的常量时间计算可比上述幂运算更快。[AR13] 和 [S85] 描述了针对扩张域的优化方法。附录 I.5 给出了 GF(p^2) 的一个优化的直线式方法。

sqrt(x)：sqrt 运算是一个多值函数，即只要 x 是平方元（x = 0 时除外），在域 F 中就存在 x 的两个根。为了在跨实现保持兼容的同时，给予实现者优化的余地，本文档不要求 sqrt() 返回某个特定值。相反，如第 6.4 节所解释的，任何调用 sqrt 的函数也会规定如何确定正确的根。

计算平方根的首选方式是固定一个针对 F 特定的确定性算法。我们在附录 I 中给出若干算法。

sgn0(x)：该函数返回 0 或 1，指示 x 的"符号"，其中当且仅当 x 为"负"时 sgn0(x) == 1。（换言之，该函数总是将 0 视为正。）第 4.1 节定义该函数并讨论其实现。
inv0(x)：该函数返回 x 在 F 中的乘法逆元，并通过规定 inv0(0) == 0 将其扩展到整个 F 上。以常量时间实现 inv0 的一种直接方式是计算

inv0(x) := x^(q - 2)。

注意，在输入为 0 时，输出按要求为 0。某些域可能允许更快的求逆方法；对此类方法的详细讨论超出了本文档的范围。

I2OSP 和 OS2IP：这些函数用于按照 [RFC8017] 的描述，在字节串与非负整数之间进行转换。（注意这些函数以大端字节序（big-endian）处理字节串。）
a || b：表示字节串 a 和 b 的连接。例如，"ABC" || "DEF" == "ABCDEF"。
substr(str, sbegin, slen)：对于字节串 str，该函数返回从位置 sbegin 开始、长度为 slen 字节的子串；位置从零开始编号。例如，substr("ABCDEFG", 2, 3) == "CDE"。
len(str)：对于字节串 str，该函数返回 str 的字节长度。例如，len("ABC") == 3。
strxor(str1, str2)：对于字节串 str1 和 str2，strxor(str1, str2) 返回两个字符串的按位异或。例如，strxor("abc", "XYZ") == "9;9"（此例中的字符串是 ASCII 字面量，但 strxor 对任意字节串都有定义）。在本文档中，strxor 仅应用于等长输入。

4.1. sgn0 函数 (The sgn0 Function)

本节定义一个适用于任意域 F = GF(p^m) 的通用 sgn0 实现。同时给出 F = GF(p) 和 F = GF(p^2) 情况下的简化实现。

扩张域的 sgn0 函数定义依赖于域元素的多项式基或向量表示，并迭代输入元素的整个向量表示。因此，sgn0 依赖于用于定义多项式基的本原多项式；关于该基的更多信息见第 8 节，关于将扩张域元素表示为向量的讨论见第 2.1 节。

sgn0(x)

Parameters:
- F, 特征为 p、阶为 q = p^m 的有限域。
- p, F 的特征（见上）。
- m, F 的扩张次数，m >= 1（见上）。

Input: x, F 的一个元素。
Output: 0 或 1。

Steps:
1. sign = 0
2. zero = 1
3. for i in (1, 2, ..., m):
4.   sign_i = x_i mod 2
5.   zero_i = x_i == 0
6.   sign = sign OR (zero AND sign_i) # 避免短路逻辑运算
7.   zero = zero AND zero_i
8. return sign

当 m == 1 时，sgn0 可大幅简化：

sgn0_m_eq_1(x)

Input: x, GF(p) 的一个元素。
Output: 0 或 1。

Steps:
1. return x mod 2

m == 2 的情况只是略微复杂一些：

sgn0_m_eq_2(x)

Input: x, GF(p^2) 的一个元素。
Output: 0 或 1。

Steps:
1. sign_0 = x_0 mod 2
2. zero_0 = x_0 == 0
3. sign_1 = x_1 mod 2
4. s = sign_0 OR (zero_0 AND sign_1) # 避免短路逻辑运算
5. return s

4.1. sgn0 函数 (The sgn0 Function)​

4.1. sgn0 函数 (The sgn0 Function)