Aspek Komputasi Solusi Residu Kuadratik

Abstract

Dalam menentukan apakah suatu kongruensi x2 º a (mod 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 x2 º a (mod p) mempunyai solusi. Jika x2 º a (mod 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 x2 º a (mod p) dengan p prima ganjil. Tetapi dari Algoritma RESSOL tersebut dapat dikembangkan menjadi beberapa algoritma untuk mencari solusi dari x2 º a(mod pq) dengan p dan q prima ganjil, dan 2 (mod ) j x º a p dengan p prima ganjil dan bilangan bulat j ³ 2 .