Desain Algoritma Randomisasi pada persoalan Hashing : Studi Kasus SPOJ 40643 AHASHREV - The Revenge Of Anti Hash

Samsico, Alexander Weynard (2024) Desain Algoritma Randomisasi pada persoalan Hashing : Studi Kasus SPOJ 40643 AHASHREV - The Revenge Of Anti Hash. Project Report. [s.n.], [s.l.]. (Unpublished)

Text 5025211014-Project_Report.pdf - Accepted Version Download (1MB)

Abstract

Hashing merupakan suatu teknik yang di mana mengubah suatu data, seperti string, menjadi suatu nilai hash dengan fungsi tertentu. Diberikan suatu fungsi hashing yang menerima suatu string untuk diubah menjadi nilai hash dengan parameter bilangan basis B dan bilangan modulo M. Pada persoalan hashing ini, diberikan pasangan B dan M sebanyak K dan meminta untuk mencari dua string berbeda yang memiliki nilai hash yang sama berdasarkan setiap pasangan B dan M yang diberikan. Teknik ini dikenal sebagai teknik anti-hash di mana untuk mencari dua string berdasarkan nilai hash yang sudah diketahui. Jika menggunakan pendekatan langsung berupa mencari string dari setiap kombinasi yang ada, maka tidak efisien karena membutuhkan waktu yang sangat lama berdasarkan panjang batasan string yang diberikan. Kerja Praktik ini melakukan desain algoritma yang efektif dan efisien untuk menyelesaikan persoalan hashing. Kerja Praktik ini mengusulkan untuk mendesain algoritma randomisasi untuk menyelesaikan persoalan hashing. Algoritma Randomisasi merupakan suatu algoritma yang di mana membangkitkan suatu nilai secara acak dengan banyak percobaan sehingga mendapatkan nilai yang benar dan sesuai dengan teori probabilitas. Algoritma randomisasi juga mendukung Birthday Paradox sebagai dasar teori untuk menentukan berapa banyaknya percobaan yang diperlukan agar mendapatkan hasil yang diinginkan, dalam kasus ini adalah dua string. Algoritma ini menggunakan teknik Birthday Attack dan Composition Attack untuk mencari dua string dengan nilai hash yang sama berdasarkan banyaknya pasang B dan M yang diberikan. Teknik Birthday Attack dapat mencari dua string yang sama pada setiap pasang B dan M serta Composition Attack sebagai transisi untuk setiap pasang B dan M yang ditentukan. Metode uji coba yang dilakukan adalah melalui uji coba kebenaran dengan mengirimkan kode sumber berdasarkan desain algoritma yang dibuat pada situs penilaian Sphere Online Judge (SPOJ). Berdasarkan uji coba tersebut, didapatkan hasil kinerja randomisasi untuk menyelesaikan persoalan hashing studi kasus SPOJ 40643 AHASHREV – The Revenge Of Anti Hash diraih dengan waktu minimum 1.47 detik dengan 62 MB sebagai hasil terbaik. Hasil kinerja juga menunjukkan waktu yang dibutuhkan dengan rata-rata 1.865 detik dan memori yang dibutuhkan dengan rata-rata 70.65 MB serta memori minimum 59 MB. Jadi, desain algoritma randomisasi efektif dan efisien dalam menyelesaikan persoalan hashing.
============================================================================================================================
Hashing is a technique that transforms data, such as a string, into a hash value using a specific function. Given a hashing function that takes a string and converts it into a hash value with base B and modulo M parameters. In this hashing problem, pairs of B and M are provided K times, and the task is to find two different strings that have the same hash value based on each provided pair of B and M. This technique is known as the anti-hash technique, where the goal is to find two strings based on a known hash value. If a direct approach is used by searching for strings from every possible combination, it would be inefficient because it would take a very long time based on the length of the given string constraints. This practical work designs an effective and efficient algorithm to solve the hashing problem.This practical work proposes designing a randomized algorithm to solve the hashing problem. Randomized Algorithm is an algorithm that generates a value randomly through many trials to obtain a correct value in accordance with probability theory. Randomized algorithm also supports the Birthday Paradox as a theoretical basis to determine how many trials are needed to achieve the desired result, in this case, two strings. This algorithm uses the Birthday Attack and Composition Attack techniques to find two strings with the same hash value based on the number of given pairs B and M. The Birthday Attack technique can find two identical strings for each pair of B and M, while the Composition Attack serves as a transition for each specified pair of B and M. The testing method used was through a correctness test by submitting the source code based on the algorithm design created on the Sphere Online Judge (SPOJ) platform. Based on these tests, the performance results of the randomized for solving the hashing problem in the SPOJ 40643 AHASHREV – The Revenge Of Anti Hash case study were achieved with a minimum time of 1.47 seconds and 62 MB as the best result. The performance results also show an average time of 1.865 seconds and an average memory usage of 70.65 MB, with a minimum memory usage of 59 MB. Therefore, randomized algorithm design effectively and efficiently solves the hashing problem.

Item Type:	Monograph (Project Report)
Uncontrolled Keywords:	Hashing, Anti-Hash, Algoritma Randomisasi, Birthday Paradox, Birthday Attack, Composition Attack
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Alexander Weynard Samsico
Date Deposited:	25 Nov 2024 02:53
Last Modified:	25 Nov 2024 02:53
URI:	http://repository.its.ac.id/id/eprint/115799

Actions (login required)

View Item