Perancangan dan Analisis Algoritma Pollard’s Rho dan Miller-Rabin pada Komputasi Fungsi Kth Power Summation Berbasis Faktorisasi Prima pada Studi Kasus SPOJ - KPOWERSUM

Salim, Muhammad Fuad (2026) Perancangan dan Analisis Algoritma Pollard’s Rho dan Miller-Rabin pada Komputasi Fungsi Kth Power Summation Berbasis Faktorisasi Prima pada Studi Kasus SPOJ - KPOWERSUM. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201057-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (5MB) | Request a copy

Abstract

Permasalahan Kth Power Summation (KPOWERSUM) merupakan salah satu permasalahan teori bilangan yang meminta perhitungan jumlah seluruh pembagi suatu bilangan dengan setiap pembagi dipangkatkan oleh suatu nilai tertentu. Pendekatan brute force yang menghasilkan seluruh pembagi secara eksplisit menjadi kurang efisien ketika diterapkan pada bilangan berukuran besar karena memiliki kompleksitas komputasi yang tinggi. Oleh karena itu, diperlukan pendekatan yang lebih efisien melalui pemanfaatan faktorisasi prima dan sifat fungsi multiplikatif. Penelitian ini bertujuan untuk merancang dan menganalisis implementasi algoritma Miller-Rabin dan Pollard’s Rho dalam komputasi fungsi Kth Power Summation pada studi kasus SPOJ - KPOWERSUM. Algoritma Miller-Rabin digunakan untuk melakukan uji primalitas, sedangkan algoritma Pollard’s Rho digunakan untuk memperoleh faktorisasi prima dari bilangan komposit. Hasil faktorisasi kemudian dimanfaatkan untuk mentransformasikan fungsi Kth Power Summation ke dalam bentuk deret geometri dan dihitung menggunakan modular exponentiation serta aritmatika modular.
Implementasi dilakukan menggunakan bahasa pemrograman C++ dan dievaluasi melalui pengujian lokal serta pengujian eksternal pada situs SPOJ. Hasil pengujian menunjukkan bahwa implementasi berhasil memperoleh status Accepted pada SPOJ dengan rata-rata waktu eksekusi sebesar 0,21 detik dan penggunaan memori sebesar 5,2 MB. Pengujian lokal juga menunjukkan rata-rata waktu eksekusi sebesar 15,16 milidetik, yang mengindikasikan bahwa implementasi memiliki performa yang stabil pada berbagai kelompok data uji.
Berdasarkan hasil penelitian, kombinasi algoritma Miller-Rabin dan Pollard’s Rho mampu menyelesaikan permasalahan Kth Power Summation secara benar, efisien, dan konsisten pada bilangan berukuran besar. Pendekatan yang diusulkan dapat menjadi alternatif yang efektif dalam penyelesaian permasalahan teori bilangan yang melibatkan faktorisasi prima dan komputasi fungsi aritmatika berbasis pembagi.
======================================================================================================================================
The Kth Power Summation (KPOWERSUM) problem is a number theory problem that requires computing the sum of all divisors of a positive integer, where each divisor is raised to a given power. A brute-force approach that explicitly enumerates all divisors becomes inefficient for large integers due to its high computational complexity. Therefore, a more efficient approach is required by utilizing prime factorization and the multiplicative properties of arithmetic functions. This research aims to design and analyze the implementation of the Miller–Rabin and Pollard's Rho algorithms for computing the Kth Power Summation function using the SPOJ Kth Power Summation problem as a case study. The Miller–Rabin algorithm is employed to perform primality testing, while the Pollard's Rho algorithm is utilized to obtain the prime factorization of composite numbers efficiently. The resulting prime factorization is then transformed into a product of geometric series, which is evaluated using modular exponentiation and modular arithmetic. The proposed solution was implemented in the C++ programming language and evaluated through both local testing and external testing on the SPOJ online judge platform. The experimental results show that the implementation successfully achieved an Accepted verdict on SPOJ with an average execution time of 0.21 seconds and an average memory consumption of 5.2 MB. Furthermore, local performance testing produced an average execution time of 15.16 milliseconds, indicating that the implementation maintains stable performance across different groups of test cases. Based on the experimental results, the combination of the Miller–Rabin and Pollard's Rho algorithms is capable of solving the Kth Power Summation problem correctly, efficiently, and consistently for large integer inputs. The proposed approach provides an effective alternative for solving number-theoretic problems involving prime factorization and divisor-based arithmetic functions.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Faktorisasi Prima, Miller-Rabin, Pollard’s Rho, Prime Factorization, Miller-Rabin, Pollard’s Rho.
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering
Depositing User:	Muhammad Fuad Salim
Date Deposited:	28 Jul 2026 06:41
Last Modified:	28 Jul 2026 06:41
URI:	http://repository.its.ac.id/id/eprint/138623

Actions (login required)

View Item