10.5 有限体に関する函数のまとめ

10.5.1 setmod_ff

setmod_ff([p|defpoly2])

setmod_ff([defpolyp,p])

setmod_ff([p,n])

:: 有限体の設定, 設定されている有限体の法, 定義多項式の表示

return

数または多項式

p

素数

defpoly2

GF(2) 上既約な 1 変数多項式

defpolyp

GF(p) 上既約な 1 変数多項式

n

拡大次数

• 引数が正整数 p の時, GF(p) を基礎体として設定する.
• 引数が多項式 defpoly2 の時, GF(2^deg(defpoly2 mod 2)) = GF(2)[t]/(defpoly2(t) mod 2) を基礎体として設定する.
• 引数が defpolyp と p の時, GF(p^deg(defpolyp)) を基礎体として設定する.
• 引数が p と n の時, GF(p^n) を基礎体として設定する. p^n は 2^29 未満で なければならない. また, p が 2^14 以上のとき, n は 1 でなければならない.
• 無引数の時, 設定されている基礎体が GF(p)の場合 p, GF(2^n) の場合定義多項式を返す. 基礎体が setmod_ff(defpoly,p) で定義された GF(p^n) の場合, [defpoly,p] を返す. 基礎体が setmod_ff(p,n) で定義された GF(p^n) の場合, [p,defpoly,prim_elem] を返す. ここで, defpoly は, n 次拡大の定義多項式, prim_elem は, GF(p^n)の 乗法群の生成元を意味する.
• GF(2^n) の定義多項式は, GF(2) 上 n 次既約ならなんでも良いが, 効率に 影響するため, defpoly_mod2() で生成するのがよい.

[174] defpoly_mod2(100);
x^100+x^15+1
[175] setmod_ff(@@);
x^100+x^15+1
[176] setmod_ff();
x^100+x^15+1
[177] setmod_ff(x^4+x+1,547);
[1*x^4+1*x+1,547]
[178] setmod_ff(2,5);
[2,x^5+x^2+1,x]

参照

defpoly_mod2

10.5.2 field_type_ff

field_type_ff()

:: 設定されている基礎体の種類

return

整数

• 設定されている基礎体の種類を返す.
• 設定なしなら 0, GF(p) なら 1, GF(2^n) なら 2 を返す.

[0] field_type_ff();
0
[1] setmod_ff(3);
3
[2] field_type_ff();
1
[3] setmod_ff(x^2+x+1);
x^2+x+1
[4] field_type_ff();
2

参照

setmod_ff

10.5.3 field_order_ff

field_order_ff()

:: 設定されている基礎体の位数

return

整数

• 設定されている基礎体の位数 (元の個数) を返す.
• 設定されている体が GF(q) ならば q を返す.

[0] field_order_ff();
field_order_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] field_order_ff();
3
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] field_order_ff();
4

参照

setmod_ff

10.5.4 characteristic_ff

characteristic_ff()

:: 設定されている体の標数

return

整数

• 設定されている体の標数を返す.
• GF(p) の場合 p, GF(2^n) の場合 2 を返す.

[0] characteristic_ff();
characteristic_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] characteristic_ff();
3
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] characteristic_ff();
2

参照

setmod_ff

10.5.5 extdeg_ff

extdeg_ff()

:: 設定されている基礎体の, 素体に対する拡大次数

return

整数

• 設定されている基礎体の, 素体に対する拡大次数を返す.
• GF(p) の場合 1, GF(2^n) の場合 n を返す.

[0] extdeg_ff();
extdeg_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] extdeg_ff();
1
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] extdeg_ff();
2

参照

setmod_ff

10.5.6 simp_ff

simp_ff(obj)

:: 数, あるいは多項式の係数を有限体の元に変換

return

数または多項式

obj

数または多項式

• 数, あるいは多項式の係数を有限体の元に変換する.
• 整数, あるいは整数係数多項式を, 有限体, あるいは有限体係数に変換するために 用いる.
• 有限体の元に対し, 法あるいは定義多項式による reduction を行う場合にも 用いる.
• 小標数有限体の元に変換する場合, 一旦素体上に射影してから, 拡大体の 元に変換される. 拡大体の元に直接変換するには ptosfp() を 用いる.

[0] simp_ff((x+1)^10);
x^10+10*x^9+45*x^8+120*x^7+210*x^6+252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
[1] setmod_ff(3);
3
[2] simp_ff((x+1)^10); 
1*x^10+1*x^9+1*x+1
[3] ntype(coef(@@,10));
6
[4] setmod_ff(2,3);
[2,x^3+x+1,x]
[5] simp_ff(1);
@_0
[6] simp_ff(2);
0
[7] ptosfp(2);
@_1

参照

setmod_ff, lmptop, gf2nton, ptosfp, sfptop

10.5.7 random_ff

random_ff()

:: 有限体の元の乱数生成

return

有限体の元

• 有限体の元を乱数生成する.
• random(), lrandom() と同じ 32bit 乱数発生器を使用している.

[0] random_ff();
random_ff : current_ff is not set
return to toplevel
[0] setmod_ff(pari(nextprime,2^40));
1099511627791
[1] random_ff();
561856154357
[2] random_ff();
45141628299

参照

setmod_ff, random, lrandom

10.5.8 lmptop

lmptop(obj)

:: GF(p) 係数多項式の係数を整数に変換

return

整数係数多項式

obj

GF(p) 係数多項式

• GF(p) 係数多項式の係数を整数に変換する.
• GF(p) の元は, 0 以上 p 未満の整数で表現されている. 多項式の各係数は, その値を整数オブジェクト(数識別子 0)としたものに 変換される.

[0] setmod_ff(pari(nextprime,2^40));
1099511627791
[1] F=simp_ff((x-1)^10);
1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
+1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
[2] setmod_ff(547);                 
547
[3] F=simp_ff((x-1)^10);
1*x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
+45*x^2+537*x+1
[4] lmptop(F);
x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
+45*x^2+537*x+1
[5] lmptop(coef(F,1));
537
[6] ntype(@@);
0

参照

simp_ff

10.5.9 ntogf2n

ntogf2n(m)

:: 自然数を GF(2^n) の元に変換

return

GF(2^n) の元

m

非負整数

• 自然数 m の 2 進表現 m=m0+m1*2+...+mk*2^k に対し, GF(2^n)=GF(2)[t]/(g(t)) の元 m0+m1*t+...+mk*t^k mod g(t) を返す.
• 定義多項式による剰余は自動的には計算されないため, simp_ff() を 適用する必要がある.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=ntogf2n(2^100);
(@^100)
[3] simp_ff(N);
(@^13+@^12+@^11+@^10)

参照

gf2nton

10.5.10 gf2nton

gf2nton(m)

:: GF(2^n) の元を自然数に変換

return

非負整数

m

GF(2^n) の元

• gf2nton の逆変換である.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=gf2nton(2^100);
(@^100)
[3] simp_ff(N);
(@^13+@^12+@^11+@^10)
[4] gf2nton(N);
1267650600228229401496703205376
[5] gf2nton(simp_ff(N));
15360

参照

gf2nton

10.5.11 ptogf2n

ptogf2n(poly)

:: 一変数多項式を GF(2^n) の元に変換

return

GF(2^n) の元

poly

一変数多項式

• poly の表す GF(2^n) の元を生成する. 係数は, 2 で割った余りに 変換される. poly の変数に @ を代入した結果と等しい.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] ptogf2n(x^100);
(@^100)

参照

gf2ntop

10.5.12 gf2ntop

gf2ntop(m[,v])

:: GF(2^n) の元を多項式に変換

return

一変数多項式

m

GF(2^n) の元

v

不定元

• m を表す多項式を, 整数係数の多項式オブジェクトとして返す.
• v の指定がない場合, 直前の ptogf2n() 呼び出し における引数の変数 (デフォルトは x), 指定がある場合には 指定された不定元を変数とする多項式を返す.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=simp_ff(gf2ntop(2^100));
(@^13+@^12+@^11+@^10)
[5] gf2ntop(N);
[207] gf2ntop(N);
x^13+x^12+x^11+x^10
[208] gf2ntop(N,t);
t^13+t^12+t^11+t^10

参照

ptogf2n

10.5.13 ptosfp, sfptop

ptosfp(p)

sfptop(p)

:: 小標数有限体への変換, 逆変換

return

多項式

p

多項式

• ptosfp() は, 多項式の係数を, 現在設定されている小標数有限体 GF(p^n) の元に直接変換する. 係数が既に有限体の元の場合は変化しない. 正整数の場合, まず位数で剰余を計算したあと, 標数 p により p 進展開し, p を x に置き換えた多項式を, 原始元表現に変換する. 例えば, GF(3^5) は GF(3)[x]/(x^5+2*x+1) として表現され, その各 元は原始元 x に関するべき指数 k により @_k として 表示される. このとき, 例えば 23 = 2*3^2+3+2 は, 2*x^2+x+2 と表現され, これは結局 x^17 と法 x^5+2*x+1 で等しいので, @_17 と変換される.
• sfptop() は ptosfp() の逆変換である.

[196] setmod_ff(3,5);
[3,x^5+2*x+1,x]
[197] A = ptosfp(23);
@_17
[198] 9*2+3+2;
23
[199] x^17-(2*x^2+x+2); 
x^17-2*x^2-x-2
[200] sremm(@,x^5+2*x+1,3);
0
[201] sfptop(A);
23

参照

setmod_ff, simp_ff

10.5.14 defpoly_mod2

defpoly_mod2(d)

:: GF(2) 上既約な一変数多項式の生成

return

多項式

d

正整数

• ‘fff’ で定義されている.
• 与えられた次数 d に対し, GF(2) 上 d 次の既約多項式を返す.
• もし 既約 3 項式が存在すれば, 第 2 項の次数がもっとも小さい 3 項式, もし 既約 3 項式が存在しなければ, 既約 5 項式の中で, 第 2 項の次数がもっとも小さく, その中で第 3 項の次数がもっとも小さく, その中で第 4 項の次数がもっとも 小さいものを返す.

参照

setmod_ff

10.5.15 sffctr

sffctr(poly)

:: 多項式の小標数有限体上での既約分解

return

リスト

poly

有限体上の 多項式

• 多項式を, 現在設定されている小標数有限体上で既約分解する.
• 結果は, [[f1,m1],[f2,m2],...] なる リストである. ここで, fi は monic な既約因子, mi はその 重複度である.

[0] setmod_ff(2,10);
[2,x^10+x^3+1,x]
[1] sffctr((z*y^3+z*y)*x^3+(y^5+y^3+z*y^2+z)*x^2+z^11*y*x+z^10*y^3+z^11);
[[@_0,1],[@_0*z*y*x+@_0*y^3+@_0*z,1],[(@_0*y+@_0)*x+@_0*z^5,2]]

参照

setmod_ff, modfctr

10.5.16 fctr_ff

fctr_ff(poly)

:: 1 変数多項式の有限体上での既約分解

return

リスト

poly

有限体上の 1 変数多項式

• ‘fff’ で定義されている.
• 一変数多項式を, 現在設定されている有限体上で既約分解する.
• 結果は, [[f1,m1],[f2,m2],...] なる リストである. ここで, fi は monic な既約因子, mi はその 重複度である.
• poly の主係数は捨てられる.

[178] setmod_ff(2^64-95);
18446744073709551521
[179]  fctr_ff(x^5+x+1); 
[[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
[1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]

参照

setmod_ff

10.5.17 irredcheck_ff

irredcheck_ff(poly)

:: 1 変数多項式の有限体上での既約判定

return

0|1

poly

有限体上の 1 変数多項式

• ‘fff’ で定義されている.
• 有限体上の 1 変数多項式の既約判定を行い, 既約の場合 1, それ以外は 0 を返す.

[178] setmod_ff(2^64-95);
18446744073709551521
[179] ] F=x^10+random_ff();
x^10+14687973587364016969
[180] irredcheck_ff(F);  
1

参照

setmod_ff

10.5.18 randpoly_ff

randpoly_ff(d,v)

:: 有限体上の 乱数係数 1 変数多項式の生成

return

多項式

d

正整数

v

不定元

• ‘fff’ で定義されている.
• d 次未満, 変数が v, 係数が現在設定されている有限体に属する 1 変数多項式を生成する. 係数は random_ff() により生成される.

[178] setmod_ff(2^64-95);
18446744073709551521
[179] ] F=x^10+random_ff();
[180] randpoly_ff(3,x);
17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
[181] randpoly_ff(3,x);
7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
[182] randpoly_ff(3,x);
10247781277095450395*x^2+10243690944992524936*x+4063829049268845492

参照

setmod_ff, random_ff

10.5.19 ecm_add_ff, ecm_sub_ff, ecm_chsgn_ff

ecm_add_ff(p1,p2,ec)

ecm_sub_ff(p1,p2,ec)

ecm_chsgn_ff(p1)

:: 楕円曲線上の点の加算, 減算, 逆元

return

ベクトルまたは 0

p1 p2

長さ 3 のベクトルまたは 0

ec

長さ 2 のベクトル

• 現在設定されている有限体上で, ec で定義される楕円曲線上の 点 p1, p2 の和 p1+p2, 差 p1-p2, 逆元 -p1 を返す.
• ec は, 設定されている有限体が奇標数素体の場合, y^2=x^3+ec[0]x+ec[1], 標数 2 の場合 y^2+xy=x^3+ec[0]x^2+ec[1] を表す.
• 引数, 結果ともに, 無限遠点は 0 で表される.
• p1, p2 が長さ 3 のベクトルの場合, 斉次座標による曲線上の 点を表す. この場合, 第 3 座標は 0 であってはいけない.
• 結果が長さ 3 のベクトルの場合, 第 3 座標は 0 でないが, 1 とは限らない. アフィン座標による結果を得るためには, 第 1 座標, 第 2 座標を第 3 座標 で割る必要がある.
• p1, p2 が楕円曲線上の点かどうかのチェックはしない.

[0] setmod_ff(1125899906842679)$
[1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
[2] Pt1=newvect(3,[1,-412127497938252,1])$
[3] Pt2=newvect(3,[6,-252647084363045,1])$
[4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
[ 560137044461222 184453736165476 125 ]
[5] F=y^2-(x^3+EC[0]*x+EC[1])$
[6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
0
[7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
0
[8] D=ecm_sub_ff(Pt3,Pt2,EC);
[ 886545905133065 119584559149586 886545905133065 ]
[9] D[0]/D[2]==Pt1[0]/Pt1[2];
1
[10] D[1]/D[2]==Pt1[1]/Pt1[2];
1

参照

setmod_ff

この文書は4月 18, 2024にtexi2html 5.0を用いて生成されました。