3

i need to make Python app to make a random prime number between 10^300 and 10^301 , i done it with this but its very slow. any solution?


import random , math
check_prime = 0


print "Please wait ..."
def is_prime(n):
    import math
    n = abs(n)
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 1

    return True



while check_prime == 0 :
    randomnumber = random.randrange(math.pow(10,300),math.pow(10,301)-1)
    if is_prime(randomnumber):
        print randomnumber
        break
ShirazITCo
  • 1,041
  • 6
  • 23
  • 38
  • 6
    Precalculate all primes between 10^300 and 10^301, add this list to your code and select a prime from that list? – Ocaso Protal Apr 12 '11 at 07:00
  • 2
    You call it "very slow"? `math.sqrt` of any number bigger than 10^300 is at least 10^150. If my computer needs 25ms to iterate over `xrange(1000000)` (equals 10^6) and does nothing more, it will need around 10^130 ages of the universum to iterate over 10^150 numbers. So there's probably other way to check the primes than your `is_prime` implementation. – eumiro Apr 12 '11 at 07:10
  • 7
    @Ocaso: there are 9000000000000000000000000000000(plus another 270 zeros) numbers between 10^300 and 10^301. If only one billionth part of them is a prime number, it will still not fit into the RAM. – eumiro Apr 12 '11 at 07:20
  • 5
    Who gave @Ocaso no less than FIVE uparrows for his comment?? Using [this](http://mathworld.wolfram.com/PrimeCountingFunction.html) information I estimate his suggested list would contain Li(10^301) - Li(10^300) = 1.3 * 10^298 items. Remember that the visible universe is estimated to contain about 10^80 atoms. [Wikipedia](http://en.wikipedia.org/wiki/Primality_test) states that the estimated number of operations required to check the primality of one number of this magnitude is log(10^300)^6 = 1.1 * 10^17, which would take approximately 1.1e17 / 160E9 / 60^2 = 190 hours on a 160 000 MIPS CPU. – Lauritz V. Thaulow Apr 12 '11 at 08:14
  • @lazyr, @eumiro (BTW: I gave both of you upvotes): I know that it is impossible to handle **all** primes in that scope, but @ShirazITCo didn't say what's the use case for his problem. In some cases it might be better to have a calculated list of primes. – Ocaso Protal Apr 12 '11 at 08:31
  • @Ocaso Protal: Are you implying that your comment about precalculating all primes was actually meant seriously? Please reconsider that... – sleske Apr 12 '11 at 10:27
  • @sleske Nooooo! As @lazyr showed, lot of calculating power is needed for the complete list. But depending on the use case you could run a job somewhere that generates a (non sequential) list of primes and you only select one out of that list if you need one. If the question was just about optimizing, my comment is of course complete bs. I just wanted to show a different perspective on the question. – Ocaso Protal Apr 12 '11 at 12:05

7 Answers7

6

First things first: Don't use math.pow(), as it is just a wrapper for the C floating-point function, and your numbers are WAY too big to be accurately represented as floats. Use Python's exponentiation operator, which is **.

Second: If you are on a platform which has a version of gmpy, use that for your primality testing.

Third: As eumiro notes, you might be dealing with too big of a problem space for there to be any truly fast solution.

John Y
  • 14,123
  • 2
  • 48
  • 72
4

Take a look at Miller-Rabin test I am sure you will find some implementations in Python on the internet.

ba__friend
  • 5,783
  • 2
  • 27
  • 20
4

As explained in the comments, you can forget about building a list of all primes between 10^300 and 10^301 and picking one randomly - there's orders of magnitudes too many primes in that range for that to work.

The only practical approach, as far as I can see, is to randomly pick a number from the range, then test if it is prime. Repeat until you find a prime.

For the primality testing, that's a whole subject by itself (libraries [in the book sense] have been written about it). Basically you first do a few quick tests to discard numbers that are obviously not prime, then you bring out the big guns and use one of the common primality tests (Miller-Rabin (iterated), AKS, ...). I don't know enough to recommend one, but that's really a topic for research-level maths, so you should probably head over to https://math.stackexchange.com/ .

See e.g. this question for a starting point and some simple recipes:

How do you determine if a number is prime or composite?

About your code:

The code you post basically does just what I described, however it uses an extremely naive primality test (trial division by all numbers 1...sqrt(n)). That's why it's so slow. If you use a better primatlity test, it will be orders of magnitude faster.

Community
  • 1
  • 1
sleske
  • 81,358
  • 34
  • 189
  • 227
4

If you need something quick and dirty simply use Fermat's little theorem.

def isPrime(p):
    if(p==2): return True
    if(not(p&1)): return False
    return pow(2,p-1,p)==1

Although this works quite well for random numbers this will fail for numbers know as "pseudoprimes". (quite scarce) But If you need something foolproof and simple enough to implement I'd suggest you read up about Miller Rabin's Primality Test.

PS: pow(a,b,c) takes O(log(b)) time in python.

jack_carver
  • 1,510
  • 2
  • 13
  • 28
  • Pseudoprimes of base two (which your code would incorrectly report as prime) are not *that* rare. There are 7 of them among the integers up to 2000. So this test will probably not be sufficient if you really need a prime. – sleske Apr 12 '11 at 22:24
  • This may be quick and dirty, but my testing of it shows it's actually quite fast. – beruic May 17 '13 at 09:55
2

Since you are handling extremely large numbers, you should really build on what clever people already did for you. Given that you need to know for sure your number is a prime (Miller Rabin is out), and you do want a random prime (not of a specific structure), I would suggest AKS. I am not sure how to optimize your numbers under test, but just choosing a random number might be okay given the speed of the primality test.

netrus
  • 153
  • 1
  • 9
  • 1
    Why is Miller-Rabin out? You can just repeat the test often enough to get a ridiculously low probability of error (that's what most production-quality crypto software does, I believe). Of course, AKS might work as well. No idea what's faster in practice. – sleske Apr 12 '11 at 10:33
1

If you want to generate a large number of primes, or generate them quickly, pure python may not be the way to go - one option would be to use a python openssl wrapper, and use openssl's facility for generating RSA private keys (which are in fact a pair of primes), or some of openssl's other primality-related functions. Another way to acheive speed would be a C extension implementing one of the tests below...

If opessl isn't an option, your two choices (as many of the comments have mentioned) are the Miller-Rabin test and the AKS test. The main differences - AKS is deterministic, and is guaranteed to give no false results; whereas Miller-Rabin is probabalistic, it may occasionally give false positives - but the longer you run it, the lower that probability becomes (the odds are 1/4**k for k rounds of testing). You would think AKS would obviously be the way to go, except that it's much slower - O(log(n)**12) compared to Miller-Rabin's O(k*log(n)**3). (For comparison, the scan test you presented will take O(n**.5), so either of these will be much faster for large numbers).

If it would be useful, I can paste in a Miller-Rabin implementation I have, but it's rather long.

Eli Collins
  • 8,375
  • 2
  • 34
  • 38
0

It is probably better to use a different algorithm, but you could optimise this code pretty easily as well.

This function will be twice as fast:

def is_prime(n):
    import math
    n = abs(n)
    if n % 2 == 0:
        return False
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            return False
        i += 2

    return True
gnur
  • 4,671
  • 2
  • 20
  • 33
  • @eumiro, I think going twice as fast still helps. If I could make any script I run twice as fast with just 3 added/changed lines I would be a very happy man. – gnur Apr 12 '11 at 09:14
  • 3
    Yes, usually that's true. However, eurmiro was pointing out that twice as fast does not help you if your expected running time is longer than the expected time until the heat death of the universe... – sleske Apr 12 '11 at 10:34