Ch4.4~4.6 지장현 2017.09.24 1.

Presentation on theme: "Ch4.4~4.6 지장현 2017.09.24 1."— Presentation transcript:

1 Ch4.4~4.6 지장현 1

2 목차 Prime Number Generation Random Search For Probable Strong Primes
전체 목차 목차 Prime Number Generation Random Search For Probable Strong Primes NIST method for generating DSA primes Constructive techniques for provable primes Irreducible polynomials over 𝒁 𝒑 Irreducible polynomials Irreducible trinomials Primitive polynomials Generators and elements of high order Selecting a prime p and generator of 𝑍 𝑝 ∗

3 1. Prime Number Generation
Prime search for probable primes

4 1. Prime Number Generation
Prime search for probable primes Random search for a prime using the Miller-Rabin Test MILLER-RABIN의 결과는 소수일 가능성이 높은 수임

5 1. Prime Number Generation
Prime search for probable primes Random search for a prime using the Miller-Rabin Test 밀러라빈 테스트 전에 랜덤 정수 n은 작은 소수 의 divisor을 가질 확률이 크기 때문에 미리 결정된 B 보다 작은 소수를 이용하여 미리 테스트 함

6 1. Prime Number Generation
Prime search for probable primes Random search for a prime using the Miller-Rabin Test

7 1. Prime Number Generation
Strong Prime Definition Strong Prime 위의 3개의 조건을 만족하는 r,s,t가 존재하면 prime p는 strong prime

8 1. Prime Number Generation
Strong Prime Gordon’s algorithm for generating a strong prime 결과

9 1. Prime Number Generation
Strong Prime Gordon’s algorithm for generating a strong prime

10 1. Prime Number Generation
NIST method for generating DSA primes NIST 디지털 서명 알고리즘(DSA)는 다음 조건을 만족하는 prime p와 q를 필요로함 다음 알고리즘을 이 조건을 만족하는 prime p 와 q를 생성하는 알고리즘 제시 H는 SHA-1 hash function을 사용

11 1. Prime Number Generation
NIST method for generating DSA primes

12 1. Prime Number Generation
NIST method for generating DSA primes

13 1. Prime Number Generation
Constructive techniques for provable primes

14 1. Prime Number Generation
Constructive techniques for provable primes Maurer’s algorithm for generating provable primes

15 1. Prime Number Generation
Constructive techniques for provable primes Maurer’s algorithm for generating provable primes

16 1. Prime Number Generation
Constructive techniques for provable primes Maurer’s algorithm for generating provable primes

17 1. Prime Number Generation
Constructive techniques for provable primes

18 2. Irreducible polynomials over 𝒁 𝒑
이러한 필드 연산은 소프트웨어 하드웨어에서 효율적인 성능을 낼 수 있음

19 2. Irreducible polynomials over 𝒁 𝒑

20 2. Irreducible polynomials over 𝒁 𝒑

21 2. Irreducible polynomials over 𝒁 𝒑
Testing a polynomial for irreducibility

22 2. Irreducible polynomials over 𝒁 𝒑
Generating a random monic irreducible polynomial over 𝒁 𝒑

23 2. Irreducible polynomials over 𝒁 𝒑
Irreducible trinomials

24 2. Irreducible polynomials over 𝒁 𝒑
Irreducible trinomials

25 2. Irreducible polynomials over 𝒁 𝒑
Primitive polynomials

26 2. Irreducible polynomials over 𝒁 𝒑
Primitive polynomials

27 3. Generators and elements of high order
Determining the order of a group element

28 3. Generators and elements of high order
Finding a generator of a cyclic group

29 3. Generators and elements of high order
Selecting an element of maximum order in 𝑍 𝑛 ∗ , where n = pq

30 3. Generators and elements of high order
Selecting a prime p and generator of 𝑍 𝑝 ∗

31 3. Generators and elements of high order
Selecting a prime p and generator of 𝑍 𝑝 ∗

32 감사합니다 Q & A 32 32