암호수학이론 - 소수, 소인수, 나머지, 지수, 로그

소개글

암호수학이론 - 소수, 소인수, 나머지, 지수, 로그에 대한 보고서 자료입니다.

목차

9.1 소수(Prime).
　9.1.1 소수(Prime)와 서로 소(Coprimes).
　9.1.2 소수의 개수.
　9.1.3 소수의 판정.
　9.1.4 오일러의 Ǿ함수(Euler’s phi-function or totient-function).
　9.1.5 페르마의 소 정리.(Fermat’s little theorem)
　9.1.6 오일러의 정리.(Euler’s theorem)
　9.1.7 소수의 생성(Mersenne & Fermat Number).

9.2 소수판정.
　9.2.1 Deterministic Algorithm.
　　- 나눔 알고리즘.
　　- A K S 알고리즘.
　9.2.2 Probalbilistic Algorithm.
　　- 페르마 검증.
　　- 제곱근 검증.
　　- Miller-Rabin 검증.
　9.2.3 추천하는 소수 검증.

9.3 소인수분해.
　9.3.1 Fundamental Theorem of Arithmetic
　9.3.2 Factorization Methods
　9.3.3 Fermat Method
　9.3.4 Pollard p – 1 Method
　9.3.5 Pollard rho Method
　9.3.6 More Efficient Methods

9.4 중국인의 나머지 정리(Chinese remainder algorithm)

9.5 2차 합동(QUADRATIC CONGRUENCE)
　9.5.1 소수가 모듈로인 2차 합동 (Quadratic Congruence Modulo a Prime)
　9.5.2 합성수가 모듈로인 2차 합동 (Quadratic Congruence Modulo a Composite)

9.6 지수와 로그 (EXPONENTIATION AND LOGARITHM)
　9.6.1 지수(Exponentiation)
　9.6.2 로그(Logarithm)

본문내용

암호수학.




┃ 9.1.1 소수(Prime)와 서로 소(Coprimes).
┗━━━━━━━━━━─────────…

　≪ 표 - 그림 파일 ≫

▣ 소수(Prime).
　오직 1이나 자신으로만 나누어 떨어지는 수. <단 1은 제외>
▣ 서로 소(Coprimes).
　임의의 양의 정수 a, b가 GCD(a, b)=1을 만족할 때, a와 b는 서로 소.

￡무한히 많은 소수, ￡수가 커질수록 소수의 분포는 줄어듬.(1-1000:303, 2000-3000:127).




┃ 9.1.2 소수의 개수.
┗━━━━━━━━━━─────────…

π(n) : n보다 작거나 같은 소수의 개수
　≪ 글 - 그림 파일 ≫
　• 상한 : 가우스(Gauss) 발견.
　• 하한 : 라그랑지 발견.

【Example 9.4】
1,000,000보다 작은 소수의 개수.
　• 공식 이용 : 72,383 < π(n) < 78,543
　• 실제 개수 : 78,498개.

ln(n) : loge(n), 자연로그(natural logarithm), 오일러의 수 e를 밑으로 하는 로그. e = 2.7182818284….




┃ 9.1.3 소수의 판정. (1/2)
┗━━━━━━━━━━─────────…

▣ 소수 판정 I.

　임의의 양의 정수 n에 대하여..
　n이 √n보다 작은 소수로 나누어지면 합성수. 아니면 소수.
　　　　　　　　　　　　　　　　<단 효율적인 방법은 아님.>

【Example 9.5-6】
97과 301의 소수 판정.
　• 9< √97 <10 : 9보다 작은 소수 {2, 3, 5, 7}중 어떤 소수로도 97을 나누지 못함.
　• 17<√301<18 : 17보다 작은 소수{2, 3, 5, 7, 11, 13, 17}중 7로 301을 나눔.
따라서 97은 소수, 301은 합성수.




┃ 9.1.3 소수의 판정. (2/2)
┗━━━━━━━━━━─────────…

▣ 소수 판정 II.
에라토스테네스(Sieve of Eratosthenes)의 체

　• 2로 나누어 떨어지는 수 삭제. (2 제외)
　• 3으로 나누어 떨어지는 수 삭제. (3 제외)
　• 5로 나누어 떨어지는 수 삭제. (5 제외)
　• 7로 나누어 떨어지는 수 삭제. (7 제외)
　• 남은수는 소수

　≪ 표 ≫




┃ 9.1.4 오일러 함수(Euler’s phi-function).
┗━━━━━━━━━━─────────…

▣ 오일러의 Ǿ함수.

　• Ǿ(n) : n보다 작고, n과 서로 소인 정수의 개수.
　　a. Ǿ(1) = 0. b. Ǿ(p) = p-1 <단 p는 소수.>
　　c. Ǿ(m•n) = Ǿ(m)•Ǿ(n) <단 m과 n이 서로 소.>
　　d. Ǿ(pe) = pe - pe-1,<단 p는 소수.>
　　e. Ǿ(p1e1•p2e2• … •pkek) = (p1e1-p1e1-1)•(p2e2-p2e2-1)• … •(pkek-pkek-1)

【Example】
　9.9 Ǿ(240) = ?
　　풀이> Ǿ(240 = 24•31•51) = Ǿ(24)•Ǿ(31)•Ǿ(51) = (24-24-1)•(31-31-1)•(51-51-1) = 8•2•4 = 64
　9.11 Z14*의 개수.
　　풀이> Ǿ(14) = Ǿ(7)•Ǿ(2) = (7-1)•(2-1) = 6 // Z14* = {1, 3, 5, 9, 11, 13}

키워드

암호수학,   소수,   소인수,   나머지,   지수,   로그