good chemistry is complicated,and a little bit messy -LW PerlMonks

Re: Re: Re: Re: Factors

by gumby (Scribe)
 on Jun 15, 2002 at 19:21 UTC ( #174864=note: print w/replies, xml ) Need Help??

in reply to Re: Re: Re: Factors

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;
}
}

Create A New User
Node Status?
node history
Node Type: note [id://174864]
help
Chatterbox?

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2018-03-24 14:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (299 votes). Check out past polls.

Notices?