Desain dan Analisis Algoritma Segmented Sieve pada Studi Kasus SPOJ EVENSEMIP - Even Semiprime Runs

Jaya, Fandi Pranata (2021) Desain dan Analisis Algoritma Segmented Sieve pada Studi Kasus SPOJ EVENSEMIP - Even Semiprime Runs. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111740000056-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (2MB) | Request a copy

Abstract

Semiprime adalah sebuah bilangan komposit yang merupakan hasil perkalian dari dua bilangan prima. Semiprime digunakan dalam bidang kriptografi. Salah satu kegunaan dari semiprime adalah untuk public key encryption dari RSA (Rivest–Shamir–Adleman) encryption yang terbentuk dari perkalian dua bilangan prima. Sebuah run dari semiprime merupakan sebuah contiguous subsequence dari semiprime. Sebuah even run dari semiprime merupakan sebuah run yang hanya berisi bilangan genap saja. Permasalahan yang selanjutnya muncul adalah bagaimana cara mencari even semiprime runs terpanjang dalam suatu jangkauan bilangan.
Topik tugas akhir ini mengulas dua metode yang optimal untuk mencari sebuah even run terpanjang dari semiprime dalam suatu jangkauan bilangan yaitu Segmented Sieve tanpa pra-komputasi semiprime dan Segmented Sieve dengan pra-komputasi semiprime. Segmented Sieve akan digunakan untuk mencari semiprime dalam suatu jangkauan bilangan.
Tugas akhir ini berhasil menyelesaikan permasalahan di atas dengan waktu eksekusi Segmented Sieve tanpa pra-komputasi semiprime dan Segmented Sieve dengan pra-komputasi semiprime rata-rata 6.428 detik dan 6.064 detik dengan penggunaan memori rata-rata 176.4 MB dan 185.6 MB.
========================================================================================================
Semiprime is a composite number that is the product of two prime numbers. Semiprime is used in the field of cryptography. One of the uses of semiprime is for public key encryption of RSA (Rivest – Shamir – Adleman) encryption which is formed from multiplying two prime numbers. A run of semiprimes is a contiguous subsequence of semiprimes. An even run of semiprimes is a run that contains only even numbers. The next problem that arises is how to find the longest even semiprime runs.
The topic of this thesis discusses two optimal methods to find the longest even semiprime runs in a range of numbers, namely Segmented Sieve without semiprime precomputation and Segmented Sieve with semiprime precomputation. A Segmented Sieve will be used to find semiprime numbers in a range of numbers.
This thesis is successful in solving the above problems with the execution time of Segmented Sieve without semiprime precomputation and Segmented Sieve with semiprime precomputation an average of 6.428 seconds and 6.064 seconds with an average memory usage of 176.4 MB and 185.6 MB.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Kata Kunci: even semiprime runs, pra-komputasi semiprime, segmented sieve, semiprime ====================================================== Keywords: even semiprime runs, segmented sieve, semiprime, semiprime precomputation
Subjects:	T Technology > T Technology (General) > T11 Technical writing. Scientific Writing T Technology > T Technology (General) > T58.8 Productivity. Efficiency
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Fandi Pranata Jaya
Date Deposited:	26 Jul 2021 23:33
Last Modified:	26 Jul 2021 23:36
URI:	http://repository.its.ac.id/id/eprint/84487

Actions (login required)

View Item