Register to reply 
Practical pseudoprimality testing 
Share this thread: 
#1
Dec105, 10:24 PM

Sci Advisor
HW Helper
P: 3,682

I'm working on a problem that includes testing large numbers for primality. I'm using Pari/GP's builtin BailliePSW pseudoprimality test, but it (understandably!) runs slowly.
I have some qustions, then: * I've been sieving the small prime factors from these numbers. For numbers if the size I'm working with (3300 to 3500 decimal digits), how far should I sieve? I've been checking up to a million, but should I go higher? As it is, I haven't been catching much this way (perhaps 1 in 10), since the numbers are fairly rough (similar to primorial primes). How much effort should I invest in this stage? * Are there better tests for what I'm doing? If it means anything, I expect "most" (~99.5%) of the numbers to be composite. I would think the p1 and perhaps p+1 tests would be useful, but are they fast enough if I know the relevant quantity is 'very smooth'? * Are there other things I should be aware of when working with numbers of this magnitude? 


#2
Dec105, 10:46 PM

Emeritus
Sci Advisor
PF Gold
P: 16,091

What you need to do is to get a reasonable estimate of how much work it takes to sieve vs how long it takes to run the rest of your algorithm on what survives. If you do this with smaller values, you should be able to get a good model which you can extrapolate to the problem size of interest. Once you have a good model, you can simply find the parameters which yield the best running time. If a probabilistic algorithm is sufficient for your purposes, they both seem to advocate the RabinMiller strong pseudoprime test. I'm not familiar with "Pari", "GP", or "BalliePSW" at all, so I can't say anything about that. Um... I suppose you could also try out various large number packages, and try to find the one that seems to perform the best  it's possible that some packages are much better than others for this type of thing. Besides, they probably even come with welloptimized primality proving functions! 


#3
Dec105, 11:03 PM

P: 16

You might take a look at the source code available from GIMPS. They've been searching for the world's largest primes for years now and their code has been tweaked for efficiency.



#4
Dec105, 11:09 PM

Sci Advisor
HW Helper
P: 3,682

Practical pseudoprimality testing
http://pari.math.ubordeaux.fr/ 


#5
Dec105, 11:13 PM

Sci Advisor
HW Helper
P: 3,682




Register to reply 
Related Discussions  
Practical Uses for Lasers...  Electrical Engineering  11  
A practical reaction?  Chemistry  4  
Practical help  Introductory Physics Homework  7  
Practical questions  Beyond the Standard Model  3  
Help! Lab practical!  Materials & Chemical Engineering  0 