3 487,,,,,, 50 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 28, 29, 30, 31, 32, 33, 34, 35, 36, 3

32 3 2002 5 M A TH EM A T ICS IN PRA CT ICE AND TH EO R Y V o l132 N o13 M ay, 2002 1 (, 300071),, 1992,,,,, ( ) ( ) ( ) ; ; ; 1,,,, 19 (Gau ss, 1777 1855),,,,,, ( ), 1, 2, 3, 4,,, ( ),,,,, 1 100,,, 19 K ronecker (1823 1891),,, D ick son (1874 1954) 20 H ardy (1877 1947) H ardy, 2001208228 1 N um ber T heo ry fo r Computing, 2nd Edition, Sp ringer2v erlag, 2001, ( ), 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 487,,,,,, 50 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 50, 1; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47; 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50 1, ( ) (p rim e num ber), (com po site num ber),, 1,,, 1,,, 2, ( ) ; 2 ( ),, Π(x ) lim = 0, (1) x x Π(x ) 2 x,, 2000 (Euclid) ( E lem en ts ), lim Π(x ) = (2) x ( ),, Π(x ) lim = 1 (3) x x glnx ( ), 1, (3, 5), (5, 7), (11, 13), 318032361 2 107001 1, 32220 (p, p + 2, p + 6) (p, p + 4, p + 6), p, p + 2, p + 4, p + 6 ; (5, 7, 11), (11, 13, 17) (17, 19, 23) (p, p + 2, p + 6), (7, 11, 13), (13, 17, 19) (37, 41, 43) (p, p + 4, p + 6), (p, p + 2, p + 4),, (3, 5, 7), ( (M ersenne, 1588 1648) 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

488 32 ), 2 p - 1, p ( p 2 p - 1 ) ; 2 p - 1, 2 p - 1 (2 p - 1), 6, 6= 1+ 2+ 3 Ρ(N ) N ( N ), N Ρ(N ) = 2N 28, Ρ(28) = 1+ 2+ 4+ 7+ 14+ 28= 56 2000, 4 6, 28, 496, 8128,, 38 ; 2 6972593-1 (2 6972593-1), 2 6972593-1 ( 2098980 ), 2, N N = 2 p - 1 (2 p - 1), 2 p - 1, (Eu ler, 1707 1783),, 2000 (, 2000 ),, ( ; ) (am icab le num ber), (M, N ) Ρ(M ) = Ρ(N ) = M + N ( ) (220, 284) 2500 (Pythago ras),,, (sociab le num ber), (M 1,M 2,,M n) Ρ(M 1) = M 1 + M 2 Ρ(M 2) = M 2 + M 3 Ρ(M n) = M n + M 1 ( ) [ 14,, ] ( Perfect, Am icab le and Sociab le N um bers, W o rld Scien tific, 1996 ), (4) N = p Α 1 1 p Α 2 2 p Α k k (5) p i, i= 1, 2,, k, Αi 15, 15= 3 5 99, 99= 3 2 11,,,,, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 489 1000= 2 3 5 3 1001= 7 11 13 1002= 2 3 167 1003= 17 59 1004= 2 2 251 1005= 3 5 67 1006= 2 503 1007= 19 53 1008= 2 4 3 2 7 1009= 1009 1010= 2 5 101 1011= 1011,, ( ),!,, 1 (, ),,,,,,,, 2,,, ( ),,,, ( ) 211,,,, 18, ( ) Π(x ) x, Π(x ), Π(x ) L i(x ), L i(x ) = x dt 0 ln t = lim Π(x ) x glnx, (6) Π(x ) lim = 1 (7) x x glnx Γ 0 1- Γ 0 Π(x ) lim x L i(x ) = 1 + x d t 1+ Γ ln t,, (7) ( 1) ; 1 Π(x ), 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

490 32 100,,!, H adam ard (1865 1963), D e la V all e2 Pou ssin (1866 1962) ; H adam ard 98, D e la V all e2pou ssin 96,,, (, ) Selberg ( 1917, ) Selberg 1949, 1950 (F ields) 2000 ( ),,,! x Π(x ) 1 x lnx Π(x ) x glnx 10 1 4 4 3 0 93 10 2 25 21 7 1 152 10 3 168 144 8 1 16 10 4 1229 1085 7 1 13 10 5 9592 8685 8 1 131 10 6 78498 72382 5 1 084 10 7 664579 620420 5 1 071 10 8 5761455 5428680 9 1 061 10 9 50847534 48254942 5 1 053 10 10 455052511 434294481 9 1 047 10 11 4118054813 3948131653 7 1 043 10 12 37607912018 36191206825 3 1 039 10 13 346065536839 334072678387 1 1 035 10 14 3204941750802 3102103442166 0 1 033 10 15 29844570422669 28952965460216 8 1 030 10 16 279238341033925 271434051189532 4 1 028 10 17 2625557157654233 2554673422960304 8 1 027 10 18 24739954287740860 24127471216847323 8 1 025 10 19 234057667276344607 228576043106974646 1 1 023 10 20 2220819602560918840 2171472409516259138 2 1 022 10 21 21127269486018731928 20680689614440563221 4 1 021 212 (Goldbach) 1742, (1690 1764) (Eu ler, 1707 1783) ; (,,, ), 4, ( 1 + 1) 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 491 6= 3+ 3 8= 3+ 5 10= 3+ 7= 5+ 5 12= 5+ 7 14= 3+ 11= 7+ 7 16= 3+ 13= 5+ 11 18= 5+ 13= 7+ 11 20= 3+ 17= 7+ 13,, 4 10 14,,,,,! (1933 1996) 1966 ( 1972 ), 1+ 2,, 40!,,, 1+ 2 1+ 1 Faber 2000 3 20, 100,!, ( ) ( ), 7, 9= 3+ 3+ 3, 11= 3+ 3+ 5, 13= 3+ 5+ 5, 15= 3+ 5+ 7, 9 10 20 ;, 10 20 ; 10 43000,, 10 20 10 43000, (, ),,, (,,, ), n> 2, xy z 0, x n + y n = z n (8), (D iophantus, 200 284 ) A rithm etica, 13, 6, 1g6, 1g12, 1g7 5, 4, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

492 32, (,, ax + by = c x 2 - N y 2 = n ) 350,, (8),, 350,, 1993 1995 A ndrew W iles 213 (R iemann) (1826 1866), ( ), 1 Φ(s) = (9) p 1 - p - s (, s ) s= Ρ+ it (Ρ> 1), 1 Φ(s) = (10) n s n= 1,, 1859 6,,, ( ),,,, H adam ard D e la V all e2pou ssin,, 40 ( ), Φ(s) Ρ= 1 2,,, Φ 1, 500, 000, 001,, 1, ;, 1, 1 1900, (H illbert, 1862 1943) 20 23 20, 21,, Ferm at (1601 1665),, Ferm at Ferm at Ferm at Ferm at p, a> 1, gcd (a, p ) = 1, a p - 1 1 (mod p ); Ferm at n> 2, xy z 0, x n + y n = z n ;, Ferm at Pascal 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 493 1 C lay 2000 5 24, 100,,, 22! 214 1,,,,, 1,, ; ( ), ( ),,, O ( logn ) k, k, N O ( logn ) k ( ) O ( logn ) 11, O ( N ) 0 1, O ( N ) 0 1 = O (20 1 (logn ) ) 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

494 32, 1, 1 N ( 1 ), N 2 N ( N N, 133 = 11 53 = 11), N 2, N 3, N 5,, NN 0, N ; N, N N m od M M, 97 m od 3= 1 97 3 1 ( 32, ) N = 113, 113 = 10, 2 10, 113 m od 2= 1, 113 m od 3= 2, 113 m od 5= 3, 113 m od 7= 1, 113 m od 9= 5 2 10, 113 m od 2= 1, 113 m od 3= 2, 113 m od 5= 3, 113 m od 7= 1 0, 113 N = 133, 133 = 11, 2 11 ( ) 133 m od 2= 1, 133 m od 3= 1, 133 m od 5= 3, 133 m od 7= 0 7, 0, 133, N, N, O ( N ) 1g2 ( ),, ( ),,O ( N ) 1g2 O (2 (logn ) g2 ),! O ( log N ) c log log log N,, N, N, Ferm at N, 2 N - 1 1 (mod N ) (11) 2 N - 1 g 1 (m od N ), N,, 2 N - 1 1 (m od N ), N, 1g4,, M iller2r ab in N = 1+ 2 j d ( d ), {b d, b 2d, b 4d, b 8d,, b 2j- 1d, b 2j d } mod N (12) (1, 1,, 1, 1, 1,, 1), (13) (?,?,,?, - 1, 1,, 1), (14) 1< b< N,? 1 N,, b= 2, n= 2047, n- 1= 2 1 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 495 1023, d = 1023, 2 1023 1 (m od 2047), 2 2046 1 (m od 2047), 2047, 2047= 23 89 b, b, Carm ichael ; Robert Carm icheal (1879 1967),, 561, 1105, 1729 Carm ichael, a (i) a N - 1 1 (m od N ), (ii) a (N - 1) gp g 1 (m od N ), N - 1 p, N,, N, N - 1, N - 1 N,, ( ),,, (zero2erro r) M iller2r ab in (one2sided erro r),, 215,,,,,,,,,, 20 70,,,,, ( ) Po llard, O ( exp (c (log N ) 1g3 (log log N ) 2g3 ) ) L en stra, y 2 = x 3 + ax + b, (15) ( 2) E, P 1 P 2 P 3, P 1g P 2 P 3 X, Q = P 1+ P 2,, P 1= John Po llard,, R uth, R uth 1958 F ields ( N obel ), 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

496 32 (x 1, y 1), P 2= (x 2, y 2) E, E P 3= P 1g P 2= (x 3, y 3) (x 3, y 3) = (Κ 2 - x 1- x 2, Κ(x 1- x 3) - y 1) (16) Κ= (3x 2 1 + a), P 1 = P 2, 2y 1 (y 2 - y 1), P 1 P 2 (x 2 - x 1) (17) Q = P + P + + P (m od N ) (18) Q, Q k P N = 187 k = 6 2 (k,, k 1, 2, 3 ) P = (0, 5) E y 2 = x 3 + x + 25, 4a 3 + 27b 2 0 6P, 2P = P g P = (0, 5) g (0, 5) 3P = P g 2P = (0, 5) g (144, 18) Κ= m 1 = 1 131 (m od 187) m 2 10 x 3 144 (m od 187) y 3 18 (m od 187) Κ= m 1 = 13 178 (m od 187) m 2 144 x 3 124 (m od 187) y 3 176 (m od 187) 6P = 2 (3P ) = 2 (124, 176) = (124, 176) g (124, 176) Κ= m 1 = 46129 m 2 352 127 165 ( m od 187) 127g165 m od 187,! 187 165 gcd (N, m 2) = gcd (187, 165) = 11, 187, 187 = 11 17 Z187, Zn n Z187,,, Z187,, 187,, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 497,, (N um ber F ield Sieve) R SA 2155, 155 (512 ), 102639592829741105772054196573991675900716567808038066803341933521790711307779, 106603488380168454820927220360012878679207958575989291522270608237193062808643, A T &T Peter Sho r 1996,, O (log N ) 2 (log log N ) (log log log N ) = O (log N ) 2+ Ε x r Z 3 N x r 1 (mod N ) (19) r,, x, 1 N = 179359, x = 3, r= 14718 N 3 1 m od 179359 = 3 3 2 m od 179359 = 9 3 3 m od 179359 = 27 3 1000 m od 179359 = 31981 3 1001 m od 179359 = 95943 3 14717 m od 179359 = 119573 3 14718 m od 179359 = 1 gcd (x rg2 + 1, N ), gcd (x rg2-1,n ) = (67, 2677), N = 179359 = 67 2677 Z 3 N,, 10 150, 1000, 3 10 80, ( Fou rier ), ( ),! (, ), N P2, N P2,,, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

N P2, Sho r, Sho r,,,, 216 498 32, a, y,n, x ( x ), y a x (mod N ) (20) a (p rim itive roo t), y Z 3 N, x, y a x (m od N ) Z 3 N x y m od N, x logay (m od N ), (21) x = indn, a (y ) (22), 2 Z 3 13, y = 1, 2, 3,, 12 2 ind13, 2 (a) y 1 2 3 4 5 6 7 8 9 10 11 12 ind13, 2 (y ) 12 1 4 2 9 5 11 3 8 10 7 6,,, N FS,, Silver, Poh lig H ellm an 1978 Fq, O p, p q- 1, q, ( q q- 1 ) [1 ] q- 1 q - [2 ], k 1 = p Α 1 1 p Α 2 2 p Α k k i= 1 rp i, j = a j (q- 1) gp i mod q, 0 Φ j < p i (23) [ 3 ] x = logab m od q, x m od p Α i i x m od p Α i i, p i x mod p Α i i = x 0 + x 1p i + + x Α i - 1p Α i - 1 i, (24) 0Φ x n< p i- 1, x 0, x 1,, [321 ] x 0, b (q- 1) gp i, j,, j, x 0= j b (q- 1) gp i mod q = rp i, j, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved rp i

3 499 b (q- 1) gp i a x (q- 1) gp i a x 0 (q- 1) gp i m od q = rp i, x 0 [322 ] x 1, b1= ba - x 0 b (q- 1) gp 2 i 1 mod q = rp i, j x 1= j, b (q- 1) gp 2 i 1 a (x - x 0 ) (q- 1) gp 2 i a (x 1 + x 2 p i + ) (q- 1) gp i a x 1 (q- 1) gp i mod q = rp i, x 1 [323 ] x 2, b2= ba - x 0 - x 1 p i, b (q- 1) gp 3 i 2 mod q, x 0, x 1,, x Α i - 1 [4 ] x, x m l m od p Α l l, l = 1, 2,, k,,,, F Α p, ( P, Q, p Α ), P, Q E, p Α, k, Q = kp (m od p Α ) (25), k, k = logpq (m od p Α ) (26) k, 3, ( ), ( ) 311,, En igm a En igm a,,, 100 M ilton Kynes ( B letch ley Park, B letch ley Park), ( T u ring M ich ie), En igm a, T u ring, En igm a 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

500 32,,,, 10 2000 4 24 8,,,,,,,,,,,,,, 1976, Stanfo rd H ellm an D iffie M erk le,, (,, ), (,, ),, ( ), ( ) Stanfo rd,,, (A lice) B (Bob) ( ), A B q Fq g A a {1, 2,, q- 1} g a m od q B B b {1, 2,, q- 1} g b m od q A A (g b ) a m od q, B (g a ) b m od q (g b ) a m od q= (g a ) b m od q= g ab m od q, A B g ab m od q,, 3 3 D iffie2h ellm an2m erk le g key, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 501, g, q, g a m od q, g b m od q,,, g, q, g a m od q, g b m od q a b, g ab m od q,, F q, a b A B q= 2 739 (7 149-1) g6+ 1 g = 7 A a, 7 a (m od q), B ( a ) B 7 a (m od q) = 12740218011997394682426924433432284974938204258693162165 45577352903229146790959986818609788130465951664554581442 80588076766033781 B b, 7 b (m od q), A ( b ) A 7 b (m odq) = 18016228528745310244478283483679989501596704669534669731 3025121734059953772084759581769106253806921016518486623 62137934026803049 A B 7 ab (m od q),, a b, q 129, N FS a b, 7 ab (m od q), q 155, 200 1978, Stanfo rd ( ), M IT, R ivest, Shm ir A dlem an, R SA C = M e mod N (27) M = C d mod N (28) M, C, (N, e) ( ), (N, d ) ( ), N = p q, p q 100, ed 1 (m od <(N ) ), < (e, N ),,, p q ( d ),, N = p q, <(N ) = (p - 1) (q - 1) (29) d 1ge (mod <(N ) ) (30), 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

502 32 N = k p Α i i= 1 <(N ) = N k 1 - i= 1 i (31) 1 p i (32), ( ), d, <(N ), <(N ), N,,, N 200, N,,,, R SA (, ),,, 1) D iffie2h ellm an2m erk le A B F q (q= p r ), F q E, E P,, E A a {1, 2,, q- 1} ap m od q B B b {1, 2,, q- 1} bp m od q A A a (bp ) m od q, B b (ap ) m od q a (bp ) m od q= b (ap ) m od q= (ab) P m od q, A B (ab) P m od q,,, g, P, ap m od q, bp m od q,, P, q, ap m od q, bp m od q a b, (ab) P m od q ( ), (, ), F q P, a b P E 2) E lgam al A lice Bob Fq (q= p r, p ) E, A lice ra, rap ; Bob rb, rbp Bob M, A lice k, (kp,m + k ( rbp ) ) M, Bob M + k (rbp ) - rb (kp ) = M (33) 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 503 rb,, P rbp, ( ),, ( R SA ),,,,,!,,,! 312,,,,?, x 2 (mod 3), x 3 (mod 5), x 2 (mod 7), x = 70 2 + 21 3 + 15 2-2 105 = 23, x a 1 (m od m 1), x a 2 (m od m 2), x a n (m od m n), (34) x n a im im i (mod m ) (35) i= 1 m = m 1m 2 m n (36) M i = m gm i (37) M i = M - 1 i (mod m i) (38) i= 1, 2,, n ( ) (, ), ( ),,,,, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

504 32,,,,,,,, ;,,,,,,,,,, z = x + y = 123684+ 413456, 100,,,,,,, ;,, x 33 (m od 99), y 32 (m od 99), x 8 (m od 98), y 92 (m od 98), x 9 (m od 97), y 42 (m od 97), x 89 (m od 95), y 16 (m od 95), z = x + y 65 (m od 99), z = x + y 2 (mod 98), z = x + y 51 (m od 97), z = x + y 10 (m od 95) (39) i= 1, 2, 3, 4 x + y mod 99 98 97 95 z 4 M im iz i (mod m ), i= 1 m = m 1m 2m 3m 4, M i = m gm i, M im i 1 (m od m i), M = 99 98 97 95 = 89403930, M 1 = M g99 = 903070, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved (39)

3 505 M 2 = M g98 = 912285, M 3 = M g97 = 921690, M 4 = M g95 = 941094 i= 1, 2, 3, 4 M i x + y 4 z im im i (m od m ) i= 1 903070M 1 91M 1 1 (mod 99), 912285M 2 3M 2 1 (m od 98), 921690M 3 93M 3 1 (mod 97), 941094M 4 24M 4 1 (mod 95) M 1 37 (m od 99), M 2 38 (m od 98), M 3 24 (m od 97), M 4 4 (m od 95) 65 903070 37 + 2 912285 33 + 51 921690 24 + 10 941094 4 (mod 89403930) 3397886480 (mod 89403930) 537140 (mod 89403930) 0< x + y = 537140< 89403930, x + y = 537140,, n k (k Φ n) ( 5 3 ), (k, n), S n n k,, k k S, ; k S,, (k, n) (, k= 3, n= 5) m i m 1 = 97, m 2 = 98, m 3 = 99, m 4 = 101, m 5 = 103, M = m 1m 2m 3m 4m 5 = 9790200882 m in (k) = m 1m 2m 3 = 941094 m ax (k - 1) = m 4m 5 = 10403 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

506 32 S 10403 < S = 671875 < 941094 P i I i (I i,m i,m ) P i S I 1 (m od m 1) ] I 1 = 53 S I 2 (m od m 2) ] I 2 = 85 S I 3 (m od m 3) ] I 3 = 61 S I 4 (m od m 4) ] I 4 = 23 S I 5 (m od m 5) ] I 5 = 6 P 1, P 2, P 3 S M 1 = M gm 1 = 100929906 M 2 = M gm 2 = 99900009 M 3 = M gm 3 = 98890918 N 1 M - 1 1 (m od m 1) ] N 1 = 95 N 2 M - 1 2 (m od m 2) ] N 2 = 13 N 3 M - 1 3 (m od m 3) ] N 3 = 31 S I 1gM 1gN 1 + I 2gM 2gN 2 + I 3gM 3gN 3 (mod m 1gm 2gm 3) 53g 100929906g 95 + 85g 99900009g 13 + 61g 98890918g 31 (mod 97g 98g 99) 805574312593 (mod 941094) = 671875 S, I 1, I 2, I 3, I 4, I 5 S, I 1 I 4 S, S I 1gM 1gN 1 + I 4gM 4gN 4 (m od m 1gm 4) 53g 100929906g 95 + 23g 96932682g 61 (mod 97g 101) 644178629556 (m od 9791) = 5679 S, I 1, I 2, I 3, I 4, I 5 S 4,, ( H ardy D ick son ),, 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

3 507,, [ 3 1992 ],,,!,,,,,, ( ), -,,,,,,!,,, ;,, [ 1 ] A tk in A O L, M o rain F E llip tic curves and p rim ality p roving[j ] M athem atics of Computation, 1993, 61 29 68 [ 2 ] B rickell E F, Go rdon D M, M ccurley K S, W ilson D S Fast Exponentiation w ith P recomputation [M ] P roceedings of Eurocryp t 92, L ecture N o tes in Computer Science 658, Sp ringer2v erlag, 1992 [ 3 ] 1 [J ]1, 1992, 21 (4) 385 387 [ 4 ] D iffie W, H ellm an E N ew directions in C ryp tography [J ] IEEE T ransactions on Info rm ation T heo ry, 1976, 22 (5) 644 654 [ 5 ] E lgam al T A public key cryp to system s and a signature schem e based on discrete logarithm s [ J ] IEEE T ransactions on Info rm ation T heo ry, 1985, 31 (5) 496 472 [ 6 ] E llis G R ings and F ields[m ] O xfo rd U niversity P ress, 1992 [ 7 ] Go rdon D M, M ccurley K S M assively Parallel Computato in of D iscrete L ogarithm s[m ] P roceedings of C ryp t 92, L ecture N o tes in Computer Science 740, Sp ringer2v erlag, 1992 [ 8 ] Koblitz N E llip tic curve cryp tography[j ] M athem atics of Computato in, 1987, 48 203 209 [ 9 ] Koblitz N A Course in N um ber T heo ry and C ryp tography[m ] 2nd Edition, Sp ringer2v erlag, 1994 [ 10 ] L enstra H W, J r Facto ring integers w ith ellip tic curves[j ] A nnals of M athem atics, 1987, 126 649 673 [ 11 ] R ivest R L, Sham ir A, A dlem an L A m ethod fo r obtaining digital signatures and public key cryp to system s[j ] Comm unications of the A CM, 1978, 21 (2) 120 126 [ 12 ] Silverm an J H T he A rithm etic of E llip tic Curves[M ] Sp ringer2v erlag, 1986 [ 13 ] W iles A M odular ellip tic curves and the ferm at s last theo rem [J ] A nnals ofm athem atics, 1995, 141 443 551 [ 14 ] Yan S Y perfect, Am icable and Sociable N um bers[m ] W o rld Scientific, 1996 [ 15 ] Yan S Y N um ber T heo ry fo r Computing[M ] 2nd Edition, Sp ringer2v erlag, 2001 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved

508 32 Num ber Theory and its Application s D edicated to P rof Sh iing2shen Chern fo r h is 90th B irthday YAN Song2yuan (Co llege of Info rm ation Science, N ankai U n iversity, T ian jin 300071, Ch ina) Abstract N um ber theo ry had long been considered as the purest branch of m athem atics, w ith very few app lications to o ther areaṡ R ecent years, how ever, have seen considerable increase in interest in several central top ics of num ber theo ry, p recisely because of their impo rtance and app lication s in o ther areas, particu larly in com pu ting and info rm ation techno logy Today, num ber theo ry has been app lied to such diverse areas as physics, chem istry, engineering, acou stics, b io logy, com pu ting, coding and cryp tography, digital comm un ication s, graph ics design, and even m usic T hus, num ber theo ry, as po inted out by the em inent m athem atican Sh iing2shen Chern, is no mo re just a pure branch of m athem atics but also a very app licable subject of m athem aticṡ In th is paper, w e shall first review som e basic concep ts of num ber theo ry, then w e shall introduce som e impo rtant (mo stly difficult and unso lved) p roblem s in num ber theo ry F inally, w e shall discuss various app lications of num ber theo ry (particularly the difficult and unso lved num ber2theo retic p roblem s) in cryp tography (including netw o rk and info rm ation secu rity) and com pu ting science (particu larly fast and parallel com pu tation) Keywords num ber theo ry; computational num ber theo ry; cryp tography; fast computation 1995-2004 Tsinghua Tongfang Optical Disc Co, Ltd All rights reserved