XP is just a number 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?
 [choroba]: Dangers of WFH: a mailman rings, brings a parcel for my wife, I need to go outside, take my son with me, sign a paper *and* into the postman's mobile app, get back. Guess what the soup was doing meanwhiles? [Discipulus]: soup without heat protections as CPUs are doomed to burned.. [1nickt]: The dangers of milk-based soup, you mean? [Corion]: choroba: Ouch! But you don't need that many external events for that. I have on several occasions set up milk to cook and then programmed a bit, only to find the milk burned and congealed over the stove :-/ [choroba]: it's still edible, just need to scour the pot [1nickt]: Corion I have a large site I need to check for broken links and absolute links. Making a scraper is easy of course; a spider that crawls a whole site is a little more involved ... I was planning a queue-based tool. Intersted to see what you do...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (9)
As of 2017-10-18 11:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (244 votes). Check out past polls.

Notices?