Sidang Tugas Akhir

Muhammad Mukafi
G54103011

Aspek Komputasi Solusi Residu Kuadratik

Dalam menentukan apakah suatu kongruensi ( ) 2 mod x a p º dengan a bilangan bulat dan p bilangan prima mempunyai solusi atau tidak dapat digunakan Kriteria Euler. Jika ( ) ( ) 1 / 2 1 mod p a p - º maka ( ) 2 mod x a p º mempunyai solusi. Jika ( ) 2 mod x a p º mempunyai solusi, maka untuk mementukan solusinya dapat digunakan Algoritma RESSOL (Residue Solver). Algoritma RESSOL adalah algoritma acak (randomized algorithm) dan bukan algoritma deterministic, tetapi prosedur perhitungannya lebih praktis dan cepat. Algoritma RESSOL hanya dapat digunakan untuk mencari solusi dari ( ) 2 mod x a p º dengan p prima ganjil. Tetapi dari Algoritma RESSOL tersebut dapat dikembangkan menjadi beberapa algoritma untuk mencari solusi dari ( ) 2 mod x a pq º dengan p dan q prima ganjil, dan 2 (mod ) j x a p º dengan p prima ganjil dan bilangan bulat 2 j ³ .