redmist's Diabolical Scheme for Prime Domination

[redmist]

I have an evil plan. It goes a little something like this:

Seeing as how prime numbers are important to those crazy Math Kids and cryptographers, THE MAN^(R) has dedicated several supercomputers to crunching numbers to find a higher prime. This gives redmist a bad idea good idea.

1. Write a script to find primes.
2. Beat THE MAN^(R) at his own game.
3. Be popular with all the ladies.

This idea, like most of my ideas, is completely outlandish. But even with this in mind, I would like to bring this to a New Level of the absurd. That's where you come in.

I have searched on CPAN for any modules to aid me in this endeavour, but to no avail. I have made attempts at coming up with my own algorithm, and have researched other peoople's (read: crazy Math Kids) algorithms, but I have failed at my own and failed to understand the others.

I need recommendations of modules or algorithms. If you don't know of any modules, I would deeply appreciate any tips on how to Roll My Own. I have thoroughly thought this process through, and eventually plan to have it to have a client/server (which I like to call scout/mothership) relationship so I can have clients on many boxs and IPC (Inter-Process Communication). Eventually, the database with all the big ass numbers in it will grow too "big", so what I am going to do is check the DB periodically and if it is too big, I will print out the number(s) and empty the DB. (And yes I realize that the numbers will get So Incredibly Large that there won't be enough hard drive space, but I think Larry Ellison is rich (and crazy) enough to give me money for 500TB of RAID space.)

Thanks for your help,
redmist

[lhoward]

Any "modern, efficient" method of finding primes is very advanced math intensive. Applied Cryptography has a good section of prime factoring and determining if a number is likely prime. Public key encryption systems based on large prime numbers (RSA) don't actually factor the large prime numbers. They generate numbers using a technique that ensures that they are probably prime. This is a great shortcut, but won't work for claiming a mathematical record like you are proposing as the number is only probably prime (extremely high certainty that it is prime, but still not %100 guaranteed).

There are many simple prime number algorightms around, unfortunately the simple ones aren't efficient. The Sieve of Erastothenes is a classic example. I do not know of any perl modules that explicitly implement prime number type functionality. Below is a simple and extermely inefficient is_prime function.

sub is_prime{
  my $n=shift;
  return 0 if($n != int($n));
  my $m=sqrt($n);
  for(my $c=2;$c<=$m;$c++){
    return 0 if($n/$c == int($n/$c));
  }
  return 1;
}

Any way you slice it, I don't think Perl is the best language for a high performance prime number analyzer. Your best bet would be to find a language designed explicitly for doing large number math if you seriously want to go after a "largest prime number" record.

[redmist]

Thanks lhoward. I looked at the web page that you recommended and it helped me some with my thought on how I am going to approach the math in this project. As for your suggestion to use another, more mathematically inclined language, it's not an issue for me because this project is to learn Perl (and stick it to the man).

redmist
redmist.dyndns.org
[e-mail]

[BlaisePascal]

Here's my attempt at a Sieve of Eratothenes... I don't use grep that much, so I won't claim that this works...

@numbers = (2 .. 1_000_000);
@primes = ( );

while (my $prime = shift @numbers) {
  push @primes,$prime;
  @numbers = grep { ($_ % $prime) != 0 } @numbers;
} 

print $primes;

[larsen]

If you're interested in prime numbers, you should consider implementing a probabilistic primality test.
What does it mean? If a number fails this test, it is not a prime. If the number passes, it may be a prime.

Instead of providing a bunch of information, I suggest starting from this page, describing Rabin-Miller test.

I also invite you to visit my links page: it may be useful (well, someone said me it was :))

Larsen

[Adam]

For an implementation of the Rabin-Miller test, see this node

[Nitsuj]

Well, I kinda disagree. Encryption is important, especially if you work for government. I, quite personally, know that I don't want everyone in the world to know where we (the US) store our nukes. I also can live without every jerk on the street being able to crack the files containing my credit card number, my medical records, sappy love letters to women from mars.

A more interesting approach, would be, rather than finding all of the prime numbers, to find a quick way to factor the product of 2 prime numbers. That's the REAL killer app of cryptography. Do that and all modern encryption systems are rendered useless. What then? Well, then, probably, a few people will learn that you don't put systems requiring security onto the internet. Of course, then we have the problem of having a bunch of data that really SHOULD BE SECRET not being secret. Information wants to be free, but lets leave my love life out of this.

There ARE many algorithms to do this (search "sieve of erostothenes").

Just remember that storing any number of primes sufficient to crack current encryption standards would be futile. It would take terrabytes.

Just Another Perl Hacker

[gryng]

I though women were from Venus? You know the really hot poisonous planet. Not the mild (in terms of other planets out there) almost livable planet called Mars :) . Why else do you think they put up with 'our' antics -- they need the real estate!

Cheers,
Gryn

p.s. Ow! In advanced to all the --'s I'm about to get. :)

[Nitsuj]

Oh yeah, I keep forgetting that.

Just Another Perl Hacker

[ferrency]

Before Too many people post their Sieves here, it should be noted that there is another thread about this elsewhere:

sieve of erothenes

Alan

[barndoor]

merlyn wrote the following article on this in Unix review. Sieve article