Perancangan dan Analisis Penerapan Metode Randomized Algorithm pada Studi Kasus SPOJ 40643 - The Revenge of Anti Hash

Akram, Afiq (2025) Perancangan dan Analisis Penerapan Metode Randomized Algorithm pada Studi Kasus SPOJ 40643 - The Revenge of Anti Hash. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201270-Undergraduated_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2027. Download (7MB) | Request a copy

Abstract

Hash polinomial dari sebuah string ditentukan dengan mengonversi setiap karakter dalam string menjadi nilai numerik berdasarkan urutannya dalam alfabet. Pada studi kasus The Revenge of Anti Hash, penelitian ini berfokus pada menghitung jumlah string yang memiliki hash polinomial yang sama dengan menggunakan fungsi hash polinomial yang telah ditentukan. Permasalahan utama dalam tugas akhir ini adalah ruang pencarian yang sangat luas akibat kombinasi karakter yang beragam, serta pengulangan subproblem yang muncul pada iterasi. Tugas akhir ini berfokus pada pencarian tabrakan hash polinomial yang muncul akibat terbatasnya ruang hash dibandingkan dengan jumlah string yang mungkin. Tantangan ini memerlukan pendekatan yang mampu menjelajahi ruang pencarian besar secara efisien. Untuk itu, digunakan Birthday Attack, sebuah metode berbasis Randomized Algorithm yang memanfaatkan prinsip probabilitas, di mana peluang tabrakan meningkat signifikan saat jumlah percobaan mendekati akar dari ukuran ruang hash. Selain itu, Composition Attack diterapkan berdasarkan metode yang ditemukan dalam forum pengembang Codeforces, yang membahas teknik optimasi pencarian tabrakan hash. Pendekatan ini mengurangi waktu komputasi dengan memanfaatkan hasil tabrakan dari pasangan base-modulus sebelumnya untuk melanjutkan proses pencarian pada iterasi berikutnya. Metode uji coba dilakukan melalui uji kebenaran dengan mengirimkan kode sumber program ke Sphere Online Judge (SPOJ) dan uji kinerja untuk mengukur efisiensi algoritma terhadap batasan waktu dan memori. Berdasarkan hasil uji coba, solusi dengan pendekatan Randomized Algorithm, Birthday Attack, dan Composition Attack menghasilkan waktu rata-rata 1,91 detik dan memori rata-rata 71,4 MB. Hasil dari tugas akhir ini diharapkan dapat berkontribusi pada pengembangan teknik pencarian tabrakan hash yang lebih efisien dalam konteks pemrograman kompetitif dan kriptografi.
===================================================================================================================================
Polynomial hashing of strings is determined by converting each character in the string into its numeric value based on its alphabetical order. In the case study "The Revenge of Anti Hash," this research focuses on calculating the number of strings that share the same polynomial hash value using a pre-defined polynomial hashing function. The primary challenge in this thesis lies in the expansive search space resulting from the diverse combinations of characters and the recurring subproblems that emerge during iterations. This thesis centers on finding polynomial hash collisions caused by the constrained hash space relative to the number of possible strings. Addressing this requires an approach capable of efficiently navigating the large search space. To achieve this, the birthday attack is employed, a randomized algorithm-based method leveraging probabilistic principles where the likelihood of collisions significantly increases as the number of attempts approaches the square root of the hash space size. Furthermore, a composition attack is applied based on methods discussed in the developer forums of Codeforces, which explore optimization techniques for hash collision searches. This approach reduces computational time by utilizing collision results from previous base-modulus pairs to continue the search process in subsequent iterations. The testing methodology involves validating the algorithm by submitting the program source code to the Sphere Online Judge (SPOJ) and measuring its performance to evaluate efficiency under time and memory constraints. Based on the experimental results, the solution employing randomized algorithm, birthday attack, and composition attack achieved an average execution time of 1.91 seconds and an average memory usage of 71.4 MB. The outcomes of this thesis are expected to contribute to the advancement of more efficient hash collision search techniques in the contexts of competitive programming and cryptography.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	birthday attack, composition attack, polinomial hash, randomized algorithm
Subjects:	Q Science Q Science > QA Mathematics Q Science > QA Mathematics > QA184 Algebra, Linear Q Science > QA Mathematics > QA76.6 Computer programming. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Electrical Engineering > 20201-(S1) Undergraduate Thesis
Depositing User:	Afiq Akram
Date Deposited:	01 Feb 2025 06:55
Last Modified:	01 Feb 2025 06:55
URI:	http://repository.its.ac.id/id/eprint/117251

Actions (login required)

View Item