研究背景，目的
初期値の条件
系列の周期長と双曲線構造
.
.
有限体上のロジスティック写像による生成系列
に対する長周期を保証するための条件
†
土屋和由
†
‡
野上保之
株式会社光電製作所
‡
岡山大学工学部
2014 年 09 月 04 日 政策研究大学院大学
日本応用数理学会 2014 年度年会
研究部会 OS：数論アルゴリズムとその応用 (2)
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 背景 1：有限体上の写像から生成される系列
. p を奇素数，f (x) ∈ Fp [x] とする．F : Fp → Fp を多項式写
像 F (x) = f (x) とする．再帰式 Xi+1 = F (Xi ) によって定ま
る系列 {Xi } に対して，長周期を保証するための条件は？
.2 deg f (x) ≦ 2 の場合，
1
{Xi } が最大周期長 p を持つ ⇔ f (x) = x + c (c ̸= 0)
. f (x) = ax + b （線形）の場合，
{Xi } が周期長 p − 1 を持つ
(1)（パラメータ条件） ：a は F×
p における原始根
⇔
(2)（初期値条件）
：X0 は不動点ではない
3
.
問題
.
deg f (x) = 2 の場合に，長周期が保証されるパラメータ及び初期
値の条件を与えよ．
.
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 背景 2：カオス性に基づく系列
. カオス的な振る舞いを乱数性の根拠とする二値系列に関する
研究が行われている．
1
テント写像を利用する系列
ロジスティック写像を利用する系列 ← 研究対象
. ロジスティック写像は 2 次関数であるため，状態遷移の度に
2 倍の演算精度を必要とする．
2
浮動小数点演算による実装
整数上のロジスティック写像を利用する系列
. 素数を法とする演算を採用することにより，演算精度を一定
に保つ．
3
有限体上のロジスティック写像から生成される系列
.
本講演の目的
.
有限体上のロジスティック写像から生成される系列に対して，長
周期が保証されるパラメータ及び初期値の条件を与えること．
.
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 有限体上のロジスティック写像から生成される系列
.
Definition (有限体上のロジスティック写像)
.
p を奇素数とする．µp ∈ Fp に対して，写像 LMFp を，
LMFp : Fp
a
→ Fp
7→ µp a(a + 1)
と定義する．写像 LMFp を µp に関する Fp 上のロジスティック写像と
.呼び，µp をコントロールパラメータと呼ぶ．
.
本講演における研究対象
.
初期値 X0 ∈ Fp に対して，再帰式
Xi+1 = LMFp (Xi )
によって定まる系列 {Xi }i≧0 を研究対象とする．
.
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 先行研究と研究目標
. SCIS 2013：宮崎 - 荒木 - 上原 - 野上
1
有限体上のロジスティック写像から生成される系列を提案
した．
パラメータの選択に依存して，平均周期長の変動が大きいこ
とを数値実験により示した．
. JSIAM 2013：宮崎 - 荒木 - 上原 - 野上
2
safe prime を適用した場合に，平均周期長の変動が小さくな
ることを数値実験により示した．
. SCIS 2014：宮崎 - 荒木 - 上原 - 野上
3
doubly safe prime p を適用した場合に，周期長が (p − 3)/4
となる系列が存在することを数値実験から得られた予想から
示した．
.
研究目標
.
周期長が (p − 3)/4 となる系列が存在するためのパラメータ及び
.初期値の条件の解明（µp = 4 の場合）．
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 系列の状態遷移例
.
Example (p = 23, µp = 4)
.
丸で囲まれている値：平方剰余 ̸= 0 ∈ Fp .
四角で囲まれている値：平方非剰余.
.
三角で囲まれている値：= 0 ∈ Fp .
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 初期値集合
初期値集合
QHyp
{
( )
(
)
}
LMFp (a)
a
a ∈ Fp |
= 1,
=1
p
p
{
( )
}
a
−1
=
a ∈ Fp |
= 1, #LMFp (a) = 2
p
(
)
}
{
( )
a+1
a
= 1,
=1
=
a ∈ Fp |
p
p
=
.
研究項目
.
1. #QHyp = ? ← 最大周期長に直結
2. LM
Fp |QHyp の簡潔な記述 ? ← 周期長の解析に直結
.
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 初期値集合と双曲線構造
a ∈ QHyp に対して，∃b, c ∈ Fp s.t. a = b 2 , a + 1 = c 2 .
よって，C : x 2 − y 2 = 1 を Fp 上の双曲線とすると，(c, b) ∈ C (Fp ).
一方，C (Fp ) の任意の元は，t ∈ Fp − {0} に対して，
)
(
))
( (
1
1
1
1
t+
,
t−
2
t
2
t
と表される．特に，#C (Fp ) = p − 1.
したがって，全射写像
Φ : Fp − {0, 1, p − 1}
→
t
7→
QHyp
{ (
)}2
1
1
t−
2
t
が定義出来る．
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 初期値集合の元の個数
.
Theorem (初期値集合 QHyp の元の個数)
.
p ≧ 5 を p ≡ 3 mod 4 を満たす素数とする．
このとき，写像 Φ は 4 : 1 の写像となり，
#QHyp =
p−3
4
が成立する．
.
.
注意（4 : 1 対応）
.
t ∈ Fp − {0, 1, p − 1} に対して，
Φ(t) = Φ(−t) = Φ(t −1 ) = Φ(−t −1 )
が成立する．
.
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. ロジスティック写像の簡易表現
.
Lemma (ロジスティック写像のパラメータ空間における対応)
.
a ∈ QHyp とする．t ∈ Fp − {0, 1, p − 1} を Φ(t) = a を満たす元とす
る．このとき，Φ(t 2 ) = LMFp (a) が成立する．すなわち，
パラメータ空間ではロジスティ
ック写像は 2 乗写像に対応する．
.
証明
{ (
)}2
{ (
)}2
1
1
1
1
t−
, a+1=
t+
より，
2
t
2
t
{ (
)}2 { (
)}2
1
1
1
1
LMFp (a) = 4a(a + 1) = 4 ×
t−
×
t+
2
t
2
t
{
(
(
)
)}2
1
1
1
1
=
2×
t−
×
t+
2
t
2
t
{ (
)}2
1
1
=
t2 − 2
= Φ(t 2 ).
2
t
a = Φ(t) =
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 長周期を保証するための条件
.
Theorem (系列の周期長)
.
p = 2q + 1（q は奇素数）を safe prime，LMFp を µp = 4 に関する Fp
上のロジスティック写像，{Xi } を LMFp によって生成される系列とす
る．X0 ∈ QHyp と仮定する．このとき，系列 {Xi } の周期長は
(1) ordq (2) が偶数ならば ordq (2)/2
(2) ordq (2) が奇数ならば ordq (2)
となる．ただし，
ordq (2) は 2 の F×
q における位数を表す．
.
.
Corollary (系列の周期保証)
.
定理の条件の下で，以下の条件 (1) または (2) を満たすとする．
(1) ordq (2) = q − 1.
(2) ordq (2) = (q − 1)/2 かつ (q − 1)/2 が奇数．
このとき，系列 {Xi } の周期長は (p − 3)/4 (= (q − 1)/2) となる．
.特に，p が doubly safe prime のとき，条件 (1) または (2) を満たす．
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. まとめと課題
. 有限体上のロジスティック写像から生成される系列に対して，
長周期を保証するためのパラメータ及び初期値の条件を提示
し，理論的保証を与えた．
.2 主結果は，宮崎 - 荒木 - 上原 - 野上（SCIS 2014）の実験的
1
結果を系として含む．
. 初期値集合を双曲線と関連付けることが鍵となる．特に，ロ
ジスティック写像の初期値集合への制限は，双曲線のパラ
メータ空間において 2 乗写像で表現される．
.4 より一般のパラメータに対して，本結果を一般化することが
課題である．
3
「ロジスティック写像」の枠組みでは一般化は困難？
「双曲線」との関連に注目すれば一般化は可能？
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
研究背景，目的
初期値の条件
系列の周期長と双曲線構造
. 謝辞
.
謝辞
.
.ご清聴ありがとうございました．
土屋和由, 野上保之
有限体上のロジスティック写像による生成系列
© Copyright 2024 ExpyDoc
