Polynomial Smash Ktya udon 3 Fixop - PDF 無料ダウンロード

Theoretical Science Group

300............................... 1 2 Polynomial Smash................................... Ktya 2........................................ udon 3 Fixophony.................................... molcul 4 Arrows............................ 6...................... tkys 8 9.......................... wleaf 9.......................... kobae964 12 ii TSG No. 300

, 1,2 TSG 40,.. TSG 300,. TSG No. 300 1

Polynomial Smash Polynomial Smash Ktya TSG Ktya TSG Polynomial Smash ipad Prime Smash! () () Z[X] (2) ()Z 2 TSG No. 300

udon,,.,,.,,, TEX Knuth,...,,.,. 1.,. 2.,,..,. () 3.,,,,. ( ),. 4.,.,,.,.. Visual C++/DX (, 1995) TSG No. 300 3

Fixophony Fixophony molcul TSG molcul = (fix) (phony) 3 fixophony Space BeatMark Beat- Mark BeatMark () BeatMark BeatMark, BeatMark BeatMark 1 BeatMark 3 3 3 2, 1 4 TSG No. 300

Fixophony, 2 5 1 4 Fixophony 4 F ail(), F air(), F ine(), F eat() F ine F eat F ail 0 F air TSG No. 300 5

Arrows Arrows Arrows 6 TSG No. 300

Arrows TSG No. 300 7

tkys websocket Flash HTML5 websocket SPDY http2.0 websocket ruby em-websocket ( php ) CSS3 jquery animate CSS3 Flash websocket CSS3 HTML5 & CSS3 8 TSG No. 300

wleaf 3DCG 3D 3D ( NARUTO ) CG () CG ( 3 ) 5 for ( ) 2 (1000 TSG No. 300 9

(a) (b) ) (c) (d) 3D DirectX SDK X 10 TSG No. 300

3D (e) (f) TSG No. 300 11

kobae964. M q. q 0 q < 1, r, s Z, 0 r < s M q = r s.,r, s q?, ε q, nε q < (n + 1)ε n,.(n ),ε = 1/(M(M 1)) q. : r 1 /s 1, r 2 /s 2, r 1 r 2 s 1 s 2 = r 1 s 2 r 2 s 1 s 1 s 2 1 lcm(s 1, s 2 ) 1 M(M 1) = ε, nε q < (n + 1)ε, nε r s < (n + 1)ε. 12 TSG No. 300

, M = 2 m (m Z), ε = 1 M(M 1) 1 M 2 = 2 2m,q 2m.,q = r/s r, s,. (m = log 2 M ),m = log 2 M.,. q,. s max,s ( M)..(floor(2.5) = 2, floor( 2.8) = 3) 1. y 0, q. 2. a 00, 0. 3. a 10, 1. 4. n 0. 5. 6. 12.. 6. z n := y n floor(y n ) 7. z n < 0.5/s max 2 a 1n 8. y n+1 1/z n 9. a 1(n+1) floor(y n+1 )a 1 + a 0 10. a 1(n+1) s max a 1n 11. a 0(n+1) a 1n 12. n 1 13. 6. ( ) floor(y) y, q = r/s s.. q = r/s(r, s ). (: q s/r..),6. 12.. u n = floor(y n ), y n = c n /d n (c n, d n ), y n+1 = 1 y n floor(y n ) = 1 = c n /d n u n d n c n u n d n TSG No. 300 13

, ( ( c n+1 d n+1 a 0(n+1) a 1(n+1), n ( ) ( 1) n+1 c n+1 = ( 1) n+2 d n+1 ) ( ) ( ) 0 1 c n = 1 u n d n ) ( ) ( ) 0 1 a 0n = 1 u n+1 a 1n ( 0 1 1 u n ) ( ( 1) n c n ( 1) n+1 d n )., n, ( ) ( 1) n+2 c n+2 a 0(n+1) = ( 1) n+3 d n+2 a 1(n+1) ( 0 1 1 u n+1 ) ( ( 1) n+1 c n+1 ( 1) n+2 d n+1 a 0n a 1n ), ( 1) n+2 c n+2 ( 1) n+3 d n+2 a 0(n+1) a 1(n+1) = ( 1) ( 1) n+1 c n+1 ( 1) n+2 d n+1 a 0n a 1n, ( 1) 1 c 1 a 00 ( 1) 2 d 1 a 10 = s 0 d 1 1 = s, ( 1) n+1 c n+1 ( 1) n+2 d n+1 a 0n a 1n = ( 1)n+1 s (8.1)., n,y n = floor(y n ), d n = 1. y n+1, c n+1, d n+1, (c n+1, d n+1 ) = (d n, c n d n ) = (1, 0), (8.1), ( 1) n+1 a 0n 0 a 1n = ( 1)n+1 s a 1n = s., s s. (i)s = 1 14 TSG No. 300

1 6. floor(y) = floor(q) = q,z = 0. 0 < 0.5/s 2 max. (ii)s < s s.s = s q = ts + g(t,g,0 < g < s ),floor(y) = t,6. z = y t = g/s. g/s 1/s max > 0.5/s 2 max,. 8. y 1/z = s /g. 9. a 2 floor(y)a 1 + a 0., s = ug + v(u,v ),floor(s /g) = u, a 2 = ua 1 + a 0. 10. (),11. 12. a 0 a 1, a 1 a 2,,6. 12. y,,.,.,.,.,.,, 0, 101, ψ.,. 1bit c 0, c 1 c 0 2 + c 1 2 = 1, c 0 0 + c 1 1,1bit bit (). c 0, c 1, 0, 1.( 1bit 2.) 1 z,a = cz, b = dz, a 0 + b 1 c 0 + d 1 ( bit ). bit, (). : c 0 2 0, c 1 2 1.() TSG No. 300 15

bit, 0 0,1 1 ( ).,, ( ). ()2= 2 1 U, (U U ) UU = U U = E 2,. c 0 0 + c 1 1, ( ) ( ) x c 0 = U y, bit x 0 + y 1., bit.,. (i-i) (X ) bit c 0 0 + c 1 1, c 1 0 + c 0 1. ( 1:,. 2.) ( 2: bit 0, 1, 1, 0. bit, c 0 0 + c 1 1 (c 0 0, c 1 0), 0, 1.) ( 3:.) (i-ii) bitc 0 0 + c 1 1, c 1 ( ) 0 1 σ x = 1 0 c 0 + c 1 2 0 + c 0 c 1 2 1, (Hadamard). ( ( ) U = 1 1 1 2 1 1.) (i-iii)y 16 TSG No. 300

σ y :. (i-iv)z σ z : ( ) 0 i σ y = i 0 σ z = ( 1 0 0 1 ). Conditional Phase. 2bit (2bit ) bit, c 00, c 01, c 10, c 11,. c 00 2 + c 01 2 + c 10 2 + c 11 2 = 1 c 00 00 + c 01 01 + c 10 10 + c 11 11 bit,. (): c 00 2 00, c 01 2 1, c 10 2 10, c 11 2 11. bit 1bit () 1bit,1bit. (, 1bit ): c 00 2 + c 10 2 0, c 01 2 + c 11 2 1. 0 c 00 00 + c 10 10 c00 2 + c 10 2 = c 00 c00 2 + c 10 2 00 + c 10 c00 2 + c 10 2 10.,1 c 01 01 + c 11 11 c01 2 + c 11 2 = c 01 c01 2 + c 11 2 01 + c 11 c01 2 + c 11 2 11.( bit, bit ) TSG No. 300 17

1bit 2bit: 1bit ψ, ϕ ψ = a 0 + b 1, ϕ = c 0 + d 1, 2bit, ψ ϕ = (a 0 + b 1 ) (c 0 + d 1 ) = ac 00 + ad 01 + bc 10 + bd 11. bit. ( 01 0 1 ) 2bit,. ()4= 2 2 U UU = U U = E 2,. c 00 00 + c 01 01 + c 10 10 + c 11 11, x c 00 y z = U c 01 c 10 w, bit x 00 + y 01 + z 10 + w 11.,. (ii-1) NOT(cNOT) bit 1 ( 10, 11 ), bit, NOT(Controlled- NOT)., x 00 + y 01 + z 10 + w 11 c 11. ( x 00 + y 01 + w 10 + z 11 1 0 0 0 U = 0 1 0 0 0 0 0 1 0 0 1 0.) 18 TSG No. 300

3bit. (iii-i) NOT(ccNOT) 2bit 11 1bit. 110 111, 111 110 n-bit() :,2 n. bit. : (iv-i)conditional Phase α. nbit 1 111 11, α (e iα ),Conditional Phase(CPhase ). n = 1, U = ( 1 0 0 e iα. n = 2 1 0 0 0 U = 0 1 0 0 0 0 1 0 0 0 0 e iα. ) () 2bit ψ ψ = (a 0 + b 1 ) (c 0 + d 1 ) = ac 00 + ad 01 + bc 10 + bd 11 (,a 0 + b 1, c 0 + d 1 bit, a 2 + b 2 = 1, c 2 + d 2 = 1 TSG No. 300 19

)., bit. ψ (0, : ac 2 + bc 2 = c 2 ) (1, : ad 2 + bd 2 = d 2 ) ac 00 + bc 10 ac 2 + bc 2 a 00 + b 10 = (a 0 + b 1 ) 0 ad 00 + bd 10 ad 2 + bd 2 a 00 + b 10 = (a 0 + b 1 ) 0 (, ac 2 + bc 2, ad 2 + bd 2 0. 0 0 ). bit.,2bit 1bit, bit ()., ϕ. ϕ = 00 + 11 2 = 1 2 00 + 1 2 11 2 1bit. ϕ bit., (0, 0.5) 00 (1, 0.5) 11,, bit., ( ϕ bit bit). +,. : ψ, ϕ, U, au ψ + bu ϕ = U(a ψ + b ϕ ).,, ψ ( ϕ 1 + ϕ 2 ) = ψ ϕ 1 + ψ ϕ 2 ( ψ 1 + ψ 2 ) ϕ = ψ 1 ϕ + ψ 2 ϕ. 20 TSG No. 300

(:, M n = {0, 1,, 2 n 1}( 2 n ) = Z/2 n (, )., 2. (1)2 000, 10101, 111 (2)10 0, 21, 7, ),.() (,() 00 00, 01 10, 10 01, 11 11.), nbit 2 n bit,, n.,, (M n M n ),., f(m) = f(n),f U U m = f(m), U n = f(n),u m = U 1 f(m) = U 1 f(n) = n,m = n. (),,.,. m, n (1 ),f M m M n., f : M m M n M m M n (x, y) (x, y + f(x) mod 2 n ).( f 1 : (x, y) (x, y f(x) mod 2 n ) ) TSG No. 300 21

,.,. Conditional NOT 1bit ψ, m-bit c, c 1 ψ.( c ). (i)m = 1 c ψ NOT. (ii)m = m,m = m + 1 1bit q. c m -bit Conditional NOT. q ( c 1bit) ψ ccnot., q, q (), q c ψ,. Conditional Increment n-bit bit ψ,m-bit bit c, c 1 1.(m 1, 1 ) m = 1, c = 1, n = 1 x 0 + y 1 y 0 + x 1,n = 2 x 00 + y 01 + z 10 + w 11 w 00 + x 01 + y 10 + z 11.,. (i)n = 1 NOT(X ). (ii)n = n,n = n + 1 ( d [e, f], bit d e-bit f-bit((f e + 1)bit) ( 0 ). d [e] d [e, e]. d bit d.) ψ [1, n ] ψ [0] Conditional NOT. ψ [1, n ] ψ ( c ), n = n Conditional increment. 22 TSG No. 300

lt (less than ) (lt(a, b, f, j )).n-bit a, b,a < b f,. bit,b, bit (, ).,(n 1)-bit j (j junk ) bit. j ( bit ). : (: j bit 1.) (i) bit. a 0bit (, a[0] ) 1 cnot( b [0] j [0]), σ x ( b [0]), cnot( b f ) 3.,b[0] 1 j[0] 1, a j[0] 0. a[0] 0, σ x ( b [0]), cnot( b [0] j [0]) 2. (ii) bit. i = 1, 2,, n 2 a[i], b[i].,j[0, i 1] bit 1, j[i 1] 1, 2 cnot( b [0] j [0]) ccnot( j [i 1] b [i] j [i]. (iii) bit. (ii), ccnot( j [i 1] b [i] j [i].(, )a[n 1] 0.., b!.() TSG No. 300 23

add (add( s, d )) m-bit s, n-bit d. 0. Conditional increment s bit. muxadd (muxadd(a 0, a 1, c, d )) n-bit a 0, a 1 ( bit ), 1bit c n-bit d,c 0 a 0,c 1 a 1,. Conditional increment bit. addn (addn(a, n, b, f, s )) (a+b) mod n, s, a+b n f., (f, b) = (0, 0),, (0, n a 1) (f, s) = (0, a),, (0, n 1) (f, b) = (0, n a),, (0, n 1) (f, s) = (1, 0),, (1, b 1) (f, b) = (1, 0),, (1, n a 1) (f, s) = (1, a n + 2 b ),, (1, 2 b 1) (f, b) = (1, n a),, (1, n 1) (f, s) = (0, n),, (0, n + a 1),f 0., j ((n 2)-bit). f (lt bit, s [0] ).,lt(n a, b, f, s [1, s 1])., cnot( f f ),f f., lt 1 (n a, b, f, s [1, s 1]) (), s ( 0 )., muxadd(a, 2 b + a n, f, s ), add( b, s ). s.( f ) 24 TSG No. 300

oaddn (overwriting addn ) (oaddn(a, n, s )) s a (s ). 1bit f. s -bit j ( (a + b) mod n )., addn(a, n, s, f, j ), σ x ( f ), addn 1 (n a, n, s, f, j ).. muln (muln(a, n, b, p )) p (0 ) a b mod n. omuln (omuln(a, n, p )) p a,n. a, n. oaddn. expn (expn(a, n, b, x = 0 ) x 1, a b,n.a, n.,b bit,x a 2? 1.. (DFT). ψ = ψ 0 ψ 1 ψ n 1 ( ψ j 0 1, ψ.,ψ = 2 n 1 ψ 0 + 2 n 2 ψ 1 + + 2 1 ψ n 2 + ψ n 1.) TSG No. 300 25

, = 0 k n 1,j k =0,1 = ψ = ( exp 2πψ(2n 1 j 0 + 2 n 2 j 1 + 2 1 j n 2 + j n 1 ) = 0 k n 1,j k =0,1 0 k n 1,j k =0,1 exp 2 n ( ) exp 2πψ(2n 1 j 0 ) j 0 exp 2 n ( 2πψ(21 j n 2 ) 2 n 2 n 1 j=0 exp( 2πψj 2 n ) j ) j 0 j 1 j n 1 ( 2πψ(2 n 2 j 1 ) 2 n ) ( j n 2 exp 2πψj n 1 2 n ) j 1 ) j n 1 exp( 2π 0.ψ n 1 j 0 ) j 0 exp( 2π 0.ψ n 2 ψ n 1 j 1 ) j 1 exp( 2π 0.ψ 1 ψ 2 ψ n 1 j n 2 ) j n 2 exp( 2π 0.ψ 0 ψ 1 ψ n 1 j n 1 ) j n 1 ().,,. (:n = 5 1 5 3 + 9 + 15 + 21 + 27 ) ) bit, r, 0, 1 2 n /r, 2 2 n /r,, (r 1) 2 n /r r. ( 0, 5, 11, 16, 21, 27 6, 0, 5, 11, 16, 21, 27 ), (Shor)., ().,a r 1 (mod N) r (), r N. N(). N = 15. 26 TSG No. 300

1. 2n-bit ψ, n-bit ϕ.(n < 2 n )( n = 4) 2.ψ,2 2n.( 2n-bit 0 ),.(. ) ψ = 1 2 n ( 0 + 1 + + 22n 1 ) ψ = 1 ( 0 + 1 + + 255 ) 16 3. x,2 x < N.x N.(, ) ( x N,(φ(N) 1)/(N 1) (φ, 1 N 1,N ). N = 15 1/2, N = pq(p q ) 1.) ( x = 2 ) 4.expn(x, N, ψ, ϕ )., ψ ϕ = 1 2 n ( 0 1 + 1 x + 2 x2 mod N + + 2 2n 1 x 2 2n 1 mod N ). ( ψ ϕ = 1 ( 0 1 + 1 2 + 2 4 + 3 8 + + 254 4 + 255 8 ) 16. 4. ϕ.,.,ϕ,a b = ϕ b, r ( ). a r 1 (mod N) ( ϕ = 8,2 b 8 (mod 15) b = 3, 7, 11, 15,, 251, 255, ψ ϕ = 1 8 ( 3 8 + 7 8 + + 255 8 ) = 1 ( 3 + 7 + + 255 ) 8 8, ψ r = 4 ) 5.DFT ψ., ψ 2 2n s/r TSG No. 300 27

. ( 0, 64, 128, 192 ) 6. ψ, 2 2n q.(q 2n )( q = 1/4 ) q = s/r r.(r = r φ(r)/r, ) ( r = r = 4 ) 7.r.r, x r 1 = (x r /2 1)(x r /2 + 1) 0 (mod N), r,r (r = r ), x r /2 ± 1 0 (mod N).,N x r /2 ± 1. ( x r /2 = 2 2 = 4, gcd(n, x r /2 1) = gcd(15, 3) = 3 gcd(n, x r /2 + 1) = gcd(15, 5) = 5,3,5.) 28 TSG No. 300

300 2012 11 16 THEORETICAL SCIENCE GROUP