Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

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]
[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."
[marto]: better: "If a type of behaviour, event, or situation is par for the course, it is not good but it is normal or as you would expect"
[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?
Others about the Monastery: (5)
As of 2017-07-26 10:14 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (388 votes). Check out past polls.