Penerapan Euler Totient pada Penyelesaian Permasalahan SPOJ-ADAHW: Ada and Homework

Therry, Gilbert (2020) Penerapan Euler Totient pada Penyelesaian Permasalahan SPOJ-ADAHW: Ada and Homework. Other thesis, Institut Teknologi Sepuluh Nopember.

Preview	Text 05111640000051-Gilbert-Lijaya-Therry-Buku_TA.pdf Download (1MB) | Preview
	Text 05111640000051-Undergraduate_Thesis.pdf Download (1MB)

Abstract

Permasalahan Tugas Akhir ini bermula dari adanya permasalahan Ada and Homework (ADAHW) pada SPOJ. Permasalahan tersebut menggambarkan sebuah bilangan N dan yang akan dicari adalah jumlah dari faktor persekutuan terbesar antara K1 dan N, dimana K adalah semua bilangan bulat positif dimulai dari 2 sampai N. Syarat yang harus dikerjakan dalam permasalahan di atas menimbulkan hal-hal baru yang membutuhkan metode penyelesaian yang tepat untuk menyelesaikan permasalahan dari ADAHW. Hal pertama adalah batasan dari nilai N yang cukup besar yaitu 2 hingga 1018. Sehingga tentunya tidak dapat dilakukan iterasi satu persatu angka karena akan memakan waktu yang sangat lama dengan bilangan sebesar 1018 . Karena itu dibutuhkan sebuah solusi yang cukup optimal untuk mengatasi rentang N yang cukup besar ini. Pada Tugas Akhir ini, awalnya permasalahan ADAHW ini akan dimodelkan dulu untuk memunculkan Euler Totient pada permasalahannya dengan menggunakan Menon Identity. Setelah itu akan diimplementasikan algoritma Pollard Rho Brent dan Miller Rabin yang dapat menangani faktorisasi prima dari angka-angka besar dengan cepat. Solusi yang dibuat cukup efisien dengan rata-rata waktu penyelesaian 0,53 detik dengan penggunaan memori 4,7 MB.
==================================================================================================================================
This Thesis starts with Ada and Homework problems on SPOJ. This problem describes a number N and we will try to find the sum of the greatest common divisor between K-1 and N, where K are all positive integers starting from 2 to N. This conditions creates things that need a correct method to solve problems from ADAHW. The first problem is the range of N is from 2 to 1018. So of course iterations cannot be done one by one number because it will take a very long time with 1018 . So we need a better solution to overcome a fairly large range of N. In this Thesis, initially this problem will be modelled first to bring Euler Totient to the problem using Menon Identity. After that, Pollard Rho Brent and Miller Rabin algorithms will be implemented which can handle prime factorization of large numbers quickly. The solution made is quite efficient with an average completion time of 0.53 seconds with 4.7 MB of memory usage.

Item Type:	Thesis (Other)
Additional Information:	RSIf 006.746 The p-1 2020
Uncontrolled Keywords:	Euler Totient, Pollard Rho Brent, Miller Rabin.
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Computer Engineering > 90243-(S1) Undergraduate Thesis
Depositing User:	Gilbert Lijaya Therry
Date Deposited:	11 Mar 2025 03:00
Last Modified:	11 Mar 2025 03:00
URI:	http://repository.its.ac.id/id/eprint/73162

Actions (login required)

View Item