We don't bite newbies here... much 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?
 [marto]: yep :) [Discipulus]: being her marto, can you explain what "Par for the course I'm afraid." means? Discipulus here.. [marto]: "what is normal or expected in any given circumstances." [Discipulus]: thanks i was unable to decide where to split the sentece [marto]: FWIW search.cpan rarely has issues, see http://noc.perl. org for a route to report problems [oakbox]: thanks, marto. [marto]: there was a period where search.cpan had some frequent outages for (IIRC) a couple of weeks. I've not had any problems since, until today. [marto]: this was about 16 months ago maybe. the noc team are, in my experience, very responsive to reports of issues, so please raise the issue after checking known problems/outages

How do I use this? | Other CB clients
Other Users?
As of 2017-07-26 10:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (388 votes). Check out past polls.