Two Types of Algorithms for Finding the Cube Root in Finite Fields
| Autor: | Gook Hwa Cho |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Combinatorics
Discrete mathematics Finite field 010201 computation theory & mathematics Cipolla's algorithm 0202 electrical engineering electronic engineering information engineering 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Cube root Klee–Minty cube Mathematics |
| Zdroj: | The Journal of Korean Institute of Communications and Information Sciences. 41:499-503 |
| ISSN: | 1226-4717 |
| Popis: | We study algorithms that can efficiently find cube roots by modifying Cipolla-Lehmer algorithm. In this paper, we present two type algorithms for finding cube roots in finite field, which improves Cipolla-Lehmer algorithm. If the number of multiplications of two type algorithms has a little bit of a difference, then it is more efficient algorithm which have less storage variables. ※ 본 논문은 2009년 정부(교육부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업임 (과제번호: 2009-0093827) ° First Author : Ewha Womans University, Institute of Mathematical Sciences, ghcho@ewha.ac.kr, 정회원 논문번호:KICS2016-02-035, Received February 25, 2016; Revised April 26, 2016; Accepted April 27, 2016 I. 서 론 유한체 상에서 제곱근을 찾는 문제는 많은 곳에 서 응용이 되고 있다. 예를 들어, 미 NIST(National Institute of Standards and Technology)에서 제안한 규정집 (Federal Information Processing Standard 186-3)의 전자서명 프로토콜에서는1 타원곡선을 이용 하여 전자서명을 구현하는 방법을 설명하였는데 여기 에서 유한체상의 제곱근을 찾는 알고리즘이 필요하 다. 마찬가지로 유한체상에서 세제곱근을 찾는 알고리 즘 역시 높은 차원의 타원곡선의 암호 시스템에서 응 용될 수 있다. 유한체상에서 세제곱근을 찾는 표준적인 두 개의 알고리즘으로는 Tonelli-Shanks 알고리즘, 그리고 Cipolla-Lehmer 알고리즘이 있다. Tonelli-Shanks 알고리즘은 이고 인 의 지수 에 의 존하고 최악의 경우 복잡도는 이지만 Cipolla-Lehmer의 복잡도는 이다. 그러므로 가 상당히 큰 경우에는 Cipolla-Lehmer 알고리즘이 Tonelli-Shanks 알고리즘보다 효율적이다. 일반적인 Cipolla-Lehmer 알고리즘은 기약 다항식 이고 가 삼차 잉여 ( )일 때, 의 세제곱근은 으로 찾을 수 있다. 이 때, 는 의 상의 해이다. 본 논문에서는 일반적인 Cipolla-Lehmer 알고리즘 보다 위 지수 계산의 곱셈량을 줄이기 위해 특수한 The Journal of Korean Institute of Communications and Information Sciences '16-05 Vol.41 No.05 500 입력: 삼차 잉여 ∈ 출력: 상수항이 인 기약 다항식 Step 1. ∈를 임의로 선택 ← ← Step 2. if 가 이거나 이차 비잉여, then Step 1 else (i.e., : 의 해) Step 3. if 가 삼차 비잉여, then 반환 else Step 1 표 2. Dickson의 삼차 다항식 기약성 테스트 알고리즘 Table 2. Dickson’s irreducibility testing of cubic polynomials 형태의 다항식을 선택하여 선형점화식을 이용한 두 가지 알고리즘을 소개하고, 비슷한 곱셈량의 알고리즘 이더라도 저장변수의 개수가 적을수록 더욱 효율적임 을 보이도록 하겠다. 본 논문의 나머지 부분은 다음과 같다 : 2장에서는, Cipolla-Lehmer가 제시한 세제곱근을 찾는 방법에 대 하여 설명한다. 3장에서는 두 가지 방법의 “Double and add”선형 점화식을 이용하여 세제곱근을 찾는 방 법에 대해 설명한다. 4장에서는 복잡도와 실험 결과를 보여준다. 마지막으로 5장에서 결론짓는다. II. Cipolla-Lehmer 알고리즘 만약 ≡ 인 소수 에 대해서 가 삼차 잉 여일 때 의 세제곱근을 찾기 위해 기약 다항식 가 필요하다. 만약 ∈ 가 의 해이라면, 의 세제곱근은 로 찾을 수 있다. 표 1이 세제곱근을 찾는 Cipolla-Lehmer 알 고리즘이다. 이 알고리즘은 의 기약성과 의 지수 계산에서 많은 곱셈량을 필요로 한 다. 그리고 이 곱셈량은 의 계수와 밀접한 관계가 있 다. Nishihara는 삼항 다항식을 이용하여 속도를 향 상시켰고, Dickson은 아래 두 가지 성질을 만족하면 기약 다항식 이 되는 것을 이용하 였다. 두 가지 성질을 다음과 같다. 1. 가 이차 잉여 ( )이다. 입력: 삼차 잉여 ∈ 출력: 의 삼차 해 Step 1. ∈를 임의로 선택 Step 2. ← if : 기약다항식, then Step 1 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|