Chapter 9 암호 수학 III 소수와 연관된 합동방정식 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Chapter 9 Objectives  소수와 암호론에서 소수의 응용에 대한 소개  소수 검증 알고리즘과 그 효율성  소인수 분해 알고리즘과 암호론에서의 응용  중국 나머지 정리와 그 응용  2차 합동에 대한 소개  모듈로 지수와 로그에 대한 소개

Topics discussed in this section: 9-1 PRIMES 비대칭 키 암호에서는 소수가 상당히 많이 사용된다. 수학의 정수론에서는 소수에 대한 주제가 상당부분을 차지한다. 이 절에서는 제 10장의 내용을 공부하기 위해 필요한 몇 가지 중요한 개념이나 사실들에 대해 공부하기로 하자. Topics discussed in this section: 9.1.1 정의(Definition) 9.1.2 소수집합의 크기 (Cardinality of Primes) 9.1.3 소수 판정 (Checking for Primeness) 9.1.4 오일러의 -함수 (Euler’s Phi-Function) 9.1.5 페르마의 리틀 정리 (Fermat’s Little Theorem) 9.1.6 오일러 정리 (Euler’s Theorem) 9.1.7 소수 생성 (Generating Primes)

9.1.1 Definition Figure 9.1 양정수의 3 부류 Note 소수는 오직 1이나 자신으로만 나누어떨어진다.

9.1.1 Continued Example 9.1 가장 작은 소수는 무엇인가? Solution 가장 작은 소수는 2이다. 왜냐하면 2는 1과 2로만 나누어떨어지기 때문이다. Example 9.2 10보다 작은 소수를 모두 찾아라. Solution 10보다 작은 소수는 2, 3, 5와 7로서 4 개가 있다. 10보다 작은 수 중에서 소수의 비중이 40%라는 사실에 주의 할 필요가 있다. 궁극적으로 수가 커지면 그 수보다 작은 소수의 개수가 차지하는 비중은 점점 작아진다.

9.1.2 소수집합의 크기 (Cardinality of Primes) 무한히 많은 소수 (Infinite Number of Primes) Note 소수의 개수는 무한개이다. 소수의 개수 (Number of Primes)

9.1.2 Continued Example 9.3 당연한 예로서 소수 전체집합이 {2, 3, 5, 7, 11, 13, 17} 이라고 해보자. 그러면 여기서 P = 510510 이고 P + 1 = 510511이 된다. 그러나 510511 = 19 × 97 × 277이다. 이 곱에 나타난 소인수 3개는 모두 앞의 집합에 들어있지 않은 소수이다. 그래서 17보다 큰 소수가 3개가 있다는 것이 증명되었다. Example 9.4 1,000,000보다 작은 소수의 개수를 구하라. Solution 위의 식을 이용하면 이 범위에 들어오는 소수의 개수는 대략 72,383에서 78,543개 사이의 수이다.

9.1.3 소수 판정 (Checking for Primeness) 주어진 수 에 대해서 그 수가 소수인지 아닌지를 어떻게 판단하는가? 답을 먼저 말해보면 이 수가 보다 작은 모든 소수로 나누어지는지 아닌지를 살펴보면 알 수 있다는 것이다. 이 방법은 그렇게 효율적이지 않다는 것을 안다. 하지만 이렇게 해보는 것은 좋은 아이디어이다.

9.1.3 Continued Example 9.5 수 은 소수인가? Solution 이므로 9 보다 작은 소수는 2, 3, 5, 7 이다. 97이 이 4 개의 소수로 나누어지는지를 살펴보면 어느 소수도 97을 나누지 못한다. Example 9.6 수 은 소수인가? Solution 이므로 보다 작은 소수는 2, 3, 5, 7, 11, 13, 17 이다. 그리고 2, 3, 5 는 301을 나누지 못한다. 하지만 7은 301을 나눈다. 그러므로 301은 소수가 아니다.

9.1.3 Continued 에라토스테네스의 체 (Sieve of Eratosthenes)

9.1.4 오일러의 f –함수(Euler’s Phi-Function) 오일러의 f -함수는 f (n) 으로 나타내며 종종 오일러의 토션 함수(Euler's totient function)이라고도 하는데 암호학에 있어서 매우 중요한 역할을 한다.

9.1.4 Continued We can combine the above four rules to find the value of f(n). For example, if n can be factored as n = p1e1 × p2e2 × … × pkek then we combine the third and the fourth rule to find Note The difficulty of finding f(n) depends on the difficulty of finding the factorization of n.

9.1.4 Continued Example 9.7 f(13) 을 구하라 Solution 10 = 2 × 5이고 위의 3 번째 성질을 이용하면 : f(10) = f(2) × f(5) = 1 × 4 = 4 이다.

9.1.4 Continued Example 9.9 f(240) 을 구하라. Solution 240 = 24 × 31 × 51 이다. 그러므로 f(240) = (24 −23) × (31 − 30) × (51 − 50) = 64 Example 9.10 f(49) = f(7) × f(7) = 6 × 6 = 36 이라고 말할 수 있나? Solution 답은 아니다. 3 번째 성질에 의하면 곱해지는 수 m 과 n 은 서로 소인 수여야 한다. 여기서 49 = 72 이므로 우리는 4 번째 성질을 이용하여 : f(49) = 72 − 71 = 42 를 구할 수 있다.

흥미로운 사실 한 가지: n > 2이기만 하면 f(n)값은 항상 짝수이다. 9.1.4 Continued Example 9.11 Z14* 에 속하는 원소의 개수는 몇 개인가? Solution 답은 f(14) = f(7) × f(2) = 6 × 1 = 6 이다. 실제 이 집합의 원소는 1, 3, 5, 9, 11, 와13 이다. Note 흥미로운 사실 한 가지: n > 2이기만 하면 f(n)값은 항상 짝수이다.

ap − 1 ≡ 1 mod p ap ≡ a mod p 9.1.5 페르마의 리틀 정리 Fermat’s Little Theorem 첫 번째 버전 ap − 1 ≡ 1 mod p 두 번째 버전 ap ≡ a mod p

9.1.5 Continued Example 9.12 610 mod 11 을 계산하라. Solution 610 mod 11 = 1 이다. 이것은 페르마의 리틀 정리에서 p = 11인 경우이다. Example 9.13 312 mod 11 을 계산하라. Solution 여기서 주의해서 볼 것은 지수는 12이고 모듈로 값은 11이다. 이 문제는 페르마의 리틀 정리를 이용해서 쉽게 풀 수 있다.

a−1 mod p = a p − 2 mod p 9.1.5 Continued 곱에 관한 역원 (Multiplicative Inverses ) a−1 mod p = a p − 2 mod p Example 9.14 모듈로 값이 소수인 경우에 곱에 관한 역원을 계산할 때에는 확장된 유클리드 알고리즘을 사용하지 않고도 구할 수 있다.

오일러 정리 두 번째 버전은 제 10장에서 다루게 될 RSA에서 사용할 것이다. 9.1.6 오일러 정리 Euler’s Theorem 첫 번째 버전 af(n) ≡ 1 (mod n) 두 번째 버전 a k × f(n) + 1 ≡ a (mod n) Note 오일러 정리 두 번째 버전은 제 10장에서 다루게 될 RSA에서 사용할 것이다.

9.1.5 Continued Example 9.15 624 mod 35 를 구하라. Solution 624 mod 35 = 6f(35) mod 35 = 1 이다. Example 9.16 2062 mod 77 을 구하라. Solution 두 번째 버전에서 k = 1 이라고 한다면 2062 mod 77 = (20 mod 77) (20f(77) + 1 mod 77) mod 77 = (20)(20) mod 77 = 15.

a−1 mod n = af(n)−1 mod n 9.1.6 Continued 곱에 대한 역원 (Multiplicative Inverses ) 오일러 정리를 이용하면 소수 모듈로를 갖는 경우에 곱에 대한 역원을 구할 수 있다. a−1 mod n = af(n)−1 mod n

9.1.5 Continued Example 9.17 합성수를 모듈로로 갖는 경우에 확장된 유클리드 알고리즘을 사용하지 않고도 곱에 대한 역원을 구할 수 있다.

Mp = 2p − 1 형태를 갖는 수를 Mersenne 수라고 하며, 이것은 소수일 수도 있고 아닐 수도 있다. 9.1.7 소수 생성(Generating Primes) Mersenne 소수 Mersenne Primes Note Mp = 2p − 1 형태를 갖는 수를 Mersenne 수라고 하며, 이것은 소수일 수도 있고 아닐 수도 있다.

9.1.7 Continued 페르마 소수 Fermat Primes F0 = 3 F1 = 5 F2 = 17 F3 = 257 F4 = 65537 F5 = 4294967297 = 641 × 6700417 Not a prime

Topics discussed in this section: 9-2 소수 판정 (PRIMALITY TESTING) 주어진 매우 큰 정수가 주어졌을 때 이 수가 소수인지 합성수인지 정확하고 효율적으로 판단할 수 있는 알고리즘을 찾아낸다는 것은 정수론과 암호론에 있어서 매우 도전적인 문제로 여겨져 왔다. 하지만 최근에 발견한 한 가지 방법은 매우 훌륭하다. 이것에 대해서 이 절에서 말해보기로 하자. Topics discussed in this section: 9.2.1 결정적 알고리즘 (Deterministic Algorithms) 9.2.2 확률적 알고리즘(Probabilistic Algorithms) 9.2.3 추천하는 소수 검증 (Recommended Primality Test)

나눔 검증법의 비트-연산 복잡도는 지수적이다. 9.2.1 Deterministic Algorithms 나눔 알고리즘(Divisibility Algorithm) Note 나눔 검증법의 비트-연산 복잡도는 지수적이다.

9.2.1 Continued Example 9.18 n 이 200비트를 갖는 수라고 가정해보자. 그러면 나눔 알고리즘을 수행하는데 필요한 비트 연산의 회수는 얼마나 되는가? Solution 이 알고리즘의 비트-연산 복잡도는 2nb/2 이다. 이 말이 의미하는 것은 이 알고리즘을 수행하기 위해서 2100 번의 비트연산을 수행해야 한다는 것이다. 초당 230 번의 비트연산을 수행할 수 있는 능력을 가진 컴퓨터를 사용하게 되면 이 알고리즘을 이용해서 소수 검증을 수행하는 데 270 초가 걸린다는 뜻이다. 하지만 이 시간은 거의 영원한 시간이다.

9.2.1 Continued AKS 알고리즘 AKS Algorithm Example 9.19 n 의 비트 수가 200이라고 가정하자. AKS 알고리즘을 수행한다고 한다면 비트연산 회수는 얼마나 되는가? Solution 이 알고리즘의 비트-연산 복잡도는 이다. 이것이 의미하는 것은 알고리즘은 오직 (log2200)12 = 39,547,615,483 번의 연산을 수행하면 이 수가 소수인지 아닌지를 알아낼 수 있다는 뜻이다. 초당 10억 번의 비트연산을 수행 할 수 있는 컴퓨터를 사용하면 이 알고리즘을 이용해서 40초 만에 소수 검증을 끝낼 수 있는 것이다.

Probabilistic Algorithms 9.2.2 확률적 알고리즘 Probabilistic Algorithms 페르마 검증 Fermat Test If n is a prime, an−1 ≡ 1 mod n If n is a composite, it is possible that an−1 ≡ 1 mod n Example 9.20 수 561을 페르마 검증하면 어떻게 되는가? Solution 2 를 밑수로 사용해보자. 그러면 을 만족하므로 수 은 페르마 검증을 통과했다. 그러나 사실 이 수는 소수가 아니다. 왜냐하면 561 = 33 × 17 이다.

9.2.2 Continued 제곱근 검증 (Square Root Test) Example 9.21 n 이 7(소수)이라면, 1 mod n 의 제곱근은 무엇인가? Solution 유일한 제곱근은 1 과 −1 뿐이다. 왜 그런지 살펴보자.

9.2.2 Continued Example 9.21 n 이 7(소수)이라면, 1 mod n 의 제곱근은 무엇인가? Solution 유일한 제곱근은 1 과 −1 뿐이다. 왜 그런지 살펴보자. 여기서 4 = –3 mod 7, 5 = –2 mod 7, 6 = –1 mod 7 이므로 4, 5, 6에 대해서는 점검할 필요가 없다는 점에 유의하기 바란다.

9.2.2 Continued Example 9.22 만약 n is 8 (합성수)이라면, 1 mod n 의 제곱근은 무엇인가? Solution 이것은 근을 4개 갖는다. 그 근은 1, 3, 5, 7(이것은 -1)이다. 이유는 다음과 같다.

9.2.2 Continued Example 9.23 만약 n is 17 (소수)이라면 1 mod n 의 제곱근은 무엇인가? Solution There are only two solutions: 1 and −1

9.2.2 Continued Example 9.24 만약 n is 22 (합성수)이라면 1 mod n 의 제곱근은 무엇인가? Solution 비록 가 합성수이기는 하지만 놀랍게도 여기에는 오직 2 개의 근만 존재한다. 그 2개의 근은 +1과 −1이다.

Miller-Rabin 검증에서 필요한 단계는 0단계부터 k − 1.단계이다 9.2.2 Continued Miller-Rabin Test Figure 9.2 페르마 소수 판정에 대한 아이디어 Note Miller-Rabin 검증에서 필요한 단계는 0단계부터 k − 1.단계이다

9.2.2 Continued

9.2.2 Continued Example 9.25 수 561은 Miller-Rabin 검증을 통과하는가? Solution 밑수 a 를 2로 사용하면, 561 − 1 = 35 × 24 로 표현된다. 그래서 ns m = 35, k = 4, 이고 a = 2이다.

9.2.2 Continued Example 9.26 27 은 소수가 아닌 것을 알고 있다. Miller-Rabin 검증을 하라. Solution 밑수를 2로 사용하자. 27 − 1 = 13 × 21 이므로 m = 13, k = 1, a = 2 이다. 이 경우에 k − 1 = 0 이므로 초기화 단계만 수행하면 된다. T = 213 mod 27 = 11 mod 27 이다. 그러나 이 알고리즘이 루프를 돌지 않기 때문에 리턴 값은 “합성수(a composite)" 이다.

9.2.2 Continued Example 9.27 61 은 소수라는 것을 알고 있다. Miller-Rabin 검증을 통과하는지 알아보아라. Solution 밑수로 2를 사용하자.

Recommended Primality Test 9.2.3 추천하는 소수 검증 Recommended Primality Test 현재 가장 많이 사용되는 소수 검증방법은 나눔 검증과 Miller-Rabin 검증을 조합한 것이다.

9.2.3 Continued Example 9.28 4033은 (37 × 109)이므로 합성수이다. 이 수는 위에 언급한 추천하는 소수 검증을 통과하는가? Solution a. 우선 나눔 검증을 실시한다. 2, 3, 5, 7, 11, 17, 23은 4033 의 약수가 아니다. 2. a. 밑수를 2로 사용하여 Miller-Rabin 검증을 실시한다. 4033 − 1 = 63 ×26 이므로 m 은 63 이고 k 는 6이다.

9.2.3 Continued Example 9.28 Continued 3. 그러나 만족스럽지 못하다. 밑수로 3을 사용해보자.

Topics discussed in this section: 9-3 소인수 분해 (FACTORIZATION) 소인수분해에 대해서는 과거에서부터 아주 많이 연구되어졌다. 이러한 소인수 분해에 대한 연구는 앞으로도 계속해서 이루어질 것이다. 소인수 분해는 여러 가지 공개 키 암호시스템의 보안성부문에서 매우 중요한 역할을 하고 있다(제 10장 참조). Topics discussed in this section: 9.3.1 산술 기본 정리 (Fundamental Theorem of Arithmetic) 9.3.2 소인수분해 방법 (Factorization Methods) 9.3.3 페르마 방법( Fermat Method) 9.3.4 Pollard p – 1 방법(Pollard p – 1 Method) 9.3.5 Pollard rho 방법(Pollard rho Method) 9.3.6 더 효율적인 방법(More Efficient Methods)

9.3.1 Fundamental Theorem of Arithmetic 최대공약수 Greatest Common Divisor 최소공배수 Least Common Multiplier

9.3.2 Factorization Methods 전수 나눔 소인수분해 방법 Trial Division Method

9.3.2 Continued Example 9.29 1233 을 소인수분해하기 위해서 전수 나눔 알고리즘을 사용하라. Solution 알고리즘에 따라 프로그램을 구동하면 다음과 같은 결과를 얻는다. Example 9.30 1523357784 을 소인수분해하기 위해서 전수 나눔 알고리즘을 사용하라. Solution 알고리즘에 따라 프로그램을 구동하면 다음과 같은 결과를 얻는다.

9.3.3 Fermat Method

9.3.4 Pollard p – 1 Method

9.3.4 Continued Example 9.31 57247159 의 소인수를 구하기 위해서 Pollard p − 1 소인수분해 방법을 사용하라. 여기서 B = 8 을 사용하라. Solution 알고리즘에 따라 프로그램을 구동하면 p = 421 을 찾아낼 수 있다. 사실 57247159 = 421 × 135979 이다. 421 이 소수이고 p − 1=421-1 은 8 보다 큰 인수를 갖지 않는다는 사실에 유의 하기 바란다. 사실 421 − 1 = 22 × 3 × 5 × 7

9.3.5 Pollard rho Method Figure 9.3 Pollard rho 연속 수

9.3.5 Continued

9.3.5 Continued Example 9.32 어떤 컴퓨터가 초당 230 (거의 10억번)번 정도의 비트연산을 할 수 있다고 해보자. 다음과 같은 크기의 정수를 소인수분해 할 때 걸리는 시간이 대략 어느 정도 되는가? a. 60자리 십진수 b. 100자리 십진수

9.3.5 Continued Solution 60자리를 갖는 십진수를 이진수로 바꿔보면 비트수가 약 200자리 정도가 된다. 따라서 복잡도는 대략 250 이다. 초당 230여산능력을 갖는 컴퓨터를 이용하면 이 알고리즘은 220 a. 초인 약 12일 정도면 끝낼 수 있다. b. 100자리를 갖는 십진수를 이진수로 바꿔보면 비트수가 약 300자리 정도가 된다. 따라서 복잡도는  대략 275이다. 초당 230 여산능력을 갖는 컴퓨터를 이용하면 이 알고리즘은 245초가 걸리는데 이것을 년 수로 환산하면 상당히 오랜 기간이다.

9.3.5 Continued Example 9.33 434617 을 소인수분해 하기 위해 프로그램을 만들었다. 그 결과로 709 (434617 = 709 × 613) 을 얻었다.

O(eC), where C ≈ (ln n lnln n)1/2 9.3.6 More Efficient Methods 2차 체 Quadratic Sieve 이 방법은 체로 걸러내는 방법을 이용하여 x2 mod n 값을 구해낸다. O(eC), where C ≈ (ln n lnln n)1/2 정수체 체 이 방법에서는 수학적인 대수구조인 환(ring) 구조 안에서 체로 걸러내어 x2 ≡ y2 mod n 을 구해낸다 . O(eC) where C ≈ 2 (ln n)1/3 (lnln n)2/3

9.3.6 Continued Example 9.34 어떤 컴퓨터가 초당 230 (거의 10억번)번 정도의 비트연산을 할 수 있다고 해보자. 그러면 다음과 같은 방법을 사용했을 때 100자리 십진 정수를 소인수 분해 하는데 소요되는 시간이 대략 얼마나 걸리는가? a. 2차 체 방법 b. 정수체 체 방법

9.3.6 Continued Solution 자리수가 100인 십진 정수는 대략 이진수로 바꿔보면 비트수가 약 300자리 정도이다. 즉, (n = 2300). ln(2300) = 207 이고 lnln (2300) = 5. a. (207)1/2 × (5)1/2 = 14 × 2.23 ≈ 32 e32 (e32) / (230) ≈ 20 hours. b. (207)1/3× (5)2/2 = 6 × 3 ≈ 18. e18 (e18) / (230) ≈ 6 seconds.

CHINESE REMAINDER THEOREM 9-4 중국인 나머지 정리 CHINESE REMAINDER THEOREM 중국인 나머지 정리(Chinese remainder theorem: CRT)를 이용하면 한 개의 변수와 서로 소인 다른 모듈로를 갖는 합동 방정식의 해를 구할 수 있다. 이 방정식은 아래와 같이 표현된다.

9-4 Continued Example 9.35 다음은 서로 다른 모듈로 값을 가진 연립방정식이다. 이 연립 방정식의 해는 다음 절에서 보이기로 한다. 여기서는 해가 x = 23 이라는 것을 알았다고 하자. 23 ≡ 2 (mod 3), 23 ≡ 3 (mod 5), and 23 ≡ 2 (mod 7) 을 만족하기 때문에 이 해는 세 개의 방정식의 해가 된다.

9-4 Continued 해 구하기(Solution To Chinese Remainder Theorem) 1. 1. 공통 모듈로로 사용할M = m1 × m2 × … × mk. 2. Find M1 = M/m1, M2 = M/m2, …, Mk = M/mk. 3. Find the multiplicative inverse of M1, M2, …, Mk using the corresponding moduli (m1, m2, …, mk). Call the inverses M1−1, M2−1, …, Mk −1. 4. The solution to the simultaneous equations is

9-4 Continued Example 9.36 Find the solution to the simultaneous equations: Solution We follow the four steps. 1. M = 3 × 5 × 7 = 105 2. M1 = 105 / 3 = 35, M2 = 105 / 5 = 21, M3 = 105 / 7 = 15 3. The inverses are M1−1 = 2, M2−1 = 1, M3 −1 = 1 4. x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = 23 mod 105

9-4 Continued Example 9.37 Find an integer that has a remainder of 3 when divided by 7 and 13, but is divisible by 12. Solution This is a CRT problem. We can form three equations and solve them to find the value of x. If we follow the four steps, we find x = 276. We can check that 276 = 3 mod 7, 276 = 3 mod 13 and 276 is divisible by 12 (the quotient is 23 and the remainder is zero).

9-4 Continued Example 9.38 Assume we need to calculate z = x + y where x = 123 and y = 334, but our system accepts only numbers less than 100. These numbers can be represented as follows: Adding each congruence in x with the corresponding congruence in y gives Now three equations can be solved using the Chinese remainder theorem to find z. One of the acceptable answers is z = 457.

Topics discussed in this section: 9-5 QUADRATIC CONGRUENCE In cryptography, we also need to discuss quadratic congruence¾that is, equations of the form a2x2 + a1x + a0 ≡ 0 (mod n). We limit our discussion to quadratic equations in which a2 = 1 and a1 = 0, that is equations of the form Cable companies are now competing with telephone companies for the residential customer who wants high-speed data transfer. In this section, we briefly discuss this technology. x2 ≡ a (mod n). Topics discussed in this section: 9.5.1 Quadratic Congruence Modulo a Prime 9.5.2 Quadratic Congruence Modulo a Composite

9.5.1 Quadratic Congruence Modulo a Prime We first consider the case in which the modulus is a prime. Example 9.39 The equation x2 ≡ 3 (mod 11) has two solutions, x ≡ 5 (mod 11) and x ≡ −5 (mod 11). But note that −5 ≡ 6 (mod 11), so the solutions are actually 5 and 6. Also note that these two solutions are incongruent. Example 9.40 The equation x2 ≡ 2 (mod 11) has no solution. No integer x can be found such that its square is 2 mod 11.

9.5.1 Continued Quadratic Residues and Nonresidue In the equation x2 ≡ a (mod p), a is called a quadratic residue (QR) if the equation has two solutions; a is called quadratic nonresidue (QNR) if the equation has no solutions.

9.5.1 Continued Example 9.41 There are 10 elements in Z11*. Exactly five of them are quadratic residues and five of them are nonresidues. In other words, Z11* is divided into two separate sets, QR and QNR, as shown in Figure 9.4. Figure 9.4 Division of Z11* elements into QRs and QNRs

9.5.1 Continued Euler’s Criterion a. If a(p−1)/2 ≡ 1 (mod p), a is a quadratic residue modulo p. b. If a(p−1)/2 ≡ −1 (mod p), a is a quadratic nonresidue modulo p. Example 9.42 To find out if 14 or 16 is a QR in Z23*, we calculate: 14 (23−1)/2 mod 23 → 22 mod 23 → −1 mod 23 nonresidue 16 (23−1)/2 mod 23 → 1611 mod 23→ 1 mod 23 residue

9.5.1 Continued Solving Quadratic Equation Modulo a Prime Special Case: p = 4k + 3

9.5.1 Continued Example 9.43 Solve the following quadratic equations: Solutions x ≡ ± 16 (mod 23) √3 ≡ ± 16 (mod 23). b. There is no solution for √2 in Z11. c. x ≡ ± 11 (mod 19). √7 ≡ ± 11 (mod 19).

9.5.2 Quadratic Congruence Modulo a Composite Figure 9.5 Decomposition of congruence modulo a composite

9.5.2 Continued Example 9.44 Assume that x2 ≡ 36 (mod 77). We know that 77 = 7 × 11. We can write The answers are x ≡ +1 (mod 7), x ≡ − 1 (mod 7), x ≡ + 5 (mod 11), and x ≡ − 5 (mod 11). Now we can make four sets of equations out of these: The answers are x = ± 6 and ± 27.

9.5.2 Continued Complexity How hard is it to solve a quadratic congruence modulo a composite? The main task is the factorization of the modulus. In other words, the complexity of solving a quadratic congruence modulo a composite is the same as factorizing a composite integer. As we have seen, if n is very large, factorization is infeasible. Note Solving a quadratic congruence modulo a composite is as hard as factorization of the modulus.

Topics discussed in this section: 9-6 EXPONENTIATION AND LOGARITHM Topics discussed in this section: 9.6.1 Exponentiation 9.6.2 Logarithm

9.6.1 Exponentiation Fast Exponentiation Figure 9.6 The idea behind the square-and-multiply method

9.6.1 Continued

9.6.1 Continued Example 9.45 Figure 9.7 shows the process for calculating y = ax using the Algorithm 9.7 (for simplicity, the modulus is not shown). In this case, x = 22 = (10110)2 in binary. The exponent has five bits. Figure 9.7 Demonstration of calculation of a22 using square-and-multiply method

9.6.1 Continued Note The bit-operation complexity of the fast exponential algorithm is polynomial.

9.6.2 Logarithm In cryptography, we also need to discuss modular logarithm. Exhaustive Search

9.6.2 Continued Order of the Group. Example 9.46 What is the order of group G = <Z21∗, ×>? |G| = f(21) = f(3) × f(7) = 2 × 6 =12. There are 12 elements in this group: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. All are relatively prime with 21.

9.6.2 Continued a. 11 ≡ 1 mod (10) → ord(1) = 1. Order of an Element Example 9.47 Find the order of all elements in G = <Z10∗, ×>. Solution This group has only f(10) = 4 elements: 1, 3, 7, 9. We can find the order of each element by trial and error. a. 11 ≡ 1 mod (10) → ord(1) = 1. b. 34 ≡ 1 mod (10) → ord(3) = 4. c. 74 ≡ 1 mod (10) → ord(7) = 4. d. 92 ≡ 1 mod (10) → ord(9) = 2.

9.6.2 Continued Euler’s Theorem Example 9.48

9.6.2 Continued Primitive Roots In the group G = <Zn∗, ×>, when the order of an element is the same as f(n), that element is called the primitive root of the group. Example 9.49 Table 9.4 shows that there are no primitive roots in G = <Z8∗, ×> because no element has the order equal to f(8) = 4. The order of elements are all smaller than 4.

9.6.2 Continued Example 9.50 Table 9.5 shows the result of ai ≡ x (mod 7) for the group G = <Z7∗, ×>. In this group, f(7) = 6.

9.6.2 Continued Note The group G = <Zn*, ×> has primitive roots only if n is 2, 4, pt, or 2pt. Example 9.51 For which value of n, does the group G = <Zn∗, ×> have primitive roots: 17, 20, 38, and 50? Solution G = <Z17∗, ×> has primitive roots, 17 is a prime. b. G = <Z20∗, ×> has no primitive roots. c. G = <Z38∗, ×> has primitive roots, 38 = 2 × 19 prime. d. G = <Z50∗, ×> has primitive roots, 50 = 2 × 52 and 5 is a prime.

9.6.2 Continued Note If the group G = <Zn*, ×> has any primitive root, the number of primitive roots is f(f(n)).

9.6.2 Continued Cyclic Group If g is a primitive root in the group, we can generate the set Zn* as Zn∗ = {g1, g2, g3, …, gf(n)} Example 9.52 The group G = <Z10*, ×> has two primitive roots because f(10) = 4 and f(f(10)) = 2. It can be found that the primitive roots are 3 and 7. The following shows how we can create the whole set Z10* using each primitive root.

9.6.2 Continued The idea of Discrete Logarithm Properties of G = <Zp*, ×> : 1. Its elements include all integers from 1 to p − 1. 2. It always has primitive roots. 3. It is cyclic. The elements can be created using gx where x is an integer from 1 to f(n) = p − 1. 4. The primitive roots can be thought as the base of logarithm.

9.6.2 Continued Solution to Modular Logarithm Using Discrete Logs Tabulation of Discrete Logarithms

9.6.2 Continued Solution Example 9.53 Find x in each of the following cases: a. 4 ≡ 3x (mod 7). b. 6 ≡ 5x (mod 7). Solution We can easily use the tabulation of the discrete logarithm in Table 9.6. a. 4 ≡ 3x mod 7 → x = L34 mod 7 = 4 mod 7 b. 6 ≡ 5x mod 7 → x = L56 mod 7 = 3 mod 7

9.6.2 Continued Using Properties of Discrete Logarithms Using Algorithms Based on Discrete Note The discrete logarithm problem has the same complexity as the factorization problem.