4. ユーティリティ関数

この文書のアルゴリズムでは、以下に示すユーティリティ関数に加え、標準的な算術演算（加算、乗算、モジュロ削減など）および楕円曲線点演算（点加算およびスカラー乗算）を使用します。

セキュリティのため、これらの関数の実装は定数時間（constant-time）であるべきです（SHOULD）。端的に言えば、これは実行時間やメモリアクセスパターンが、秘密の入力、中間値、または出力の値に依存してはならないことを意味します。このような定数時間の実装では、すべての算術、比較、および代入も定数時間で実装されなければなりません（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 において平方（square）である場合に True を返します。オイラーの基準により、この関数は定数時間で次のように計算できます。
```
is_square(x) := { True,  if x^((q - 1) / 2) is 0 or 1 in F;
                { False, otherwise.
```
一部の拡大体では、上記のべき乗よりも速く定数時間で is_square を計算できます。[AR13] と [S85] は、拡大体に対する最適化された方法を説明しています。付録 I.5 は、GF(p^2) に対する最適化された直線法（straight-line method）を示しています。
sqrt(x): sqrt 操作は多価関数です。すなわち、x が平方である限り（x = 0 の場合を除き）、体 F には x の2つの根が存在します。実装の互換性を維持しつつ実装者に最適化の余地を与えるため、この文書は sqrt() が特定の値を返すことを要求しません。代わりに、第6.4節で説明されているように、sqrt を呼び出す関数は正しい根を決定する方法も指定します。

平方根を計算する好ましい方法は、F に固有の決定論的アルゴリズムを固定することです。付録 I でいくつかのアルゴリズムを示します。
sgn0(x): この関数は x の「符号」を示す 0 または 1 を返します。sgn0(x) == 1 は x が「負」である場合のみです。（言い換えれば、この関数は常に 0 を正とみなします。）第4.1節でこの関数を定義し、その実装について説明します。
inv0(x): この関数は F における x の乗法逆元を返します。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 バイトのサブ文字列を返します。位置は 0 からインデックス付けされます。例えば、substr("ABCDEFG", 2, 3) == "CDE" です。
len(str): バイト文字列 str に対して、この関数は str の長さをバイト単位で返します。例えば、len("ABC") == 3 です。
strxor(str1, str2): バイト文字列 str1 と str2 に対して、strxor(str1, str2) は2つの文字列のビット単位の XOR を返します。例えば、strxor("abc", "XYZ") == "9;9"（この例の文字列は ASCII リテラルですが、strxor は任意のバイト文字列に対して定義されています）。この文書では、strxor は同じ長さの入力にのみ適用されます。

4.1. sgn0 関数

この節では、任意の体 F = GF(p^m) に適用される一般的な sgn0 の実装を定義します。また、F = GF(p) および F = GF(p^2) の場合の簡略化された実装も示します。

拡大体に対する sgn0 関数の定義は、体要素の多項式基底（polynomial basis）またはベクトル表現に依存し、入力要素のベクトル表現全体を反復処理します。その結果、sgn0 は多項式基底を定義するために使用される原始多項式に依存します。この基底の詳細については第8節を参照し、拡大体要素をベクトルとして表現することに関する議論については第2.1节を参照してください。

sgn0(x)

Parameters:
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).

Input: x, an element of F.
Output: 0 or 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) # Avoid short-circuit logic ops
7.   zero = zero AND zero_i
8. return sign

m == 1 の場合、sgn0 は大幅に簡略化できます。

sgn0_m_eq_1(x)

Input: x, an element of GF(p).
Output: 0 or 1.

Steps:
1. return x mod 2

m == 2 の場合は、わずかに複雑になります。

sgn0_m_eq_2(x)

Input: x, an element of GF(p^2).
Output: 0 or 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) # Avoid short-circuit logic ops
5. return s

4.1. sgn0 関数​

4.1. sgn0 関数