- PDF 無料ダウンロード

Size: px

Start display at page:

Download ""

ぜんますわ
5 years ago
Views:

4 #include <stdio.h> #include <stdlib.h> #include <math.h> 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 c = gcd( a, b ); printf( "gcd(%d, %d) = %d\n", a, b, c ); return 0; }

5 kauai:yama550> gcc euclid.c -o euclid kauai:yama552>./euclid gcd(60, 45) = 15 kauai:yama553>

6 6 = 2 3 = (1 + 5)(1 5)

8 int gcd( int a, int b) { if ( b == 0 ) return a; else { int c = a % b; return gcd( b, c); } /* if */ }

9 int gcd( int a, int b) { if ( b == 0 ) return a; else { int c = a % b; return gcd( b, c); } /* if */ }

10 O

12 O(f(n)) = g(n) g(n) c f(n) Θ(f(n)) = g(n) c 2 f(n) g(n) c 1 f(n) Ω(f(n)) = g(n) c f(n) g(n)

13 g 1 (n) = O(n 2 ), g 2 (n) = O(n 3 ) g 1 (n) + g 2 (n) = O(n 3 )

14 GCD(x 4 + x 2 + 1, x 3 1) (x 4 + x 2 + 1) (x 3 1) = x... x 2 + x + 1 (x 3 1) (x 2 + x + 1) = (x 1)... 0

15 CGD(x 4 + 3x 3 + x + 1, 31x 2 + 1) x

16 GCD(x x 3 + x + 1, 31x 2 + 1) x

17 int mult(int a, int b) { int i; int s = 0; for (i = 0; i < b; i++ ){ s = s + a; } return s; } /* mult */ O(n + m)

18 int mult2(int a, int b) { if (b == 0) return 0; else if (b % 2 == 0){ int mm = mult2(a, b / 2); return mm + mm; } else { int mm = mult2(a, b / 2); return mm + mm + a; } /* if */ } /* mult2 */ a 2b = 2(a b ) a (2b + 1) = 2(a b )+a O(log n + log m)

19 O((log n + log m) 2 ) int mult3(int a, int b) { if (b == 0) return 0; else if (b % 2 == 0){ int mm = mult3(a, b / 2); return mm * 2; } else { int mm = mult3(a, b / 2); return add2(mm * 2, a); } /* if */ } /* mult3 */ int add2(int a, int b) { if (b == 0) return a; else if (a == 0) return b; else { int mm = add2(a / 2, b / 2); if (a % 2 > 0 && b % 2 > 0) return (mm + 1) * 2; else if (a % 2 > 0 && b % 2 == 0) return mm * 2 + 1; else if (a % 2 == 0 && b % 2 > 0) return mm * 2 + 1; else return mm * 2; } } /* add2 */

20 x n = x x x O

21 int exp(int a, int n) { if (n == 0) return 1; else { int m = exp(a, n / 2); m = m * m; if (n ) m = m * a; } return m; F F (n) = F (n/2) + c F (n) = O(log n)

22 a 1000 = (a 500 ) 2 a 500 = (a 250 ) 2 a 250 = (a 125 ) 2 a 125 = (a 61 ) 2 a a 61 = (a 30 ) 2 a a 30 = (a 15 ) 2 a 15 = (a 7 ) 2 a a 7 = (a 3 ) 2 a a 3 = a 2 a

24 p i p ( ) p p i ( ) p p! = i (p i)!i! a b a b = p (p 1) 2 1 (p i) (p i 1) 2 1 i (i 1) 2 1 p p p

25 x y (x + y) p = p ( p i ) x i y p i i=0 p i p p

26 p (x + y) p = p i=0 ( p i ) x i y p i (modp) = x 0 y p + x p y 0 (mod p) = x p + y p (mod p)

27 a p =( ) p a =1 p +1 p + +1 p (mod p) a = (mod p) a = a(mod p) a p 1 = 1(mod p)

28 #include <stdio.h> #include <stdlib.h> int myexp(int x, int i, int p); int myexp(int x, int i, int p) { if ( i == 0 ) return 1; else { int j = myexp( x, i / 2, p ); j = (j * j) % p; if (i % 2 == 1) j = (j * x) % p; return j; } /* if */ } /* myexp */ int main() { enum{ N = 13}; int i; for (i = 0; i < N; i++ ){ printf( "%5d%5d\n", i, myexp( i, N - 1, N )); } /* for */ return 0; } /* main */ a p 1 = 1(mod p)

29 a a a n

30 n a a n 1 = 1(mod p)

32 いくつかの数に対するFermatテスト n 素数か否かによってかなり状況は異なる 555 合成数青 FermatテストOK 赤 FermatテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

34 p p x x p x 2 = 1(mod p) (x 1)(x + 1) = 0(mod p) x 1 = 0(mod p) x + 1 = 0(mod p) x = ±1(mod p)

35 p p d a d = 1(modn) 0 i < s, a 2id = 1(modn)

36 a d 1(mod n) 0 i < s, a 2id 1(modn) p

37 d a d 1(mod n) 0 i < s, a 2id 1(modn)

38 p p

39 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

40 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

41 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

42 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

43 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

44 いくつかの数に対するMRテスト n 素数か否かによってかなり状況は異なる 555 合成数青 MRテストOK 赤 MRテストNG 557 素数 559 合成数 561 合成数カーマイケル数 563 素数

46 O ((log n) 7.5 )

47 R. L. Rivest, A. Shamir, and L. Adelman: A method for obtaining digital signature and public-key cryptsystems. MIT Laboratory for Computer Science Technical Memo LCS/TM82; April 4,1977 (Revised December 12,1977).

48 pq n p q n e de n d m m e (m e ) d = m de mod

49 de = 1(mod n ) c = m e (mod n) c d = (m e ) d = m ed (mod n) m n = (m q 1 ) p 1 = 1(mod p) m n = (m p 1 ) q 1 = 1(mod q) de = n k + 1 m n 1 = 0(mod pq) m de = m n k+1 = (m n ) k m = m (mod pq)

50 n = pq e d d e e d

52 public static BigInteger find_a_prime_number(biginteger start, Random r){ BigInteger ii = start.subtract( one ); while ( true ){ ii = ii.add( one ); if (ii.remainder( two ).equals( zero ) ) continue; if (ii.remainder( three ).equals( zero ) ) continue; if (ii.remainder( five ).equals( zero ) ) continue; if (miller( ii, r )) return (ii ); } /* while */ }

53 public static void main2(string [] args){ } init(); Random r = new Random(22345); BigInteger a = new BigInteger( 300, r ); BigInteger b = new BigInteger( 300, r ); a = find_a_prime_number( a, r ); b = find_a_prime_number( b, r ); System.out.println( "a = " + a ); System.out.println( "b = " + b ); BigInteger n = a.multiply( b ); BigInteger n_prime = (a.subtract(one)).multiply( b.subtract(one) ); System.out.println( "n = " + n ); System.out.println( "n' = " + n_prime ); BigInteger d = find_a_prime_number(new BigInteger( 500, r ), r); BigInteger e = d.modinverse( n_prime ); System.out.println( "d = "+ d ); System.out.println( "e = "+ e ); BigInteger c = new BigInteger( " " ); BigInteger encoded = expmod( c, d, n ); BigInteger decoded = expmod( encoded, e, n); System.out.println( "c = " + c ); System.out.println( "encoded =" + encoded); System.out.println( "decoded =" + decoded);

54 a = b = n = n' = d = e = c = encoded = decoded =

/* do-while */ #include <stdio.h> #include <math.h> int main(void) double val1, val2, arith_mean, geo_mean; printf( \n ); do printf( ); scanf( %lf, &v

$/* do-while */ #include <stdio.h> #include <math.h> int main(void) double val1, val2, arith_mean, geo_mean; printf( \n ); do printf( ); scanf( %lf, &v$ 1 http://www7.bpe.es.osaka-u.ac.jp/~kota/classes/jse.html kota@fbs.osaka-u.ac.jp /* do-while */ #include #include int main(void) double val1, val2, arith_mean, geo_mean; printf( \n );