4. 实用函数 (Utility Functions)

本文档中的算法使用下面描述的实用函数，以及标准算术运算（加法、乘法、模约简等）和椭圆曲线点运算（点加法和标量乘法）。

为了安全起见，这些函数的实现应该 (SHOULD) 是常数时间的：简而言之，这意味着执行时间和内存访问模式不应该 (SHOULD NOT) 依赖于秘密输入、中间值或输出的值。对于这种常数时间实现，所有算术运算、比较和赋值也必须 (MUST) 以常数时间实现。第 10.3 节简要讨论了常数时间安全问题。

有关实现低级操作（以常数时间或其他方式）的指导超出了本文档的范围；读者应参考标准参考资料 [MOV96] [CFADLNV05]。

CMOV(a, b, c): 如果 c 为 False，CMOV 返回 a；否则返回 b。对于常数时间实现，此操作必须以独立于 c 的值的时间运行。
AND、OR、NOT 和 XOR 是标准的按位逻辑运算符。对于常数时间实现，必须 (MUST) 避免短路运算符。
is_square(x): 此函数在值 x 是域 F 中的平方数时返回 True。根据欧拉判据 (Euler's criterion)，此函数可以在常数时间内计算为

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

在某些扩展域中，is_square 可以比上述指数运算更快地在常数时间内计算。[AR13] 和 [S85] 描述了扩展域的优化方法。附录 I.5 给出了 GF(p^2) 的优化直线方法。

sqrt(x): sqrt 运算是一个多值函数 (multi-valued function)，即，当 x 是平方数时，在域 F 中存在 x 的两个根（除非 x = 0）。为了在保持实现之间兼容性的同时允许实现者进行优化，本文档不要求 sqrt() 返回特定值。相反，如第 6.4 节所述，任何调用 sqrt 的函数还指定如何确定正确的根。

计算平方根的首选方法是固定特定于 F 的确定性算法。我们在附录 I 中给出了几种算法。

sgn0(x): 此函数返回 0 或 1，表示 x 的"符号"，其中 sgn0(x) == 1 表示 x 为"负"。（换句话说，此函数始终将 0 视为正。）第 4.1 节定义了此函数并讨论了其实现。
inv0(x): 此函数返回 x 在 F 中的乘法逆元，通过固定 inv0(0) == 0 扩展到整个 F。在常数时间内实现 inv0 的直接方法是计算

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

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

I2OSP 和 OS2IP: 这些函数用于将字节串转换为非负整数或从非负整数转换，如 [RFC8017] 中所述。（请注意，这些函数以大端字节顺序操作字节串。）
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)