sqrtmod(4, 8) fails

[hvds]

% $PERL -MMath::Prime::Util=sqrtmod -wle 'print sqrtmod(4, 8) // "undef"'
undef
% MPU_NO_XS=1 $PERL -MMath::Prime::Util=sqrtmod -wle 'print sqrtmod(4, 8) // "undef"'
2
% 

Spotted "if 8|n 'a' must = 1 mod 8 ..." in the code, and thought "eh?"

[danaj]

Thanks. It looks like this was fixed with the big sqrtmod / rootmod rewrite last August. But it's been far too long since a release.

$ perl -MMath::Prime::Util=sqrtmod -wle 'print sqrtmod(4, 8)'
2

I just added it to the tests.

[hvds]

Thanks, I hadn't appreciated there was so much difference between github and release (and sqrtmod doesn't even appear in the already lengthy list of changes). I'll see if I can work out how to install from github.

[hvds]

Just taking a quick look through latest sqrtmod PP, I noticed this:

diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index 69b8cab..625e377 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -3879,7 +3879,7 @@ sub sqrtmod {
     for my $r (2 .. $lim) {
       return $r if (($r*$r) % $n) == $a;
     }
-    undef;
+    return undef;
   }
 
   $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt';

[danaj]

The GMP code still needs a lot of changes to rootmod / sqrtmod, which is the main bottleneck for my release. I would like to get the GMP backend out first. But other things have come up and I just haven't put enough time into it lately.

I also wanted to

Thanks -- that's a nice find. The PP code needs some looking at for sure (it's mentioned in the TODO which just keeps getting longer).

Also thank you very much for the reports! It's good motivation.

[hvds]

Well I originally looked because my own code has a comment # TODO: use Tonelli-Shanks, and I thought before I start exploring that I should check if MPU already has something ...

[danaj]

Ah. Tonelli-Shanks and Cipolla work modulo a prime. It got substantially more complicated with both composite modulos as well as arbitrary k-th roots. Tonelli-Shanks still exists in the C code in both an extended k-th root version with prime k and p, as well as the original for square roots modulo prime p.

There's a pretty standard Tonelli-Shanks on RosettaCode: https://rosettacode.org/wiki/Category:Perl

It looks like the PP code until last August really didn't do much of anything other than try the fixed methods for p % 4 = 3 and p % 8 = 5 before doing trial search. A quick test with the RosettaCode Tonelli-Shanks in place of the current (github) Cipolla code gets the same results and essentially the same performance. I'm not entirely sure why I chose Cipolla other than it's simpler especially when concerned with bigints.

[danaj]

GMP code with full sqrtmod implementation has been pushed.

My rootmod implementation (in C and PP) uses znlog to solve a discrete log, which isn't in GMP, so that would need to be written first. But that's another topic.

[hvds]

Am I right to guess that you are pushing towards an imminent release?

I've pushed commit 183d150be0 to my code for now, but the people using it are not sophisticated git users: it would help a lot if I could target a release instead.

My rootmod implementation ...

Here's mine, though it isn't fully general: rootmod.c.

.. uses znlog [...] But that's another topic.

Fingers crossed that that topic is GNFS. :)