Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

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]
[Discipulus]: i'v installed ubuntu 16.04lts and i'm quite disappointed: is deadly simmilar to new win osses where you cannot find even simple things...
[Corion]: Hi Discipulus ;)
[Corion]: Mj1234: Maybe Ubuntu didn't package Devel::GDB? In that case, consider using local::lib and install the module from CPAN
[Corion]: But a quick Google search turns up this page, which seems to suggest that it should be packaged
[Discipulus]: iirc active perl has repositories only for last 2 o 3 major release of perl Mj1234. I strongly suggest portable version of strawberry perl and use cpan client to install modules
[choroba]: Also, who needs GDB when there's hdb?

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (10)
As of 2016-12-07 08:55 GMT
Find Nodes?
    Voting Booth?
    On a regular basis, I'm most likely to spy upon:

    Results (125 votes). Check out past polls.