l l 2018 08 27 2018 08 28 FFTPRSWS18 1 / 20
FCSR l LFSR NLFSR NLFSR Goresky Klapper FCSR l word-based FCSR l l... l 2 / 20
LFSR FCSR l a m 1 a m 2... a 1 a 0 q 1 q 2... q m 1 q m a = (a n) n 0 R m LFSR a n = q 1a n 1 + + q ma n m, n m. 3 / 20
FCSR FCSR l z div N mod N a m 1 a m 2... a 1 a 0 q 1 q 2... q m 1 q m a = (a n) n 0 S = {0, 1,..., N 1} m FCSR a n + Nz n = q 1a n 1 + + q ma n m + z n 1, n m. a n, q n S, z n Z. 4 / 20
l LFSR vs FCSR F 2 m LFSR S = {0, 1} m FCSR q 1,..., q m {0, 1} q 1,..., q m {0, 1} a(x) F 2[[x]] 2 α Z 2 a(x) = a 0 + a 1x + a 2x 2 + α = a 0 + a 12 + a 22 2 + q(x) F 2[x] q(x) = 1 + q 1x + + q mx m a(x) = h(x)/q(x) q Z q = 1 + q 12 + + q m2 m α = h/q a n = Tr(Aω n ) a n = A2 n (mod q) (mod 2) M Berlekamp Massey l 5 / 20
l FCSR FCSR a = (a n) n 0 S = {0, 1,..., N 1} m FCSR q 1 f a i N i = f q Z N i=0 a = (a n) n 0 2 a = (a n) n 0 q f 0. 3 q < f < 0 gcd (f, q) = 1 a = (a n) n 0 ord q N. Definition (l ) q = p t p a ord q N = φ (q) a l q l q 1 6 / 20
l l Theorem (l ) a = (a n) n 0 l q = p t p t 1 Z r b S r a b µ (b) t = 1 p p µ (b) + 1 N r N r t 2 p t p t 1 N r N r p t 1 µ (b) N r q l p t 1 N r + 1 7 / 20
l FCSR l 1 N = 2 N = 2 e e CPU Lee Park 2011 2 N = 2 e, e 3 l q (q 1)/2 Definition ( l ) q a (q 1)/2 a l N = 2 e, e 3 l 8 / 20
l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = 603679, (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v 0 1 2 3 4 5 6 7 µ (v) 19034 18829 18998 18882 19032 18848 18679 18901 v 8 9 10 11 12 13 14 15 µ (v) 18829 19051 18882 18698 18848 18732 18901 18695 Theorem (Gu 2016) µ (v) q 1 2N < q 1 2q + (q1/2 + 1) 2 ( 4 0.608 log q + 0.38 + + 0.116 ) π2 q q 2 (s n, s n+τ ), (s n, s n+1, s n+2) 9 / 20
l Gu Klapper SETA 2014 µ (v) q 1 2N 1 ( ( )) q 1 1 + log (q 1/2 + 1) 2 2 Wang Tan ISIT 2015 µ (v) q 1 ( ( ) ) 1 q 1 2N π log + 0.3 (q 1/2 + 1) + q 1 2 2q Gu 2016 µ (v) q 1 2N < q 1 2q + (q1/2 + 1) 2 q 1/2 log q ( 4 0.608 log q + 0.38 + + 0.116 ) π2 q q 2 Pólya Vinogradov µ (v) (q 1)/2N q 1/2 log q 10 / 20
l Pólya Vinogradov Theorem (Pólya Vinogradov 1918) p c m+n ( ) i cp 1/2 log p, p i=m m, n > 0 Z µ (v), v 0, N 1 { { µ (v) =# v + Nj j 0, 1,..., q + 1 } ( ) v + Nj N 1, q = = 1 2 q+1 N 1 j=0 { 1 2 q+1 N 1 j=0 (( v + Nj q ( N 1 v + j q ) )} + 1 } = 1 ) + q + 1 2N. 11 / 20
FCSR l N, q l FCSR 12 / 20
l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = 603679, (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v 0 1 2 3 4 5 6 7 µ (v) 19034 18829 18998 18882 19032 18848 18679 18901 v 15 14 13 12 11 10 9 8 µ (v) 18695 18901 18732 18848 18698 18882 19051 18829 19034 18829 18998 18882 19032 18848 18679 18901 + 18695 18901 18732 18848 18698 18882 19051 18829 37729 37730 37730 37730 37730 37730 37730 37730 37730 = (603679 + 1)/16 = (q + 1)/N. Theorem ( ) { (q + 1)/N 1 if v = 0, N 1 µ (v) + µ (N 1 v) = (q + 1)/N otherwise 13 / 20
l N = 2 3 = 8, m = 5, q = 1 + N + 3N 2 + 3N 4 + 5N 5 = 176327, (a 0, a 1, a 2, a 3, a 4; z) = (3, 2, 4, 1, 0; 5). v 00 01 02 03 04 05 06 07 µ (v) 10909 10982 10982 11059 10982 11059 11059 11131 µ(1) = µ(2) = µ(4), µ(3) = µ(5) = µ(6)? N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = 603679, (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v 0 1 2 3 4 5 6 7 µ (v) 19034 18829 18998 18882 19032 18848 18679 18901 v 15 14 13 12 11 10 9 8 µ (v) 18695 18901 18732 18848 18698 18882 19051 18829 µ(1) = µ(8), µ(3) = µ(10), µ(5) = µ(12), µ(7) = µ(14)? µ(1) = µ(n/2)? 14 / 20
l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = 603679, (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). a n 00 01 02 03 04 05 06 07 a n 9 5 14 1 13 2 11 15 n 08 09 10 11 12 13 14 15 a n 0 11 15 1 12 6 9 1 v 8 v N 1 v b n 00 01 02 03 04 05 06 07 b n 6 5 1 1 2 2 4 0 n 08 09 10 11 12 13 14 15 b n 0 4 0 1 3 6 6 1 v 0 1 2 3 4 5 6 7 µ (v) 37729 37730 37730 37730 37730 37730 37730 37730 15 / 20
l S = {0, 1,..., N/2 1} f : S S { v if v S f (v) = N 1 v otherwise. N l a = (a n) n 0 N/2 b = (b n) n 0 b n = f (a n), n 0 b (q 1)/2 b v µ (v) { µ (q + 1)/N 1 if v = 0 (v) = (q + 1)/N otherwise... 16 / 20
l x (1) = (x n (1) ) n 0, x (2) = (x n (2) ) n 0 T M ω = e 2πi/M C τ {0, 1,..., T 1} T 1 R x (1),x (2)(τ) = i=0 ω x(1) x (2) i i+τ x (1) x (2) R x (1),x(2)(τ) x := x (1) = x (2) R x(τ) := R x,x(τ) R x(0) = T 17 / 20
l N = 8, m = 3, q = 3167 a b 18 / 20
FCSR l l l l 19 / 20
FCSR l 20 / 20