研究背景,目的 初期値の条件 系列の周期長と双曲線構造 . . 有限体上のロジスティック写像による生成系列 に対する長周期を保証するための条件 † 土屋和由 † ‡ 野上保之 株式会社光電製作所 ‡ 岡山大学工学部 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