|
|
|
- たつぞう なぐも
- 5 years ago
- Views:
Transcription
1 15 2
2 Fermat Solovay-Strassen Miller-Rabin Lucas-Lehmer Frobenius-Grantham Proth-Pocklington-Lehmer-Selfridge(PPLS) Kraitchik-Lehmer Elliptic Curve Primality Proving (ECPP) Cohen-Lenstra Agrawal-Kayal-Saxena-Lenstra(AKSL) AKS Random Choice Incremental Search FIPS DSS Shawe-Taylor Maurer
3 Miller-Rabin RSA DSA ANSI FIPS CRYPTREC CMVP
4 RSA. DSA.. RSA. e-japan. RSA RSA 3 4 PC. RSA. 1.2 URL R. Crandall C. Pomerance [19] H. C. Williams [69]. ANSI RSA DSA 4
5 , 1. n, Cond i ( i =1, 2,...)..,, Cond i. 1. 1, t Cond i, probable prime ( ). n Cond i ( n. Cond i ). ( ) n (false witness) ([23]. [43] liar. ). 1, (1) (c pp) ( probable prime 1 probable prime,. 5
6 1 n, t probable prime composite 1: for i =1tot do 2: if n i Cond i then 3: composite. 4: end if 5: end for 6:,, probable prime. ), (2) ( ). [ ] n probable prime (c pp) := Prob n (1) ( { }) n max (2) n: Cond i, (2) (c pp), (c pp), (2), ( ) (c pp)., (1), (2) ( ) Fermat (F ) [3, 35, 43] 2.3 Solovay-Strassen (SS ) [35, 43, 65] 2.4 Miller-Rabin (MR ) [4, 7, 23, 35, 43, 46, 47, 59] 2.5 Lucas-Lehmer (LL ) [4, 5, 8, 19, 54, 55, 56, 60] 2.6 Frobenius-Grantham (FG ) [4, 29, 30, 51, 55] 1: Fermat Fermat 1 n, 1 a<n a ( gcd(a, n) 1) a n 1 1 mod n (3). 6
7 , Fermat., a Cond i 1 Fermat.,, O((log n) 3 ),. 1 n, (3) a(1 a<n) (Fermat-)., n a (Fermat-). n FW(n), #FW(n) ( # ). 2, Fermat n. 2 ([3]) n, #FW(n) =ϕ(n) n. ϕ(n) a (1 a<n,gcd(a, n) 1)., Fermat (2) (c pp),. n Carmichael., 561 = Carmichael. Fermat,,,. 2.3 Solovay-Strassen Fermat Carmichael Solovay-Strassen. Solovay-Strassen, (Euler ). 3 n, 1 a<n a ( gcd(a, n) 1), ( a a (n 1)/2 mod n (4) n). ( a n) Jacobi. ( ) a n p, Jacobi p / a, x 2 a mod p 1 x<p p 1, 1, p a 0. n = p e i i, ( ) ( ) ei ( a n = a p i. Jacobi a n) (1 a<n), O((log n) 3 ) ([35] )., 2.1 Cond i, a 3, 1. 7
8 FWs(n) FWe(n) FW(n) 1: ([43] ) 2 n, (4) a (1 a n, gcd(a, n) 1) Euler-., n a Euler-. n Euler- FW e (n)., n, #FWe(n) ϕ(n) 1, t a Solovay- 2 Strassen (c pp) ( 1 2) t ([35] )., n, FW e (n) FW(n) ([35, 43], 1 ) Solovay-Strassen Fermat., Solovay-Strassen Miller-Rabin. 2.4 Miller-Rabin Miller-Rabin. 4 n, n 1=2 s t ( t ), 1 a<n a ( gcd(a, n) 1), a t 1 mod n i (0 i<s) a t2i 1 mod n. (5) Fermat, Solovay-Strassen, a Cond i,. 3 n, (5) a (1 a n, gcd(a, n) 1) (MR- )., n a. n FW s (n)., n, #FWs 1, t a Miller- ϕ(n) 4 Rabin (c pp) ( 1 t 4) ([35] )., n, FW s (n) FW e (n) ([35, 43], 1 ). 8
9 ,,.,, Fermat.,,. Miller-Rabin ([23]), , Solovay-Strassen, Miller-Rabin (GRH),1<a<min{n, 2(log n) 2 } a probable prime ([7, 46]). 2.5 Lucas-Lehmer Lucas-Lehmer. 5 n, P, Q =P 2 4Q n / 2Q ( gcd(2q,n) 1) U n ( n ) 0 mod n (6)., U i U 0 =0,U 1 =1,U i = PU i 1 QU i 2 (i 2)., P, Q Cond i,., U n ( n ) mod n, P, Q, n, n 2 ( [4] ). [5],. 6 ([5]) n, P, Q :=P 2 4Q n / 2Q ( gcd(2q,n) 1) n ( n ) =2 s t ( t ) U t 0 mod n i (0 i<s) V 2 i t 0 mod n. (7)., U i 5, V i V 0 =2,V 1 = P, V i = PV i 1 QV i 2 (i 2). 5, 6. 4 n, n, (6) (P, Q) (1 P, Q < n, gcd(q, n) 1, P 2 4Q mod n) Lucas-., n (P, Q) Lucas-. n Lucas- FW l (n)., (6) (7), Lucas-, Lucas-, FW sl (n). 9
10 , n n, #FW sl(n) 4 (t n 15 Lucas-Lehmer (c pp) ( 4 t 15) ) [5].,, ( ), #FWs(n) ( ) (2.1 n )., Lucas-Lehmer 2.2, 2.3, 2.4. Fermat, Solovay-Strassen, Miller-Rabin FW s (n) FW e (n) FW(n).,, Miller-Rabin., Lucas-Lehmer,., , P, Q Lucas-Lehmer ([56] )., 2 Lucas.,, Miller-Rabin Lucas-Lehmer., ANSI X9.80[4], Miller-Rabin, Lucas-Lehmer 1., 5 2 3, 2, (P, Q) =(1, 1) Lucas ([54] ). 2.6 Frobenius-Grantham Frobenius-Grantham. 7 n, f(x) F n d, gcd(f(0),n) 1. f 0 (X) :=f(x),f i (X) := gcd(x ni X, f i 1 (X)),f i (X) := f i 1 (X)/F i (X) (1 i d), i (1 i d), n i 1=2 r s, F i,0 (X) := gcd(f i (X),X s 1),F i,j (X) := gcd(f i (X),X 2j 1s +1) (1 j i), S := 2 i., deg(f i (X)) i f d (X) =1 i deg(f i (X)) (1 i d) (8) F i (X) F i (X n ) (2 i d) (9) ( 1) S = ( ) n (Jacobi ) (10) r j=0 F i,j(x) =F i (X) i deg(f i,j (X)) (0 j i) (11), f(x) 7 (8), (9), (10) Cond i Frobenius-Grantham, Cond i (11) Frobenius-Grantham. [29], d =2 Frobenius-Grantham 2 Frobenius ( [29] )., ANSI X9.80[4], d =2 f(x). 10
11 (d = 2), 1 f(x), 1 Miller-Rabin 3 ([29] )., [51], Miller-Rabin n, M(n) = (P, Q) Z 2 ( 0 P, Q ) < n, P 2 +4Q n = 1 ( Q n ) =1 1 < gcd(p 2 +4Q, n) <n 1 < gcd(q, n) <n, (8) (11) (P, Q) M(n)( 2 f(x) =X 2 PX Q) Frobenius-., n (P, Q)( 2 f(x) =X 2 PX Q) Frobenius-. n Frobenius- FW sf (n). Frobenius-Grantham, #FW sf, t #M(n) Frobenius-Grantham (c pp) (1/7710) t , 3 Miller-Rabin (c pp) 1/4 3 =1/64., 1 f(x), , 2 f(x) Frobenius, Lucas ([30] ), ,., Frobenius-Grantham, ( 4.3.2, 5.2 )., [51], (c pp) ( [51] ) , [55]., ANSI X 9.80[4].,. n Assump, Cond,n. (12).,, 3.2, 3.6, 11
12 Cond log n ( ), 3.6, [4, 34] 3.3 Proth-Pocklington-Lehmer- Selfridge (PPLS ) [4, 19, 55] 3.4 Kraitchik-Lehmer (KL ) [4, 55, 57] 3.5 Elliptic Curve Primality Proving (ECPP ) [4, 6, 26, 37, 48, 49, 63] 3.6 Cohen-Lenstra (CL ) [1, 4, 17, 18, 44, 45, 55, 67] 3.7 Agrawal-Kayal-Saxena- Lenstra (AKSL ) [2, 10, 50, 55, 66] 3.8 AKS[2] (AKS ) [2, 32] 2: n p n 1/2, n., n,., n 1/2,.,.,, n 0.35 ([34]).,,,. 3.3 Proth-Pocklington-Lehmer-Selfridge(PPLS) PPLS n 1 n +1 ([55] ). ANSI X9.80[4], n 1. 9 n>1, a, F 1 (F 1 n 1) a n 1 = 1 mod n q F 1 gcd(a (n 1)/q 1,n) = 1 (13) 12
13 ., P, Q (gcd(q, n) =1, :=P 2 4Q ( n ) = 1) F 2 (F 2 n +1) U n+1 0 mod n q F 2 U (n 1)/q (Z/(n)) (14), F =lcm[f 1,F 2 ] >n 1/2, n. 3.1 Assump F 1 n 1,F 2 n +1, F =lcm[f 1,F 2 ] >n 1/2 F 1,F 2, Cond (13) (14)., [55], (13), (14) n 1, n +1. ANSI[4], P, Q, =5, 7, 9, 11, 13, 15, 17,..., (P, Q) =(1, 1 4 ). 3.4 Kraitchik-Lehmer Kraitchik-Lehmer, n>1, n 1. n 1 q, a, n. a n 1 1 mod n, a (n 1)/q / 1 mod n (15), Assump, n 1, Cond (15). Assump Kraitchik-Lehmer,, n 1, (15) a. [55], n ϕ(n 1) > n 2 log log n ϕ( ) 2. n, ϕ(n 1) n q (15) a, a (1 <a<n) (15) 2 log log n a. Kraitchik-Lehmer PPLS,, PPLS., [57], 10 NP( ). NP,., n 1 q a., q,., q. 10, n 13 (16)
14 , [57],. (primality certificate). 3.5 ECPP,, 3.5,., (3.5 )., [2] P ( ) (3.7 ). 3.5 Elliptic Curve Primality Proving (ECPP),. n a, b Z (0 a, b < n, 4a 3 +27b 2 / 0), E a,b Y 2 = X 3 + ax + b. E a,b (n) (17) (x, y) F n O ( )., [6, 26, 37, 55],., M P =(x, y) E a,b (n), MP P M P } {{ P } M., ([26] ). 11 gcd(n, 6) = 1 n Z >1 gcd(4a 3 +27b 2,n)=1 a, b Z, P =(x, y) (Z/nZ) 2 y 2 x 3 + ax + b mod n., F Z F>(n 1/4 +1) 2. n n, P., FP, F q (F/q)P n,, n. FP = O, F q (F/q)P O (17) 10 (15) 11 (17) (15), (17).,. 11 (12), Assump, ( ) a, b ( P ) F, Cond (17). 14
15 3.4 n, n 1 Assump, ECPP F. F, 11 F = q., 11 F>(n 1/4 +1) 2 (17), E a,b (n), [63]., 3.4 ((17) ), ( ). 11 (Goldwasser-Kilian )ECPP, [26],, log n 1 O(2 log n1/ log log log n ) ( ). [63], [6] O((log n) 6+ɛ )(, ɛ ) ([37] ). [48], DEC 3000 (125 MHz), , 68.53, Cohen-Lenstra Cohen-Lenstra,, 12.,. p, q p k q 1, χ q,p : F q Q[ζ p k] χ q,p(f q )=< ζ p k >., a, b ab(a + b) / 0 mod p (a + b) p / a p + b p mod p 2 ( a, b )., J(χ a q,p,χb q,p ). q 1 J(χ a q,p,χ b q,p) := χ a q,p(y)χ b q,p(1 y) y=0, Q(ζ p k)/q G =Gal(Q(ζ p k)/q) Z[G] α., n (> 1), y Q, [y] y. p k [ ] nx α = σx 1 Z[G] x=1,p / x p k, σ x G, σ x : ζ p k ζ x p. k, ( ) E p E a p > 0. t := 2 p E pap, s := q,q 1 t qvq(t)+1 (v q q ) s>n 1/2. 15
16 12 ([67]) 4, n,. 1. s q q (n 1)/2 ±1( mod n) 2. s q q 1 p J(χ a q,p,χb q,p )α ζ mod n. (, ζ 1 p k ). 3. s q c (q 1)/2 1 mod n c Z. 4. n r, i (0 i<t) r n i mod s 12.,, (12) Assump, Cond., 2, Solovay-Strassen. 2 log n O(log log log n),., ( ),. [1, 17, 18, 39], (cyclotomy primality proving), [45], DEC Alpha n, 23.83, 41.40, , [45] p.106 3, ECPP, ECPP [48]. H/W, H/W ECPP 9 (, [45] H/W [48] ). 3.7 Agrawal-Kayal-Saxena-Lenstra(AKSL) [2], ( ). [10]. Agrawal-Kayal-Saxena-Lenstra(AKSL).. 13 n, r. S( Z) ( ). n. 1. n a c (, a, c Z,c>1). 2. n (Z/rZ). 3. ( b b ) b, b S gcd(n, b b )=1 ϕ(r)+#s 1 4. n ϕ(r) #S 5. b S, (x + b) n = x n + b (Z/nZ)[x]/(x r 1). 16
17 , (12) Assump, Cond. s = #S, [2, 10],, Õ(rs(log n)2 ). Õ(t(n)) := O(t(n)poly(log(t(n)))). 13 r, s, r = O((log n) 6 ),s = O((log n) 4 )., r = O((log n) 2 ),s= O((log n) 2 ) ([10] ),, Õ((log n)12 ), Õ((log n)6 ). [50], 700MHz PC, 10 9, AKSL , 65., AKSL,., ( [11, 66] ).,,. 3.8 AKS [2] 6, AKS.. 1 n Z >1, r Z >0 (r / n) n. (x 1) n x n 1 mod (x r 1,n) n 2 / 1 mod r, Õ((log n)3 ) ([2]). 1, 13 S = {1}, r r / n n 2 / 1 mod r, 13 4, r. r [2, 4 log n] ([2]). [32], r 100 n 10 10, 1. ( AKSL ),,,
18 2, 3 (4.3 ) (4.4 )..,,,,, 4.2, [24] DSA Random Choice (RC ) [4, 16, 22, 23, 33] Incremental Search(IS ) [4, 12, 13] FIPS DSS [24] Shawe-Taylor (ST ) [4, 43, 64] Maurer (M ) [4, 41, 42, 43] 3: [24] Appendix 3, [20] 5.3.1, CRYPTREC 2002 [58]., [24], SHA-1 DES 2., [20], SHA-1., [20] 160 SHA-1,, NIST SHA(SHA-256, SHA-384, SHA-512) SHA , , 3 Miller-Rabin probable prime, (18) (pp c). [ (pp c) := Prob n n probable prime [9]., 2.1 (c pp) (pp c). ] (18) 18
19 [33], log n, log n α, (2) β, (19) (pp c). (pp c) (1 α)β α +(1 α)β (19), (19), (pp c)., π(x) (x ) x, π(x) x log x (x ) ( ).,, x log x.,.,. (pp c), ([12, 23], (19) α ) Random Choice Random Choice , Miller-Rabin Random Choice Miller-Rabin Random Choice k, t n (k probable prime 1: repeat 2: k n. 3: n, t Miller-Rabin. 4: until n probable prime. 5: n. 2 n (pp c) p k,t 4. 4, log 2 p k,t., [16],, (pp c) 2 80 p 600, t 2..,
20 , Miller-Rabin (pp c), [22] Frobenius-Grantham (2.6 ).,. k\t : Random Choice log 2 p k,t Incremental Search Incremental Search,, Miller-Rabin Incremental Search, 3. [13], Incremental Search 25% ([13], H/W, 10 ). 3 (pp c) q k,t,c k., [12] 4 log 2 q k,t,c k., Incremental Search log 2 q k,t,c k, 4 log 2 p k,t., [12], log 2 q k,t,c k.,, c =1,k = 100,t=1 0. q 100,1,100 1,., [12] FIPS DSS FIPS DSS[24], Miller-Rabin,,.,, 20
21 3 Miller-Rabin Incremental Search k, t ), c ( ) n (k probable prime 1: k n 0 (= n). 2: while n<n 0 + c k do 3: n, t Miller-Rabin. 4: n probable prime n. 5: n n +2. 6: end while 7: fail., Shawe-Taylor Shawe-Taylor, (13).. 14 n, n 1 q (q >n 1/2 ) a, n. a n 1 1 mod n gcd(a (n 1)/q 1,n) = 1 (20) q, 2R<q R ( ) n =1+2Rq, n, q, (20) a Z. 14 n., q 2 n., (20) a, 3.4 (16)., Shawe-Taylor. ANSI X9.80[4] [64]., Maurer 4 4 r 1/2 Shawe-Taylor., [4], q = (3.2 ), R = (R <q), n =1+2Rq = (40 )., a = , (20), 40 n. 21
22 3.5 ECPP,,., , 10 (PPLS, Kraitchik-Lehmer ) Maurer Maurer Shawe-Taylor, 14, 4, r(0.5 r 1), n, n 1 q. x R, n [1,x], r(0.5 r 1) n n 1 x r s = s(r), 1 + log r ([42])., 4(MRandom Prime) s = 1 + log r,., 0.5 r 1 r, s = s(r) = Prob[n 1 x r n R [1,x]] 1 + log r (x ) (21). 4 Maurer (M Random Prime) b Z >0 b y 1: if b<20 then 2: b,. 3: else 4: s [0, 1] (21) r (0.5 r 1) 5: q M Random Prime( r b +1) 6: R n =2Rq +1 b, (20) n, n,. 7: end if 5 5.1, 5.,., 22
23 ( ), (, 4.2 ( ) ). ( ) ( ), (c pp) (512, 1024 ) (primality certificate) 5.1, , :,,, Cohen-Lenstra, AKSL, AKS. 5.2 n ( ) log n, log n (log n) 2.,, (, AKSL, AKS, 3.7, 3.8 )., AKSL, O((log n) 2 ),. AKS, AKSL ,, 7,., 2,3., AKS, 3.8 1, 2.4 Solovay-Strassen, Miller-Rabin, AKSL 7., Fermat, Solovay-Strassen, Miller- Rabin ((c pp), (pp c) ). 23
24 F SS MR LL FG t (c pp) ( 3 + o(1))t(log 2 n)3, 1 (GRH) MR ( 3 + o(1))t(log 2 n)3, ( 1 2(log n) 5 MR 2 )t ( o(1))t(log n)3, ( 1 4 )t 2(log n) 5 (3 + o(1))t(log n) 3, ( 4 15 )t ( 9 + o(1))t(log 2 n)3, ( )t Pentium IV 1.8 GHz, 1024 ( 2 ), 70m. 1 MR 2 1 MR 4.5 6:, Lucas-Lehmer,, Miller-Rabin,, Miller-Rabin, 2.5 Miller-Rabin. Frobenius-Grantham, (c pp) Miller-Rabin, (pp c), (19)., 2.6, [22], (pp c),,,., Miller-Rabin,,. (Assump) O(n 1/2 (log n) 2 ) n 1,n , PPLS O((log n) 4 ) MR 1000 (1.8GHz 70 ) KL O((log n) 4 ) n , MR 1000 (1.8GHz 70 ) 24
25 ECPP AM O((log n) 6+ɛ ). O(2 (log n) 1 log log log n ). DEC 3000, , 68.53, O((log n) 6 ) DEC Alpha 500, c,, 41.40, CL O((log n) c log log log n ) MHz PC, Õ((log n) ). AKSL 3, Õ((log, 65 n)7 ).. Pentium IV, 1.8GHz, r 100, 1024 AKS 3 Õ((log n) ), 62. r :, ( ),,. PPLS, Kraitchik-Lehmer, 7,, ( ) ( ). ECPP, Cohen-Lenstra, [48, 45] 1998, PC 7 512, 1024.,,.,., 5.4., Cohen-Lenstra ( ), ECPP ([45]), ECPP ([48] 3.5 ). 2 [36] , (608 ) log log log 512 = ,log log log 1024 = , log log log n c log log log n, ,
26 ,, Maurer, [43], t =1 Miller-Rabin,., Maurer., Random Choice Incremental Search,. 5.3., log n ( 10 ), PC,. PPLS Kraitchik-Lehmer, PC.,,. ECPP,,, [6], ( 2 ) (, ). [49] 2244, 10M., ECPP, PC. Cohen-Lenstra, [44] 12 q, PC, [36] n 512, 1024,. PC [36], (Windows XP,), 3M 512, Cohen-Lenstra,. AKSL, ( ), 512,1024 n,. [10] 26
27 13 r (log n) 2, r (log n) 2, n 1024, r 10 6, 1024( 10 3 ),, 10 9 ( = M ) (, )., (, AKSL, 5.2 ). AKS, r, PC. 5.4, 5.2 6, 7, Miller-Rabin., Cohen-Lenstra ( ) ECPP,, [4],,., Maurer,., [43], 4.4, Miller-Rabin Miller-Rabin 8 Miller-Rabin Miller-Rabin Miller-Rabin 27
28 Miller-Rabin Miller-Rabin Miller-Rabin 4 RSA 3 Miller-Rabin RSA Miller-Rabin [61] Miller-Rabin Miller-Rabin RSA [28, 43] Sliding Window 1 Sliding Window Miller-Rabin Binary 5 5 Binary x n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) y x k mod n 1: A x 2: for i from t 2downto0do 3: A A 2 4: if k i =1then 5: A A x 6: end if 7: end for 8: A x k k 1 S M k t Binary (t 1)S + t 2 M 28
29 Binary 1 Ary [28, 43] Ary Sliding Window 6 [28, 43] 6 Sliding Window x n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) Window w y x k mod n 1: 2: x 1 x, x 2 x 2 3: for i from 1 to (2 k 1 1) do 4: x 2i+1 x 2i 1 x 2 5: end for 6: 7: A 1, i t 1 8: while i 0 do 9: if k i =0then 10: A A 2, i i 1 11: else 12: i l +1 w e l =1 k i k i 1 k l 13: A A 2i l+1 x (ki k i 1 k l ) 2 14: i l 1 15: end if 16: end while 17: A Ary Sliding Window window w window x window w window w window window n x 29
30 window Sliding Window Window w 1 Binary Miller-Rabin Miller-Rabin 2 2 Binary Binary 2 n t k =(k t 1 k t 2 k 1 k 0 ) 2 (k i {0, 1} k t 1 =1) y 2 k mod n 1: A 2 2: for i from t 2downto0do 3: A A 2 4: if k i =1then 5: A A 2( ) 6: end if 7: end for 8: A 1 Binary Sliding Window 2 7 Miller-Rabin 2 (Sliding Window 2 ) [61] Miller-Rabin 2 (Random Choice) 3(Incremental Search) Miller-Rabin Random Choice [13] r, 30
31 . r = R 2 D log(r 2 /D) (22) R 2 2 Miller-Rabin 1 D window 8 CPU Pentium IV 1.6 GHz C OS RedHat Linux 8.0 gcc version 3.2 -O2 GNU MP version RAM 512 MB 8: 10,000 10,000 1 CRYPTREC [58] SHA Sliding Window window window 1 Binary 9 10 window 512 window window 6 31
32 Window (m ) ( ) , , , ,192 9: y x k mod n (512 ) Window (m.) ( ) , , , , ,384 10: y x k mod n (1024 ) x x PC IC window Sliding Window Miller-Rabin 2 32
33 Miller-Rabin (m ) : 2 y 2 k mod n Miller-Rabin 512 window 5 Sliding Window 1024 window 6 Sliding Window Miller-Rabin (22) Miller-Rabin 2 Miller-Rabin1 2 2 ( 11) µ µ 12: ( ) (22) Random Choice Incremental Search Random Choice Incremental Search Random Choice 2500 Incremental Search
34 (m ) Random Choice Incremental Search : Miller-Rabin (512 bit =6) ( ) Random Choice Incremental Search : Miller-Rabin (1024 bit =3) 6.3 Miller-Rabin 15 GMP ( 8) 15 IC 15 34
35 Sliding Window Window Random Choice Kbyte Kbyte Incremental Search Kbyte Kbyte 15: Miller-Rabin ( : ) window 6.4 GNU MP version 4.1.2(GMP)[25] GMP GMP GMP Miller-Rabin mpz probab prime p() Incremental Search mpz nextprime() n Miller-Rabin (n /30) 2 Miller-Rabin GMP ( ) GMP bit : m 1024 bit : m 35
36 7 RSA DSA RSA DSA RSA RSA 2 p q n p q n RSA RSA p q n(= pq) n ( ) n p ( ) 2 [38] [40] Fermat [14] Pollard p 1 [53] Williams p +1 [68] RSA p q p q ( ) p q (Fermat ) 36
37 p 1 q 1 (p 1 ) p +1 q +1 (p +1 ) O(exp(c(log e n) 1/3 (log e log e n) 2/3 )), c=1.901 O(exp(c log e plog e log e p) (log 2 n) 2 ),c=1.414 [20] n p RSA n = pq p q 2 p 1 p +1 p 1 p +1 p p 1 p +1 [62] p 1 p +1 [62] 2 p q n = pq n n = pq (Fermat [14]) 2 Fermat CRYPTREC CRYPTREC p q 512 n = pq 1024 [20] RSA p q n(= pq) 1024 CRYPTREC Report 2001( )[20] CRYPTREC Report 2001( )[20] CRYPTREC Report 2002( ) 37
38 7.2 DSA DSA NIST [24] DSA G 6( ) G G g u = g x (x Z) x [20] G DSA Pohlig-Hellman [52] Index-Calculus [27] DSA 2 p q [24] DSA DSA p q DSA p q p 1024 q 160 p 1 q DSA [24] p 1024 p 1024 DSA DSA 7.3 p p p p 38
39 p p (p ) CRYPTREC p 160 [20] p p ANSI ANSI ANSI X 9.80 American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates [4] 8.2 FIPS NIST FIPS Digital Signature Standard (DSS) DSA Miller-Rabin SHA-1 DES 8.3 CRYPTREC e-japan CRYPTREC [21] CRYPTREC [58] 16 CRYPTREC 39
40 RSASSA-PKCS-v1 5, RSA-PSS, RSA-OAEP, RSAES-PKCS-v1 5 DSA, DH ECDSA, ECDH, PSEC-KEM 16: ( ) 7 RSA DSA CMVP 9.1 Miller-Rabin ( ) Cohen-Lenstra 40
41 Miller-Rabin Miller- Rabin CRYPTREC [58] window IC ( ) IC RAM 6 window CRYPTREC 7 RSA DSA 41
42 ( ) Miller-Rabin Solovay-Strassen AKSL AKS Miller-Rabin Miller-Rabin 9.5 Miller-Rabin Solovay-Strassen Miller-Rabin Solovay-Strassen Miller-Rabin ( ) 1 AKSL (3.7 ) AKSL AKSL [2] AKS
43 AKS Miller-Rabin Random choice Miller-Rabin Incremental search Solovay-Strassen Random choice Solovay-Strassen Incremental search AKSL Random choice AKSL Incremental search AKS Random choice AKS Incremental search Random choice Incremental search (6 ) CRYPTREC [58] AKS [2] RSA DSA CRYPTREC RSA DSA 3 3 p p RSA RSA 43
44 DSA 7 RSA DSA 7 RSA p q p q DSA p q p 1024 q 160 p 1 q 9.5 CMVP Cryptographic Module Validation Program(CMVP) 1995 NIST( ) CSE( ) CMVP FIPS FIPS / Miller-Rabin CMVP Miller-Rabin 1 Miller-Rabin Solovay-Strassen (2.3 ) ( ) 44
45 CMVP RSA DSA FIPS FIPS DSA (SHA-1) SHA-1 10 Miller-Rabin Miller-Rabin ( ) AKSL AKS AKSL AKS 45
46 [1] L. M. Adleman, C. Pomerance and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. Math. 117 (1983), [2] M. Agrawal, N. Kayal, N. Saxena, Primes is in P, preprint, available at http: // [3] W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 140 (1994), [4] ANSI X 9.80, American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates, American National Standard Institute, [5] F. Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Math. Comp. 66 (1997), [6] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), [7] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 35 (1990), [8] R. Bailie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), [9] P. Beauchemin, G. Brassard, C. Crepeau, C. Goutier and C. Pomerance, The generation of random numbers that are probably prime, Journal of Cryptology 1 (1988), [10] D. J. Bernstein, An exposition of the Agrawal-Kayal-Saxena primality-proving theorem, preprint. [11] P. Berrizbeitia, Sharpening Primes is in P for a large family of numbers, preprint, available at [12] J. Brandt, I. Damgard, On generation of probable primes by incremental search, CRYPTO 92 (1992), LNCS 740, [13] J. Brandt, I. Damgard and P. Landrock, Speeding up prime number generation, ASIACRYPT 91 (1991), LNCS 739, [14] J. Brillhart, Fermat s factoring method and its variants, Congressus Numberantium, vol. 32, (1981),
47 [15] J. Brillhart, D. H. Lehmer, J. Selfridge, B. Tuckerman and S. S. Wagstaff, Jr., Factorizations of bn 1 for b = 2,3,5,6,7,10,11,12 up to high powers, Contemporary Mathematics, vol. 22, American Mathematical Society, Second Edition, [16] R. J. Burthe, Jr., Further investigations with the strong probable prime test, Math. Comp. 65 (1996), [17] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), [18] H. Cohen and H. W. Lenstra, Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), [19] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, [20] CRYPTREC Report 2001 ( ), (IPA) (TAO). [21] IPA, TAO, CRYPTREC, enc/cryptrec/ [22] I. Damgard, G. S. Frandsen, An extended quadratic Frobenius primality test withaverage case error estimates, BRICS Report, RS-01-45, Univ. of Aarhus, Denmark, [23] I. Damgard, P. Landrock and C. Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), [24] FIPS 186-2, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, U.S. Department of Commerce/ N.I.S.T., January [25] GNU MP home page, [26] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC. (1986), [27] D. M. Gordon, Discrete logarithm in GF (p) using the number field sieve, SIAM Journal on Discrete Math., vol. 6 (1993), [28] D. M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, vol. 27, (1998), [29] J. Grantham, A probable prime test with high confidence, Journal of Number Theory 72 (1998),
48 [30] J. Grantham, Frobenius pseudoprimes, Math. Comp. 70 (2001), [31] J. Grantham, There are infinitely many Perrin pseudoprimes, preprint, available at [32] N. Kayal, N. Saxena, Towards a deterministic polynomial-time primality test, Technical Report, IIT Kanpur, 2002, available at research/btp2001/primality.html. [33] S. -H. Kim and C. Pomerance, The probability that a random probable prime is composite, Math. Comp. 61 (1989), [34] D. E. Knuthand L. T. Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci., 3 (1976), [35] N. Koblitz, A Course in Number Theory and Cryptography, GTM 114, Springer Verlag, Second Edition, [36] Y. Kida, Cohen-Lenstra method UBASIC program, available at rkmath.rikkyo.ac.jp/~kida/ubasic.htm. [37] A. K. Lenstra and H. W. Lenstra, Jr, Algorithms in number theory, J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Elsevier Science Publishers, 1990, [38] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The number field sieve, Proc. 22nd STOC, (1990), [39] H. W. Lenstra, Jr, Primality testing algorithms (after Adleman, Rumely and Williams), Séminaire Bourbaki 33 (1980/1981), no. 576, LNM Vol. 901, Springer. 1981, [40] H. W. Lenstra, Jr., Factoring integers withelliptic curves, Ann. Math., vol. 126, (1987), [41] U. Maurer, Some number-theoretic conjectures and their relation to the generation of cryptographic primes, C. Mitchell. Editor, Cryptography and Coging II, volume 33 of Institute of Mathematics & Its Applications (IMA), , Clarendon Press, [42] U. Maurer, Fast generation of prime numbers and secure public-key cryptographic parameters, Journal of Cryptology 8 (1995), [43] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC press,
49 [44] P. Mihăilescu, Cyclotomy of rings and primality testing, dissertation 12278, ETH Zürich, 1997 available at [45] P. Mihăilescu, Cyclotomy primality proving - recent developments, ANTS III, LNCS Vol. 1423, Springer. 1998, [46] G. L. Miller, Riemann s hypothesis and tests for primality, Journal of Computer and System Sciences, 13 (1976), [47] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci., 12 (1980), [48] F. Morain, Primality proving using elliptic curves: an update, ANTS III, LNCS Vol. 1423, Springer. 1998, [49] F. Morain, ECPP package, available at polytechnique.fr/labo/francois.morain/prgms/ecpp.english.html. [50] F. Morain, Primalite theorique et primalite pratique ou AKS vs. ECPP, available at Francois.Morain/aks-f.pdf [51] S. Müller, A probable prime test withvery highconfidence for n 1 mod 4, ASIACRYPT 2001 (2001), LNCS 2248, [52] S. C. Pohlig, M. E. Hellman, An improved algorithm for computing logarithm over GF (p) and its Cryptographic Significance, IEEE Trans. Information Theory, IT-24, No. 1, (1978), [53] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambr. Philos. Soc, vol. 76, 1974, [54] C. Pomerance, Are there counter-examples to the Baillie-PSW primality test, Letter to A. Lenstra, available at [55] C. Pomerance, Primality testing: variations on a theme of Lucas, to appear in the proceedings of an MSRI workshop, J. Buhler and P. Stevenhagen, eds. available at [56] C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to , Math. Comp. 35 (1980), [57] V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput., 4 (1975), [58], , 5.html. 49
50 [59] M. O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), [60] P. Ribenboim, The Book of Prime Number Records, Springer Verlag, Second Edition, [61] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhauser, Second Edition, [62] R. L. Rivest, R. D. Silverman, Are strong primes needed for RSA?, Cryptology eprint Archive, Report 2001/007, (2001), available at [63] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44, 1985, [64] J. Shawe-Taylor, Generating strong primes, Electronics Letters 22 (July 31, 1986), [65] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput., 6 (1977), 84-85, Erratum in 7 (1978), 118. [66] J. F. Voloch, Improvements to AKS, preprint, available at utexas.edu/users/voloch/preprint.html. [67] L. C. Washington, Introduction to Cyclotomic Fields, GTM 83, Springer Verlag, Second Edition, [68] H. C. Williams, A p + 1 method of factoring, Math. Comp., vol. 39, No. 159, (1982), [69] H. C. Williams, Edouard Lucas and Primality Testing, Can. Math. Soc. series of monographs and advanced text, Wiley-Interscience,
a m 1 mod p a km 1 mod p k<s 1.6. n > 1 n 1= s m, (m, = 1 a n n a m 1 mod n a km 1 mod n k<sn a 1.7. n > 1 n 1= s m, (m, = 1 r n ν = min ord (p 1 (1 B
10 004 Journal of the Institute of Science and Engineering. Chuo University Euler n > 1 p n p ord p n n n 1= s m (m B psp = {a (Z/nZ ; a n 1 =1}, B epsp = { ( a (Z/nZ ; a n 1 a }, = n B spsp = { a (Z/nZ
( 9 1 ) 1 2 1.1................................... 2 1.2................................................. 3 1.3............................................... 4 1.4...........................................
30 2018.4.25 30 1 nuida@mist.i.u-tokyo.ac.jp 2018 4 11 2018 4 25 30 2018.4.25 1 1 2 8 3 21 4 28 5 37 6 43 7 47 8 52 30 2018.4.25 1 1 Z Z 0 Z >0 Q, R, C a, b a b a = bc c 0 a b b a b a a, b, c a b b c a
#2 (IISEC)
#2 (IISEC) 2007 10 6 E Y 2 = F (X) E(F p ) E : Y 2 = F (X) = X 3 + AX + B, A, B F p E(F p ) = {(x, y) F 2 p y2 = F (x)} {P } P : E(F p ) E F p - Given: E/F p : EC, P E(F p ), Q P Find: x Z/NZ s.t. Q =
数理解析研究所講究録 第1955巻
1955 2015 158-167 158 Miller-Rabin IZUMI MIYAMOTO $*$ 1 Miller-Rabin base base base 2 2 $arrow$ $arrow$ $arrow$ R $SA$ $n$ Smiyamotol@gmail.com $\mathbb{z}$ : ECPP( ) AKS 159 Adleman-(Pomerance)-Rumely
21 Key Exchange method for portable terminal with direct input by user
21 Key Exchange method for portable terminal with direct input by user 1110251 2011 3 17 Diffie-Hellman,..,,,,.,, 2.,.,..,,.,, Diffie-Hellman, i Abstract Key Exchange method for portable terminal with
楕円曲線暗号と RSA 暗号の安全性比較
RSA, RSA RSA 7 NIST SP-7 Neal Koblitz Victor Miller ECDLP (Elliptic Curve Discrete Logarithm Problem) RSA Blu-ray AACS (Advanced Access Control System) DTCP (Digital Transmission Content Protection) RSA
SQUFOF NTT Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) N UBASIC 50 / 200 [
SQUFOF SQUFOF NTT 2003 2 17 16 60 Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) 60 1 1.1 N 62 16 24 UBASIC 50 / 200 [ 01] 4 large prime 943 2 1 (%) 57 146 146 15
Block cipher
18 12 9 1 2 1.1............................... 2 1.2.................. 2 1.3................................. 4 1.4 Block cipher............................. 4 1.5 Stream cipher............................
特集_03-07.Q3C
3-7 Error Detection and Authentication in Quantum Key Distribution YAMAMURA Akihiro and ISHIZUKA Hirokazu Detecting errors in a raw key and authenticating a private key are crucial for quantum key distribution
28 SAS-X Proposal of Multi Device Authenticable Password Management System using SAS-X 1195074 2017 2 3 SAS-X Web ID/ ID/ Web SAS-2 SAS-X i Abstract Proposal of Multi Device Authenticable Password Management
1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4..
2010 8 3 ( ) 1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4........................................
2 2 MATHEMATICS.PDF 200-2-0 3 2 (p n ), ( ) 7 3 4 6 5 20 6 GL 2 (Z) SL 2 (Z) 27 7 29 8 SL 2 (Z) 35 9 2 40 0 2 46 48 2 2 5 3 2 2 58 4 2 6 5 2 65 6 2 67 7 2 69 2 , a 0 + a + a 2 +... b b 2 b 3 () + b n a
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 1 1977 x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) ( x 2 y + xy 2 x 2 2xy y 2) = 15 (x y) (x + y) (xy
2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking RSA Group Name RSA C
2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name RSA Group Name RSA Code Elliptic Curve Cryptograrhy Group /Project No. 13-B /Project Leader 1009087 Takahiro
ISO/IEC 9798プロトコルの安全性評価
ISO/IEC 9798 2011 2 4 ISO/IEC 9798-2 (Mechanisms using symmetric encipherment algorithms), ISO/IEC 9798-3 (Mechanisms using digital signature techniques), ISO/IEC 9798-4 (Mechanisms using a cryptographic
., White-Box, White-Box. White-Box.,, White-Box., Maple [11], 2. 1, QE, QE, 1 Redlog [7], QEPCAD [9], SyNRAC [8] 3 QE., 2 Brown White-Box. 3 White-Box
![., White-Box, White-Box. White-Box.,, White-Box., Maple [11], 2. 1, QE, QE, 1 Redlog [7], QEPCAD [9], SyNRAC [8] 3 QE., 2 Brown White-Box. 3 White-Box](/thumbs/91/105919953.jpg "., White-Box, White-Box. White-Box.,, White-Box., Maple [11], 2. 1, QE, QE, 1 Redlog [7], QEPCAD [9], SyNRAC [8] 3 QE., 2 Brown White-Box. 3 White-Box")
White-Box Takayuki Kunihiro Graduate School of Pure and Applied Sciences, University of Tsukuba Hidenao Iwane ( ) / Fujitsu Laboratories Ltd. / National Institute of Informatics. Yumi Wada Graduate School
ASF-01
暗号モジュール試験及び認証制度 (JCMVP) 承認されたセキュリティ機能に関する仕様 平成 26 年 4 月 1 日独立行政法人情報処理推進機構 ASF-01 A p p r o v e d S e c u r i t y F u n c t i o n s 目次 1. 目的... 1 2. 承認されたセキュリティ機能... 1 公開鍵... 1 共通鍵... 3 ハッシュ... 4 メッセージ認証...
RSA署名方式の安全性を巡る研究動向について
RSA RSA RSA RSA RSA RSA PSSRSA PSS RSARSA PSS RSA PSS RSARSA-PSS E-mail:mayumi.saitou@boj.or.jp RSARSA PKCS ISO ISO IPS ANS X RSARSA RSA RSA RSA RSA RSA RSA bit RSA RSA PSS RSA PSS RSA ISO PKCSVer RSA
:00-16:10
3 3 2007 8 10 13:00-16:10 2 Diffie-Hellman (1976) K K p:, b [1, p 1] Given: p: prime, b [1, p 1], s.t. {b i i [0, p 2]} = {1,..., p 1} a {b i i [0, p 2]} Find: x [0, p 2] s.t. a b x mod p Ind b a := x
<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F5F A815B FD B A5F E646F63>
2008 年度版リストガイド ( メッセージ認証コード ) 平成 21 年 3 月 独立行政法人情報通信研究機構独立行政法人情報処理推進機構 1 1 1.1............................. 1 1.1.1............................ 1 1.1.2....................... 1 1.1.3...........................
1 UTF Youtube ( ) / 30
2011 11 16 ( ) 2011 11 16 1 / 30 1 UTF 10 2 2 16 2 2 0 3 Youtube ( ) 2011 11 16 2 / 30 4 5 ad bc = 0 6 7 (a, b, a x + b y) (c, d, c x + d y) (1, x), (2, y) ( ) 2011 11 16 3 / 30 8 2 01001110 10100011 (
2008 (2008/09/30) 1 ISBN 7 1.1 ISBN................................ 7 1.2.......................... 8 1.3................................ 9 1.4 ISBN.............................. 12 2 13 2.1.....................
Mazur [Ma1] Schlessinger [Sch] [SL] [Ma1] [Ma1] [Ma2] Galois [] 17 R m R R R M End R M) M R ut R M) M R R G R[G] R G Sets 1 Λ Noether Λ k Λ m Λ k C Λ
![Mazur [Ma1] Schlessinger [Sch] [SL] [Ma1] [Ma1] [Ma2] Galois [] 17 R m R R R M End R M) M R ut R M) M R R G R[G] R G Sets 1 Λ Noether Λ k Λ m Λ k C Λ](/thumbs/78/78261740.jpg "Mazur [Ma1] Schlessinger [Sch] [SL] [Ma1] [Ma1] [Ma2] Galois [] 17 R m R R R M End R M) M R ut R M) M R R G R[G] R G Sets 1 Λ Noether Λ k Λ m Λ k C Λ")
Galois ) 0 1 1 2 2 4 3 10 4 12 5 14 16 0 Galois Galois Galois TaylorWiles Fermat [W][TW] Galois Galois Galois 1 Noether 2 1 Mazur [Ma1] Schlessinger [Sch] [SL] [Ma1] [Ma1] [Ma2] Galois [] 17 R m R R R
newmain.dvi
数論 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/008142 このサンプルページの内容は, 第 2 版 1 刷発行当時のものです. Daniel DUVERNEY: THÉORIE DES NOMBRES c Dunod, Paris, 1998, This book is published
SAMA- SUKU-RU Contents p-adic families of Eisenstein series (modular form) Hecke Eisenstein Eisenstein p T
SAMA- SUKU-RU Contents 1. 1 2. 7.1. p-adic families of Eisenstein series 3 2.1. modular form Hecke 3 2.2. Eisenstein 5 2.3. Eisenstein p 7 3. 7.2. The projection to the ordinary part 9 3.1. The ordinary
2001 Miller-Rabin Rabin-Solovay-Strassen self-contained RSA RSA RSA ( ) Shor RSA RSA 1 Solovay-Strassen Miller-Rabin [3, pp
200 Miller-Rabin 2002 3 Rabin-Solovay-Strassen self-contained RSA RSA RSA ( ) Shor 996 2 RSA RSA Solovay-Strassen Miller-Rabin [3, pp. 8 84] Rabin-Solovay-Strassen 2 Miller-Rabin 3 4 Miller-Rabin 5 Miller-Rabin
Kullback-Leibler
Kullback-Leibler 206 6 6 http://www.math.tohoku.ac.jp/~kuroki/latex/206066kullbackleibler.pdf 0 2 Kullback-Leibler 3. q i.......................... 3.2........... 3.3 Kullback-Leibler.............. 4.4
Z[i] Z[i] π 4,1 (x) π 4,3 (x) 1 x (x ) 2 log x π m,a (x) 1 x ϕ(m) log x 1.1 ( ). π(x) x (a, m) = 1 π m,a (x) x modm a 1 π m,a (x) 1 ϕ(m) π(x)
![Z[i] Z[i] π 4,1 (x) π 4,3 (x) 1 x (x ) 2 log x π m,a (x) 1 x ϕ(m) log x 1.1 ( ). π(x) x (a, m) = 1 π m,a (x) x modm a 1 π m,a (x) 1 ϕ(m) π(x)](/thumbs/94/118373946.jpg "Z[i] Z[i] π 4,1 (x) π 4,3 (x) 1 x (x ) 2 log x π m,a (x) 1 x ϕ(m) log x 1.1 ( ). π(x) x (a, m) = 1 π m,a (x) x modm a 1 π m,a (x) 1 ϕ(m) π(x)")
3 3 22 Z[i] Z[i] π 4, (x) π 4,3 (x) x (x ) 2 log x π m,a (x) x ϕ(m) log x. ( ). π(x) x (a, m) = π m,a (x) x modm a π m,a (x) ϕ(m) π(x) ϕ(m) x log x ϕ(m) m f(x) g(x) (x α) lim f(x)/g(x) = x α mod m (a,
untitled
2 : n =1, 2,, 10000 0.5125 0.51 0.5075 0.505 0.5025 0.5 0.4975 0.495 0 2000 4000 6000 8000 10000 2 weak law of large numbers 1. X 1,X 2,,X n 2. µ = E(X i ),i=1, 2,,n 3. σi 2 = V (X i ) σ 2,i=1, 2,,n ɛ>0
K 2 X = 4 MWG(f), X P 2 F, υ 0 : X P 2 2,, {f λ : X λ P 1 } λ Λ NS(X λ ), (υ 0 ) λ : X λ P 2 ( 1) X 6, f λ K X + F, f ( 1), n, n 1 (cf [10]) X, f : X
![K 2 X = 4 MWG(f), X P 2 F, υ 0 : X P 2 2,, {f λ : X λ P 1 } λ Λ NS(X λ ), (υ 0 ) λ : X λ P 2 ( 1) X 6, f λ K X + F, f ( 1), n, n 1 (cf [10]) X, f : X](/thumbs/91/106734137.jpg "K 2 X = 4 MWG(f), X P 2 F, υ 0 : X P 2 2,, {f λ : X λ P 1 } λ Λ NS(X λ ), (υ 0 ) λ : X λ P 2 ( 1) X 6, f λ K X + F, f ( 1), n, n 1 (cf [10]) X, f : X")
2 E 8 1, E 8, [6], II II, E 8, 2, E 8,,, 2 [14],, X/C, f : X P 1 2 3, f, (O), f X NS(X), (O) T ( 1), NS(X), T [15] : MWG(f) NS(X)/T, MWL(f) 0 (T ) NS(X), MWL(f) MWL(f) 0, : {f λ : X λ P 1 } λ Λ NS(X λ
[I486S] 暗号プロトコル理論
![[I486S] 暗号プロトコル理論](/thumbs/91/105754538.jpg "[I486S] 暗号プロトコル理論")
[I486S] 2018 5 1 (JAIST) 2018 5 1 1 / 22 : I486S I URL:https://wwwjaistacjp/~fujisaki/i486S (Tuesdays) 5 17:10 18:50 4/17, 4/24, 5/1, 5/15, 5/22, 5/29, 6/5, 6/19, 6/26, 7/3, 7/10, 7/17, 7/24, 7/31 (JAIST)
II
II 2016 7 21 computer-assisted proof 1 / 64 1. 2. 3. Siegfried M. Rump : [1] I,, 14:3 (2004), pp. 214 223. [2] II,, 14:4 (2004), pp. 346 359. 2 / 64 Risch 18 3 / 64 M n = 2 n 1 (n = 1, 2,... ) 2 2 1 1
将来の暗号技術に関する安全性要件調査報告書
i ... 1... 3... 4 DES... 4 DES Cracker (1998 )... 4... 6 3.3.1 Lenstra & Verheul1999... 6 3.3.2 2000... 10 3.3.3 Silverman2000... 12... 12... 13... 13... 14... 17... 18... 18 5.1.1... 18 5.1.2... 18 5.1.3...
Title 素数判定の決定的多項式時間アルゴリズム ( 代数的整数論とその周辺 ) Author(s) 木田, 雅成 Citation 数理解析研究所講究録 (2003), 1324: Issue Date URL
Title 素数判定の決定的多項式時間アルゴリズム ( 代数的整数論とその周辺 ) Author(s) 木田 雅成 Citation 数理解析研究所講究録 (2003) 1324: 22-32 Issue Date 2003-05 URL http://hdlhandlenet/2433/43143 Right Type Departmental Bulletin Paper Textversion
http://www.ipa.go.jp/security/ Contents 1. NIST 2010 2. NISC 3. CRYPTREC 2008 10 28 Copyrignt 2008, IPA all right reserved. 2 1977 MAC) PKI PKI PKI: (Public Key Infrastructure) 2008 10 28 Copyrignt 2008,
, = = 7 6 = 42, =
http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1 1 2016.9.26, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.1 1 214 132 = 28258 2 + 1 + 4 1 + 3 + 2 = 7 6 = 42, 4 + 2 = 6 2 + 8
電子マネー・システムにおけるセキュリティ対策：リスク管理に焦点を当てて
1999 IC IC 2008 2 5 10 E-mail: masataka.suzuki@boj.or.jp E-mail: hirokawa@imes.boj.or.jp E-mail: une@imes.boj.or.jp //2008.8 39 1. 1990 2007 1 IC 1 1 20072006 2007 1 Edy Edy IC 2007 2 22 IC PASMO IC 2008
CPU Levels in the memory hierarchy Level 1 Level 2... Increasing distance from the CPU in access time Level n Size of the memory at each level 1: 2.2
FFT 1 Fourier fast Fourier transform FFT FFT FFT 1 FFT FFT 2 Fourier 2.1 Fourier FFT Fourier discrete Fourier transform DFT DFT n 1 y k = j=0 x j ω jk n, 0 k n 1 (1) x j y k ω n = e 2πi/n i = 1 (1) n DFT
kokyuroku.dvi
On Applications of Rigorous Computing to Dynamical Systems (Zin ARAI) Department of Mathematics, Kyoto University email: arai@math.kyoto-u.ac.jp 1 [12, 13] Lorenz 2 Lorenz 3 4 2 Lorenz 2.1 Lorenz E. Lorenz
第5章 偏微分方程式の境界値問題
October 5, 2018 1 / 113 4 ( ) 2 / 113 Poisson 5.1 Poisson ( A.7.1) Poisson Poisson 1 (A.6 ) Γ p p N u D Γ D b 5.1.1: = Γ D Γ N 3 / 113 Poisson 5.1.1 d {2, 3} Lipschitz (A.5 ) Γ D Γ N = \ Γ D Γ p Γ N Γ
/ ( ) 1 1.1 323 206 23 ( 23 529 529 323 206 ) 23 1.2 33 1.3 323 61 61 3721 3721 323 168 168 323 23 61 61 23 1403 323 111 111 168 206 323 47 111 323 47 2 23 2 2.1 34 2 2.2 2 a, b N a b N a b (mod N) mod
genus 2 Jacobi Pila Schoof 42 Adleman Huang 2 19 3 Gaudry Harley l genus 2 Jacobi 17 Jacobi Spallek 52 theta CM Jacobi genus2 Wang 61 Weber 60 Wamelen
6 2000 Journal of the Institute of Science and Engineering5 Chuo University Jacobi CM Type Computation of CM Type of Jacobian Varieties Jacobi CM CM Jacobi CM type reflex CM type Frobenius endomorphism
Twist knot orbifold Chern-Simons
Twist knot orbifold Chern-Simons 1 3 M π F : F (M) M ω = {ω ij }, Ω = {Ω ij }, cs := 1 4π 2 (ω 12 ω 13 ω 23 + ω 12 Ω 12 + ω 13 Ω 13 + ω 23 Ω 23 ) M Chern-Simons., S. Chern J. Simons, F (M) Pontrjagin 2.,
Pari-gp /7/5 1 Pari-gp 3 pq
Pari-gp 3 2007/7/5 1 Pari-gp 3 pq 3 2007 7 5 Pari-gp 3 2007/7/5 2 1. pq 3 2. Pari-gp 3. p p 4. p Abel 5. 6. 7. Pari-gp 3 2007/7/5 3 pq 3 Pari-gp 3 2007/7/5 4 p q 1 (mod 9) p q 3 (3, 3) Abel 3 Pari-gp 3
2 2 ( M2) ( )
2 2 ( M2) ( ) 2007 3 3 1 2 P. Gaudry and R. Harley, 2000 Schoof 63bit 2 8 P. Gaudry and É. Schost, 2004 80bit 1 / 2 16 2 10 2 p: F p 2 C : Y 2 =F (X), F F p [X] : monic, deg F = 5, J C (F p ) F F p p Frobenius
Int Int 29 print Int fmt tostring 2 2 [19] ML ML [19] ML Emacs Standard ML M M ::= x c λx.m M M let x = M in M end (M) x c λx.
![Int Int 29 print Int fmt tostring 2 2 [19] ML ML [19] ML Emacs Standard ML M M ::= x c λx.m M M let x = M in M end (M) x c λx.](/thumbs/93/111616248.jpg "Int Int 29 print Int fmt tostring 2 2 [19] ML ML [19] ML Emacs Standard ML M M ::= x c λx.m M M let x = M in M end (M) x c λx.")
1, 2 1 m110057@shibaura-it.ac.jp 2 sasano@sic.shibaura-it.ac.jp Eclipse Visual Studio ML Standard ML Emacs 1 ( IDE ) IDE C C++ Java IDE IDE IDE IDE Eclipse Java IDE Java Standard ML 1 print (Int. 1 Int
Optical Flow t t + δt 1 Motion Field 3 3 1) 2) 3) Lucas-Kanade 4) 1 t (x, y) I(x, y, t)
http://wwwieice-hbkborg/ 2 2 4 2 -- 2 4 2010 9 3 3 4-1 Lucas-Kanade 4-2 Mean Shift 3 4-3 2 c 2013 1/(18) http://wwwieice-hbkborg/ 2 2 4 2 -- 2 -- 4 4--1 2010 9 4--1--1 Optical Flow t t + δt 1 Motion Field
Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N.
![Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N.](/thumbs/93/113887245.jpg "Basic Math. 1 0 [ N Z Q Q c R C] 1, 2, 3,... natural numbers, N Def.(Definition) N (1) 1 N, (2) n N = n +1 N, (3) N (1), (2), n N n N (element). n/ N.")
Basic Mathematics 16 4 16 3-4 (10:40-12:10) 0 1 1 2 2 2 3 (mapping) 5 4 ε-δ (ε-δ Logic) 6 5 (Potency) 9 6 (Equivalence Relation and Order) 13 7 Zorn (Axiom of Choice, Zorn s Lemma) 14 8 (Set and Topology)
Input image Initialize variables Loop for period of oscillation Update height map Make shade image Change property of image Output image Change time L
1,a) 1,b) 1/f β Generation Method of Animation from Pictures with Natural Flicker Abstract: Some methods to create animation automatically from one picture have been proposed. There is a method that gives
25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble
25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.
& 3 3 ' ' (., (Pixel), (Light Intensity) (Random Variable). (Joint Probability). V., V = {,,, V }. i x i x = (x, x,, x V ) T. x i i (State Variable),
.... Deeping and Expansion of Large-Scale Random Fields and Probabilistic Image Processing Kazuyuki Tanaka The mathematical frameworks of probabilistic image processing are formulated by means of Markov
セアラの暗号
1 Cayley-Purser 1 Sarah Flannery 16 1 [1] [1] [1]314 www.cayley-purser.ie http://cryptome.org/flannery-cp.htm [2] Cryptography: An Investigation of a New Algorithm vs. the RSA(1999 RSA 1999 9 11 2 (17
å‰Łçı—訋çfl»æ³Łã†¨ã…Łã‡£ã…œã…−ã……ã…†æŁ°, ㆚ㆮ2æ¬¡è©Łä¾¡å‹ƒå›²ã•† ㅋㅪㅜã…−ã……ã…†æŁ°å‹Šã†«ã‡‹ã‡‰é•£ã†®ç¢ºç”⁄訋箊
, 2 August 28 (Fri), 2016 August 28 (Fri), 2016 1 / 64 Outline 1 2 3 2 4 2 5 6 August 28 (Fri), 2016 2 / 64 fibonacci Lucas 2 August 28 (Fri), 2016 3 / 64 Dynamic Programming R.Bellman Bellman Continuum
Lebesgue可測性に関するSoloayの定理と実数の集合の正則性=1This slide is available on ` `%%%`#`&12_`__~~~ౡ氀猀e
Khomskii Lebesgue Soloay 1 Friday 27 th November 2015 1 This slide is available on http://slideshare.net/konn/lebesguesoloay 1 / 34 Khomskii 1 2 3 4 Khomskii 2 / 34 Khomskii Solovay 3 / 34 Khomskii Lebesgue
2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Visualization of Code-Breaking Group Name Implemati
2011 Future University Hakodate 2011 System Information Science Practice Group Report Project Name Group Name Implemation Group /Project No. 13-C /Project Leader 1009087 Takahiro Okubo /Group Leader 1009087
(Requirements in communication) (efficiently) (Information Theory) (certainly) (Coding Theory) (safely) (Cryptography) I 1
(Requirements in communication) (efficiently) (Information Theory) (certainly) (oding Theory) (safely) (ryptography) I 1 (Requirements in communication) (efficiently) (Information Theory) (certainly) (oding
DPA,, ShareLog 3) 4) 2.2 Strino Strino STRain-based user Interface with tacticle of elastic Natural ObjectsStrino 1 Strino ) PC Log-Log (2007 6)
1 2 1 3 Experimental Evaluation of Convenient Strain Measurement Using a Magnet for Digital Public Art Junghyun Kim, 1 Makoto Iida, 2 Takeshi Naemura 1 and Hiroyuki Ota 3 We present a basic technology
a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552
3 3.0 a n a n ( ) () a m a n = a m+n () (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 55 3. (n ) a n n a n a n 3 4 = 8 8 3 ( 3) 4 = 8 3 8 ( ) ( ) 3 = 8 8 ( ) 3 n n 4 n n
( )
NAIST-IS-MT0851100 2010 2 4 ( ) CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i On the Key Management Policy of Challenge Response Authentication Schemes Toshiya
/ AICHI UNIVERSITY OF EDUCATION A { z = x + iy 0.100 2 HI LO ZDD 2 ZDD 2 HI LO 2 ( ) HI (Zero-suppress ) Zero-suppress ZDD ZDD Zero-suppress 1 ZDD abc a HI b c b Zero-suppress b ZDD ZDD 5) ZDD F 1 F = a
ZDD 1, 2 1, 2 1, 2 2 2, 1 #P- Knuth ZDD (Zero-suppressed Binary Decision Diagram) 2 ZDD ZDD ZDD Knuth Knuth ZDD ZDD Path Enumeration Algorithms Using ZDD and Their Performance Evaluations Toshiki Saitoh,
1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [
![1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [](/thumbs/91/106628466.jpg "1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [")
Vol.2, No.x, April 2015, pp.xx-xx ISSN xxxx-xxxx 2015 4 30 2015 5 25 253-8550 1100 Tel 0467-53-2111( ) Fax 0467-54-3734 http://www.bunkyo.ac.jp/faculty/business/ 1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The
mahoro/2011autumn/crypto/
http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 1 1 2011.9.29, ( ) http://www.ss.u-tokai.ac.jp/ mahoro/2011autumn/crypto/ 1.1 1.1.1 DES MISTY AES 1.1.2 RSA ElGamal 2 1 1.2 1.2.1 1.2.2 1.3 Mathematica
I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x
![I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x](/thumbs/103/158868201.jpg "I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ) modular symbol., notation. H = { z = x")
I. (CREMONA ) : Cremona [C],., modular form f E f. 1., modular X H 1 (X, Q). modular symbol M-symbol, ( ). 1.1. modular symbol., notation. H = z = x iy C y > 0, cusp H = H Q., Γ = PSL 2 (Z), G Γ [Γ : G]
Microsoft PowerPoint - IntroAlgDs-05-4.ppt
アルゴリズムとデータ構造入門 2005 年 0 月 25 日 アルゴリズムとデータ構造入門. 手続きによる抽象の構築.2 Procedures and the Processes They generate ( 手続きとそれが生成するプロセス ) 奥乃 博. TUT Scheme が公開されました. Windows は動きます. Linux, Cygwin も動きます. 0 月 25 日 本日のメニュー.2.
() n C + n C + n C + + n C n n (3) n C + n C + n C 4 + n C + n C 3 + n C 5 + (5) (6 ) n C + nc + 3 nc n nc n (7 ) n C + nc + 3 nc n nc n (
3 n nc k+ k + 3 () n C r n C n r nc r C r + C r ( r n ) () n C + n C + n C + + n C n n (3) n C + n C + n C 4 + n C + n C 3 + n C 5 + (4) n C n n C + n C + n C + + n C n (5) k k n C k n C k (6) n C + nc
Title 最適年金の理論 Author(s) 藤井, 隆雄 ; 林, 史明 ; 入谷, 純 ; 小黒, 一正 Citation Issue Date Type Technical Report Text Version publisher URL
Title 最適年金の理論 Author(s) 藤井, 隆雄 ; 林, 史明 ; 入谷, 純 ; 小黒, 一正 Citation Issue 2012-06 Date Type Technical Report Text Version publisher URL http://hdl.handle.net/10086/23085 Right Hitotsubashi University Repository
2012 A, N, Z, Q, R, C
2012 A, N, Z, Q, R, C 1 2009 9 2 2011 2 3 2012 9 1 2 2 5 3 11 4 16 5 22 6 25 7 29 8 32 1 1 1.1 3 1 1 1 1 1 1? 3 3 3 3 3 3 3 1 1, 1 1 + 1 1 1+1 2 2 1 2+1 3 2 N 1.2 N (i) 2 a b a 1 b a < b a b b a a b (ii)
Feynman Encounter with Mathematics 52, [1] N. Kumano-go, Feynman path integrals as analysis on path space by time slicing approximation. Bull
![Feynman Encounter with Mathematics 52, [1] N. Kumano-go, Feynman path integrals as analysis on path space by time slicing approximation. Bull](/thumbs/94/118365979.jpg "Feynman Encounter with Mathematics 52, [1] N. Kumano-go, Feynman path integrals as analysis on path space by time slicing approximation. Bull")
Feynman Encounter with Mathematics 52, 200 9 [] N. Kumano-go, Feynman path integrals as analysis on path space by time slicing approximation. Bull. Sci. Math. vol. 28 (2004) 97 25. [2] D. Fujiwara and
RIMS98R2.dvi
RIMS Kokyuroku, vol.084, (999), 45 59. Euler Fourier Euler Fourier S = ( ) n f(n) = e in f(n) (.) I = 0 e ix f(x) dx (.2) Euler Fourier Fourier Euler Euler Fourier Euler Euler Fourier Fourier [5], [6]
1 1 n 0, 1, 2,, n n 2 a, b a n b n a, b n a b (mod n) 1 1. n = (mod 10) 2. n = (mod 9) n II Z n := {0, 1, 2,, n 1} 1.
1 1 n 0, 1, 2,, n 1 1.1 n 2 a, b a n b n a, b n a b (mod n) 1 1. n = 10 1567 237 (mod 10) 2. n = 9 1567 1826578 (mod 9) n II Z n := {0, 1, 2,, n 1} 1.2 a b a = bq + r (0 r < b) q, r q a b r 2 1. a = 456,
guideline_1_0.dvi
Version 1.0 ( 22 5 ) cflkanta Matsuura Laboratory 2010, all rights reserved. I 3 1 3 2 3 3 4 II 8 4 8 5 9 5.1......................... 9 5.2......................... 10 5.3......................... 10
,.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukaw
,.,. NP,.,. 1 1.1.,.,,.,.,,,. 2. 1.1.1 (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., 152-8552 2-12-1, tatsukawa.m.aa@m.titech.ac.jp, 190-8562 10-3, mirai@ism.ac.jp
3. ( 1 ) Linear Congruential Generator:LCG 6) (Mersenne Twister:MT ), L 1 ( 2 ) 4 4 G (i,j) < G > < G 2 > < G > 2 g (ij) i= L j= N
RMT 1 1 1 N L Q=L/N (RMT), RMT,,,., Box-Muller, 3.,. Testing Randomness by Means of RMT Formula Xin Yang, 1 Ryota Itoi 1 and Mieko Tanaka-Yamawaki 1 Random matrix theory derives, at the limit of both dimension
(1) (2) (1) (2) 2 3 {a n } a 2 + a 4 + a a n S n S n = n = S n
. 99 () 0 0 0 () 0 00 0 350 300 () 5 0 () 3 {a n } a + a 4 + a 6 + + a 40 30 53 47 77 95 30 83 4 n S n S n = n = S n 303 9 k d 9 45 k =, d = 99 a d n a n d n a n = a + (n )d a n a n S n S n = n(a + a n
Siegel modular forms of middle parahoric subgroups and Ihara lift ( Tomoyoshi Ibukiyama Osaka University 1. Introduction [8] Ihara Sp(2, R) p
![Siegel modular forms of middle parahoric subgroups and Ihara lift ( Tomoyoshi Ibukiyama Osaka University 1. Introduction [8] Ihara Sp(2, R) p](/thumbs/98/138321532.jpg "Siegel modular forms of middle parahoric subgroups and Ihara lift ( Tomoyoshi Ibukiyama Osaka University 1. Introduction [8] Ihara Sp(2, R) p")
Siegel modular forms of middle parahoric subgroups and Ihara lift ( Tomoyoshi Ibukiyama Osaka University 1. Introduction [8] Ihara 80 1963 Sp(2, R) p L holomorphic discrete series Eichler Brandt Eichler
三石貴志.indd
流通科学大学論集 - 経済 情報 政策編 - 第 21 巻第 1 号,23-33(2012) SIRMs SIRMs Fuzzy fuzzyapproximate approximatereasoning reasoningusing using Lukasiewicz Łukasiewicz logical Logical operations Operations Takashi Mitsuishi
Milnor 1 ( ), IX,. [KN].,. 2 : (1),. (2). 1 ; 1950, Milnor[M1, M2]. Milnor,,. ([Hil, HM, IO, St] ).,.,,, ( 2 5 )., Milnor ( 4.1)..,,., [CEGS],. Ω m, P
![Milnor 1 ( ), IX,. [KN].,. 2 : (1),. (2). 1 ; 1950, Milnor[M1, M2]. Milnor,,. ([Hil, HM, IO, St] ).,.,,, ( 2 5 )., Milnor ( 4.1)..,,., [CEGS],. Ω m, P](/thumbs/94/118231293.jpg "Milnor 1 ( ), IX,. [KN].,. 2 : (1),. (2). 1 ; 1950, Milnor[M1, M2]. Milnor,,. ([Hil, HM, IO, St] ).,.,,, ( 2 5 )., Milnor ( 4.1)..,,., [CEGS],. Ω m, P")
Milnor 1 ( ), IX,. [KN].,. 2 : (1),. (2). 1 ; 1950, Milnor[M1, M2]. Milnor,,. ([Hil, HM, IO, St] ).,.,,, ( 2 5 )., Milnor ( 4.1)..,,., [CEGS],. Ω m, PC ( 4 5 )., 5, Milnor Milnor., ( 6 )., (I) Z modulo
1 M = (M, g) m Riemann N = (N, h) n Riemann M N C f : M N f df : T M T N M T M f N T N M f 1 T N T M f 1 T N C X, Y Γ(T M) M C T M f 1 T N M Levi-Civi
1 Surveys in Geometry 1980 2 6, 7 Harmonic Map Plateau Eells-Sampson [5] Siu [19, 20] Kähler 6 Reports on Global Analysis [15] Sacks- Uhlenbeck [18] Siu-Yau [21] Frankel Siu Yau Frankel [13] 1 Surveys
23 Study on Generation of Sudoku Problems with Fewer Clues
23 Study on Generation of Sudoku Problems with Fewer Clues 1120254 2012 3 1 9 9 21 18 i Abstract Study on Generation of Sudoku Problems with Fewer Clues Norimasa NASU Sudoku is puzzle a kind of pencil
#include #include #include int gcd( int a, int b) { if ( b == 0 ) return a; else { int c = a % b; return gcd( b, c); } /* if */ } int main() { int a = 60; int b = 45; int
ALGEBRA I Hiroshi SUZUKI Department of Mathematics International Christian University
ALGEBRA I Hiroshi SUZUKI Department of Mathematics International Christian University 2004 1 1 1 2 2 1 3 3 1 4 4 1 5 5 1 6 6 1 7 7 1 8 8 1 9 9 1 10 10 1 E-mail:hsuzuki@icu.ac.jp 0 0 1 1.1 G G1 G a, b,
IPSJ SIG Technical Report 1, Instrument Separation in Reverberant Environments Using Crystal Microphone Arrays Nobutaka ITO, 1, 2 Yu KITANO, 1
1, 2 1 1 1 Instrument Separation in Reverberant Environments Using Crystal Microphone Arrays Nobutaka ITO, 1, 2 Yu KITANO, 1 Nobutaka ONO 1 and Shigeki SAGAYAMA 1 This paper deals with instrument separation
2. Eades 1) Kamada-Kawai 7) Fruchterman 2) 6) ACE 8) HDE 9) Kruskal MDS 13) 11) Kruskal AGI Active Graph Interface 3) Kruskal 5) Kruskal 4) 3. Kruskal
1 2 3 A projection-based method for interactive 3D visualization of complex graphs Masanori Takami, 1 Hiroshi Hosobe 2 and Ken Wakita 3 Proposed is a new interaction technique to manipulate graph layouts
<4D F736F F D20838A B F955C8E8682A982E796DA8E9F914F E718F9096BC816A5F E646F63>
2008 年度版リストガイド ( 電子署名 ) 平成 21 年 3 月 独立行政法人情報通信研究機構独立行政法人情報処理推進機構 1 1 1.1............................. 1 1.1.1............................ 1 1.1.2....................... 1 1.1.3...........................
Real AdaBoost HOG 2009 3 A Graduation Thesis of College of Engineering, Chubu University Efficient Reducing Method of HOG Features for Human Detection based on Real AdaBoost Chika Matsushima ITS Graphics
80 X 1, X 2,, X n ( λ ) λ P(X = x) = f (x; λ) = λx e λ, x = 0, 1, 2, x! l(λ) = n f (x i ; λ) = i=1 i=1 n λ x i e λ i=1 x i! = λ n i=1 x i e nλ n i=1 x
80 X 1, X 2,, X n ( λ ) λ P(X = x) = f (x; λ) = λx e λ, x = 0, 1, 2, x! l(λ) = n f (x i ; λ) = n λ x i e λ x i! = λ n x i e nλ n x i! n n log l(λ) = log(λ) x i nλ log( x i!) log l(λ) λ = 1 λ n x i n =
23 Fig. 2: hwmodulev2 3. Reconfigurable HPC 3.1 hw/sw hw/sw hw/sw FPGA PC FPGA PC FPGA HPC FPGA FPGA hw/sw hw/sw hw- Module FPGA hwmodule hw/sw FPGA h
23 FPGA CUDA Performance Comparison of FPGA Array with CUDA on Poisson Equation (lijiang@sekine-lab.ei.tuat.ac.jp), (kazuki@sekine-lab.ei.tuat.ac.jp), (takahashi@sekine-lab.ei.tuat.ac.jp), (tamukoh@cc.tuat.ac.jp),
1 Abstract 2 3 n a ax 2 + bx + c = 0 (a 0) (1) ( x + b ) 2 = b2 4ac 2a 4a 2 D = b 2 4ac > 0 (1) 2 D = 0 D < 0 x + b 2a = ± b2 4ac 2a b ± b 2
1 Abstract n 1 1.1 a ax + bx + c = 0 (a 0) (1) ( x + b ) = b 4ac a 4a D = b 4ac > 0 (1) D = 0 D < 0 x + b a = ± b 4ac a b ± b 4ac a b a b ± 4ac b i a D (1) ax + bx + c D 0 () () (015 8 1 ) 1. D = b 4ac
15 mod 12 = 3, 3 mod 12 = 3, 9 mod 12 = N N 0 x, y x y N x y (mod N) x y N mod N mod N N, x, y N > 0 (1) x x (mod N) (2) x y (mod N) y x
A( ) 1 1.1 12 3 15 3 9 3 12 x (x ) x 12 0 12 1.1.1 x x = 12q + r, 0 r < 12 q r 1 N > 0 x = Nq + r, 0 r < N q r 1 q x/n r r x mod N 1 15 mod 12 = 3, 3 mod 12 = 3, 9 mod 12 = 3 1.1.2 N N 0 x, y x y N x y
<4D F736F F D B B83578B6594BB2D834A836F815B82D082C88C60202E646F63>
確率的手法による構造安全性の解析 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/55271 このサンプルページの内容は, 初版 1 刷発行当時のものです. i 25 7 ii Benjamin &Cornell Ang & Tang Schuëller 1973 1974 Ang Mathematica
1 4 1 ( ) ( ) ( ) ( ) () 1 4 2
7 1995, 2017 7 21 1 2 2 3 3 4 4 6 (1).................................... 6 (2)..................................... 6 (3) t................. 9 5 11 (1)......................................... 11 (2)
untitled
API API Part 1 10API 25 10API Part2 Copyright (c) 2004 NPO Page 2 Copyright (C) 2004 NPO JNSA 1 API API Wassenaar API Copyright (c) 2004 NPO Page 4 Copyright (C) 2004 NPO JNSA 2 56 512512 112 IC 1 I II
03.Œk’ì
HRS KG NG-HRS NG-KG AIC Fama 1965 Mandelbrot Blattberg Gonedes t t Kariya, et. al. Nagahara ARCH EngleGARCH Bollerslev EGARCH Nelson GARCH Heynen, et. al. r n r n =σ n w n logσ n =α +βlogσ n 1 + v n w
kato-kuriki-2012-jjas-41-1.pdf
Vol. 41, No. 1 (2012), 1 14 2 / JST CREST T 2 T 2 2 K K K K 2,,,,,. 1. t i y i 2 2 y i = f (t i ; c) + ε i, f (t; c) = c h t h = c ψ(t), i = 1,...,N (1) h=0 c = (c 0, c 1, c 2 ), ψ(t) = (1, t, t 2 ) 3
NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1
![NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1](/thumbs/94/118607815.jpg "NP 1 ( ) Ehrgott [3] ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1")
NP 1 ( ) Ehrgott [3] 2 1 1 ( ) (Ehrgott [3] ) Ulungu & Teghem [8] Zitzler, Laumanns & Bleuler [11] Papadimitriou & Yannakakis [7] Zaroliagis [10] 2 1 1 1 Avis & Fukuda [1] 2 NP (Ehrgott [3] ) ( ) 3 NP
waseda2010a-jukaiki1-main.dvi
November, 2 Contents 6 2 8 3 3 3 32 32 33 5 34 34 6 35 35 7 4 R 2 7 4 4 9 42 42 2 43 44 2 5 : 2 5 5 23 52 52 23 53 53 23 54 24 6 24 6 6 26 62 62 26 63 t 27 7 27 7 7 28 72 72 28 73 36) 29 8 29 8 29 82 3
Trapezoidal Rule θ = 1/ x n x n 1 t = 1 [f(t n 1, x n 1 ) + f(t n, x n )] (6) 1. dx dt = f(t, x), x(t 0) = x 0 (7) t [t 0, t 1 ] f t [t 0, t 1 ], x x
![Trapezoidal Rule θ = 1/ x n x n 1 t = 1 [f(t n 1, x n 1 ) + f(t n, x n )] (6) 1. dx dt = f(t, x), x(t 0) = x 0 (7) t [t 0, t 1 ] f t [t 0, t 1 ], x x](/thumbs/92/107866474.jpg "Trapezoidal Rule θ = 1/ x n x n 1 t = 1 [f(t n 1, x n 1 ) + f(t n, x n )] (6) 1. dx dt = f(t, x), x(t 0) = x 0 (7) t [t 0, t 1 ] f t [t 0, t 1 ], x x")
University of Hyogo 8 8 1 d x(t) =f(t, x(t)), dt (1) x(t 0 ) =x 0 () t n = t 0 + n t x x n n x n x 0 x i i = 0,..., n 1 x n x(t) 1 1.1 1 1 1 0 θ 1 θ x n x n 1 t = θf(t n 1, x n 1 ) + (1 θ)f(t n, x n )
Bulletin of JSSAC(2014) Vol. 20, No. 2, pp (Received 2013/11/27 Revised 2014/3/27 Accepted 2014/5/26) It is known that some of number puzzles ca
Bulletin of JSSAC(2014) Vol. 20, No. 2, pp. 3-22 (Received 2013/11/27 Revised 2014/3/27 Accepted 2014/5/26) It is known that some of number puzzles can be solved by using Gröbner bases. In this paper,