半系列における記号の出現度数の対称性

Size: px

Start display at page:

Download "半系列における記号の出現度数の対称性"

へいぞうみのしま
5 years ago
Views:

1 l l FFTPRSWS18 1 / 20

2 FCSR l LFSR NLFSR NLFSR Goresky Klapper FCSR l word-based FCSR l l... l 2 / 20

3 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 q ma n m, n m. 3 / 20

4 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 q ma n m + z n 1, n m. a n, q n S, z n Z. 4 / 20

5 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 q(x) F 2[x] q(x) = 1 + q 1x + + q mx m a(x) = h(x)/q(x) q Z q = 1 + q q m2 m α = h/q a n = Tr(Aω n ) a n = A2 n (mod q) (mod 2) M Berlekamp Massey l 5 / 20

6 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

7 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 / 20

8 l FCSR l 1 N = 2 N = 2 e e CPU Lee Park 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

9 l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = , (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v µ (v) v µ (v) Theorem (Gu 2016) µ (v) q 1 2N < q 1 2q + (q1/2 + 1) 2 ( log q ) π2 q q 2 (s n, s n+τ ), (s n, s n+1, s n+2) 9 / 20

10 l Gu Klapper SETA 2014 µ (v) q 1 2N 1 ( ( )) q log (q 1/2 + 1) 2 2 Wang Tan ISIT 2015 µ (v) q 1 ( ( ) ) 1 q 1 2N π log (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 ( log q ) π2 q q 2 Pólya Vinogradov µ (v) (q 1)/2N q 1/2 log q 10 / 20

11 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

12 FCSR l N, q l FCSR 12 / 20

13 l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = , (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v µ (v) v µ (v) = ( )/16 = (q + 1)/N. Theorem ( ) { (q + 1)/N 1 if v = 0, N 1 µ (v) + µ (N 1 v) = (q + 1)/N otherwise 13 / 20

14 l N = 2 3 = 8, m = 5, q = 1 + N + 3N 2 + 3N 4 + 5N 5 = , (a 0, a 1, a 2, a 3, a 4; z) = (3, 2, 4, 1, 0; 5). v µ (v) µ(1) = µ(2) = µ(4), µ(3) = µ(5) = µ(6)? N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = , (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). v µ (v) v µ (v) µ(1) = µ(8), µ(3) = µ(10), µ(5) = µ(12), µ(7) = µ(14)? µ(1) = µ(n/2)? 14 / 20

15 l N = 2 4 = 16, m = 4, q = 1 + 2N + 6N 2 + 3N 3 + 9N 4 = , (a 0, a 1, a 2, a 3; z) = (9, 5, 14, 1; 7). a n a n n a n v 8 v N 1 v b n b n n b n v µ (v) / 20

16 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 / 20

17 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

18 l N = 8, m = 3, q = 3167 a b 18 / 20

19 FCSR l l l l 19 / 20

20 FCSR l 20 / 20

() x + y + y + x dy dx = 0 () dy + xy = x dx y + x y ( 5) ( s55906) 0.7. (). 5 (). ( 6) ( s6590) 0.8 m n. 0.9 n n A. ( 6) ( s6590) f A (λ) = det(a λi)

() x + y + y + x dy dx = 0 () dy + xy = x dx y + x y ( 5) ( s55906) 0.7. (). 5 (). ( 6) ( s6590) 0.8 m n. 0.9 n n A. ( 6) ( s6590) f A (λ) = det(a λi) 0. A A = 4 IC () det A () A () x + y + z = x y z X Y Z = A x y z ( 5) ( s5590) 0. a + b + c b c () a a + b + c c a b a + b + c 0 a b c () a 0 c b b c 0 a c b a 0 0. A A = 7 5 4 5 0 ( 5) ( s5590) () A ()

半 系列における記号の出現度数の対称性

半系列における記号の出現度数の対称性