Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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
in thread Vampire Numbers

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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://174864]
[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
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (244 votes). Check out past polls.