|
gtozoom has asked for the wisdom of the Perl Monks concerning the following question:
Hello Monks, I am looking at making a faster, more logical prime number generator than simply brite forcing all available numbers. I am looking into a Miller-Rabin primality test, but I don't know how to do modular exponentiation in perl.
Another idea I had was to use the fact that n is prime if (n-1)!+1 is divisable by n. This worked, but the facotorialization created numbers too large for my computer to handle after n=23. If you are interested in this approach, this is the code i used:
print "Number to test: ";
$prime=<>;
$t=($prime-1);
sub fac {
my ($n) = @_;
if ($n < 2) {
return $n;
}
else {
return $n *fac($n-1);
}
}
$r = ((fac($t))+1);
if ($r % $prime) {
print "not prime\n";
} else {
print "prime\n";
}
Any help in making a faster, more logical prime number generator than brute-forcing the whole thing would be appreciated. Thanks for the help, monks. |
Re: Prime Numbers
by blokhead (Monsignor) on Dec 10, 2007 at 00:24 UTC
|
One of the fastest ways would be to use a math library like PARI. It uses very good primality tests internally. I don't have it installed right now, but you should be able to use:
use Math::Pari 'isprime';
my $num = shift || '12345678901';
print isprime($num) ? "$num is prime!\n"
: "$num is composite!\n";
Even if you are looking for the practice of implementing a nice primality test by hand, pari would be a good tool, as it supports all sorts of abstract algebra things (including fast modular arithmetic). If you want to do even that by hand, the above FAQ lists several primality test algorithms that you can use as starting points.
| [reply]
[d/l] |
|
|
I'm really interested in Math::Pari but I haven't been able to get it to install on any of my systems.
You can easily see the issues that Math::Pari has given people by checking out this pass/fail result test results at cpan. The last time I looked it was 113 passes to 160 failures.
What really irks me is that Math::Pari seems to be required for Net::SSH::Perl so I haven't been able to get that to work either.
--
I used to drive a Heisenbergmobile, but every time I looked at the speedometer, I got lost.
| [reply] |
|
|
Hi KurtSchwind,
I've had good success building Math::Pari in the past on both windows and linux by building against PARI-2.1.4. Version 2.1.7 is probably ok, too - but I think there are issues if you try to build against some of the later versions of PARI (is it the 2.3.x versions ? ... I can't remember). In all cases, I've avoided building PARI first, opting instead to place the PARI source within the Math::Pari source - as outlined in the INSTALL file that ships with Math::Pari. Mind you, I haven't built it for a while, so I'm a little rusty on it.
As regards SSH, you might like to try Net::SSH2 (for which you'll need libssh2). That's assuming you're interested only in the SSH2 protocol.
As regards primality testing, Math::GMP (which requires the gmp library) is as good as Math::Pari.
Cheers,
Rob
| [reply] |
|
|
|
|
If you are using AS Perl, Randy Kobes has built Math::Pari (v 2.010500) and provides it through PPM.
CountZero A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James
| [reply] |
|
|
|
|
Re: Prime Numbers
by moritz (Cardinal) on Dec 09, 2007 at 23:13 UTC
|
If you want fast results, search on cpan for prime.
If you want your own approach to work for larger numbers, use bigint. | [reply] |
Re: Prime Numbers
by ikegami (Patriarch) on Dec 09, 2007 at 23:13 UTC
|
my @primes = (2, 3, 5, 7, 11, 13, 17, 19);
sub get_a_prime {
return $primes[rand @primes];
}
sub get_primes_iter {
my $i = 0;
return sub {
return if $i > $#primes;
return $primes[$i++];
};
}
print(get_a_prime(), "\n");
my $i = get_primes_iter();
while (my ($prime) = $i->()) {
print("$prime\n");
}
Or do you have a more specific criteria?
| [reply]
[d/l] |
|
|
The very fastest way would be to just grab them from one of the files here!
CountZero A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James
| [reply] |
Re: Prime Numbers
by pc88mxer (Vicar) on Dec 10, 2007 at 07:27 UTC
|
This won't make it any faster, but you can avoid having to use the bigint package by reducing the factorial mod $prime every time you add a factor:
my $r = 1;
my $k = 2;
while ($k < $prime) {
$r = ($r * $k) % $prime;
$k++;
}
if ($r + 1 % $prime == 0) {
print "prime\n";
} else {
print "not prime\n";
}
Then $r never gets bigger than $prime.
| [reply]
[d/l]
[select] |
Re: Prime Numbers
by RMGir (Prior) on Dec 10, 2007 at 14:21 UTC
|
gtozoom,
Some friends and I came up with this years ago when we were trying to generate large primes ourselves, but I'm sure it already exists somewhere in MathWorld or Wikipedia...
You can save a lot of space if, instead of computing (n-1)!, you compute the "minimal factorial" (which isn't the real name for it, that I know of).
The idea is that you don't need all the "junk" in (n-1)! - you only need a number that will be divisible by anything (n-1)! would have been divisible by.
What you do is, instead of computing 1*2*...*(n-1), you compute the prime factors for each number in 1..n-1, AND THEIR MULTIPLICITY. For example, 80 is 2^4*5, so its prime factors are 2 (with multiplicity 4), and 5 (multiplicity 1).
Now, for all the prime factors you collected, you only need to keep _the highest multiplicity_. Multiply the prime factors at the highest multiplicity for each, and you've got a number just as good as (n-1)!, but MUCH smaller. For example, you've eliminated about 2^(n/2) un-needed powers of 2, since half the numbers you were multiplying together were even...
Make sense??
| [reply] |
Re: Prime Numbers
by gam3 (Curate) on Dec 10, 2007 at 22:52 UTC
|
| [reply] |
|
|
