On the Cipolla–Lehmer type algorithms in finite fields
| Autor: | Byeong-Hwan Go, Chang Heon Kim, Gook Hwa Cho, Namhun Koo, Soonhak Kwon |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Algebra and Number Theory
Finite field 010201 computation theory & mathematics Applied Mathematics Theory of computation 0202 electrical engineering electronic engineering information engineering 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Algorithm Primitive root modulo n Mathematics |
| Zdroj: | Applicable Algebra in Engineering, Communication and Computing. 30:135-145 |
| ISSN: | 1432-0622 0938-1279 |
| DOI: | 10.1007/s00200-018-0362-2 |
| Popis: | In this paper, we present a refinement of the Cipolla–Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue $$c\in \mathbb {F}_q$$ where r is an odd prime, the algorithm of H. C. Williams determines a solution of $$X^r=c$$ in $$O(r^3\log q)$$ multiplications in $$\mathbb {F}_q$$ , and the algorithm of K. S. Williams and K. Hardy finds a solution in $$O(r^4+r^2\log q)$$ multiplications in $$\mathbb {F}_q$$ . Our refinement finds a solution in $$O(r^3+r^2\log q)$$ multiplications in $$\mathbb {F}_q$$ . Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink