Chulalongkorn University Theses and Dissertations (Chula ETD)

Other Title (Parallel Title in Other Language of ETD)

ขั้นตอนวิธีทำซ้ำแบบนิวตันสำหรับการคำนวณพหุนามมอดุลาร์ผกผันภายใต้มอดุโล xn±1 สำหรับบางรูปแบบของ n

Year (A.D.)


Document Type


First Advisor

Wutichai Chongchitmate


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




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$ ขนาดใหญ่

Included in

Mathematics Commons



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.