Ch4.4~4.6 지장현 2017.09.24 1

목차 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 𝑍 𝑝 ∗

1. Prime Number Generation Prime search for probable primes

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

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

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

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

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

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

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

1. Prime Number Generation NIST method for generating DSA primes

1. Prime Number Generation NIST method for generating DSA primes

1. Prime Number Generation Constructive techniques for provable primes

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

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

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

1. Prime Number Generation Constructive techniques for provable primes

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

2. Irreducible polynomials over 𝒁 𝒑

2. Irreducible polynomials over 𝒁 𝒑

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

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

2. Irreducible polynomials over 𝒁 𝒑 Irreducible trinomials

2. Irreducible polynomials over 𝒁 𝒑 Irreducible trinomials

2. Irreducible polynomials over 𝒁 𝒑 Primitive polynomials

2. Irreducible polynomials over 𝒁 𝒑 Primitive polynomials

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

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

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

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

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

감사합니다 Q & A 32 32