Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
ขั้นตอนวิธีทำซ้ำแบบนิวตันสำหรับการคำนวณพหุนามมอดุลาร์ผกผันภายใต้มอดุโล xn±1 สำหรับบางรูปแบบของ n
Year (A.D.)
2021
Document Type
Thesis
First Advisor
Wutichai Chongchitmate
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2021.5
Abstract
This thesis presents an algorithm for computing the modular inverse of a polynomial in a ring of polynomials over a finite field $\mathbb{F}_q$ with a characteristic $p$. Given a polynomial $f$ and a natural number $r$, by applying the idea of the Newton iteration algorithm, the fast division algorithm used to find the inverse of $f$ under modulo $x^{p^r}-1$, $x^{p^r}+1$, $x^{2p^r}-1$ and $x^n-1$ where $n=2^r d$ for some $r,d\in\mathbb{N}$, is established. The cost analysis for these cases show that the algorithm has the computational complexity of $\mathcal{O}(n \log n)$ which is more efficient than the Half-GCD algorithm in terms of computational complexity for large $n$.
Other Abstract (Other language abstract of ETD)
วิทยานิพนธ์ฉบับนี้นำเสนอขั้นตอนวิธีสำหรับการคำนวณมอดุลาร์ผกผันของพหุนามในริงของพหุนามเหนือฟิลด์จำกัด $\mathbb{F}_q$ ที่มีลักษณะเฉพาะ $p$ เมื่อกำหนดพหุนาม $f$ และจำนวนนับ $r$ โดยใช้แนวคิดของขั้นตอนวิธีทำซ้ำแบบนิวตัน จะได้ว่าเราสามารถหาขั้นตอนวิธีการหารแบบเร็วที่ใช้หาตัวผกผันของ $f$ ภายใต้มอดุโล $x^{p^r}-1$ , $x^{p^r}+1$, $x^{2p^r}-1$ และ $x^n-1$ เมื่อ $n=2^r d$ และ $r,d\in\mathbb{N}$ ได้ โดยเราได้มีการวิเคราะห์ความซับซ้อนในการคำนวณของขั้นตอนวิธีภายใต้มอดุโลเหล่านี้ไว้ที่ $\mathcal{O}(n \log n)$ ซึ่งมีประสิทธิภาพมากกว่าขั้นตอนวิธีแบบ Half-GCD ในแง่ของการคำนวณสำหรับ $n$ ขนาดใหญ่
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Sripatthanakul, Samakorn, "Newton iterative algorithm for polynomial modular inversion modulo xn±1 for some patterns of n" (2021). Chulalongkorn University Theses and Dissertations (Chula ETD). 4547.
https://digital.car.chula.ac.th/chulaetd/4547