Here's a more 'reference' style implementation. Basically, this is the algorithm you'll find in the paper 'Square Roots, From 1; 24, 51, 10 To Dan Shanks' by Ezra Brown, but at the cost of using Math::BigInt.
#!/usr/bin/perl -w
use Math::BigInt ':constant';
use strict;
sub tonelli {
my ($s, $e, $n, $x, $b, $g, $r, $m, $t);
my ($a, $p) = @_;
die "$a has no square roots (mod $p)" if $a**(($p-1)/2) % $p == -1;
$s = $p-1;
$e = 0;
while ($s % 2 == 0) {
$s = $s / 2;
$e++;
}
for ($n = 2; $n >= 2; $n++) {
last if $n**(($p-1)/2) % $p == $p-1;
}
$x = $a**(($s+1)/2) % $p;
$b = $a**$s % $p;
$g = $n**$s % $p;
$r = $e;
$t = $b;
while (1) {
for ($m = 0; $m <= $r-1; $m++) {
last if $t % $p == 1;
$t = $t**2;
}
return $x if $m == 0;
$x = $x * $g**(2*($r-$m-1)) % $p;
$b = $b * $g**(2*($r-$m-1)) % $p;
$g = $g**(2*($r-$m)) % $p;
$r = $m;
}
}