mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Closed Thread
 
Thread Tools
Old 2004-01-21, 10:41   #1
Unregistered
 

22·1,597 Posts
Default How does this whole prime-testing thing work?

Hi,

I have seen that Prime95 is considerably faster than other prime programs (eg Primo) ut is that because prime95's algorithms would only work with a mersenne prime?

Cheers,
Chris
 
Old 2004-01-21, 17:39   #2
nomadicus
 
nomadicus's Avatar
 
Jan 2003
North Carolina

3668 Posts
Default

Yes. Prime95 evaluates primality for numbers in the form of (2^p)-1 were p is a prime number (and could but doesn't have to be a Mersenne prime). This special form and the fact that the assembly code pulls out all the stops is what makes it fast. Improvements are being made all the time and is quite a feat of research, coding, and testing.
This url http://www.mersenne.org/math.htm may be of further help.
nomadicus is offline  
Old 2004-07-16, 00:28   #3
imo
 
Jul 2004

3 Posts
Default How does this whole prime-testing thing work?

Hi. I started running Prime95 as I was inspired by the recent small article in new scientist about M41. I've been running seti@home for at least a couple of years, and thought this was something a little more concrete.

o) Can I just cut and paste the Prime95 folder to wherever I'd like it?

o) How can I be sure that the program is doing work of type 4 (10,000,000 plus digits? And that therefore I have a chance of my PC being the one to discover M42?

Thanks
imo is offline  
Old 2004-07-16, 01:20   #4
Primehack
 
Jul 2004

2 Posts
Default

Quote:
Originally Posted by imo
o) Can I just cut and paste the Prime95 folder to wherever I'd like it?
Yes, just be carefull to redirect the shortcuts (if you -or automatically the setup- created them).
Primehack is offline  
Old 2004-07-16, 02:07   #5
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by imo
o) How can I be sure that the program is doing work of type 4 (10,000,000 plus digits? And that therefore I have a chance of my PC being the one to discover M42?
First: M42 could have either 10,000,000 or more digits, or fewer than 10,000,000 digits. We won't know M42's length until we find it, and we have not yet tested all Mersenne numbers with fewer than 10 million digits. (In fact, we haven't yet completed testing of all Mersenne numbers smaller than M41, so the 42nd Mersenne prime to be discovered might be smaller than the 41st to be discovered. An out-of-order discovery has happened before.)

So you do not have to be testing a 10,000,000-plus-digit number in order to have a chance of finding M42.

In order for a Mersenne number 2N-1 to be at least 10,000,000 decimal digits long, the exponent N must be greater than 33219277. So if the number you're testing has an exponent greater than 33,219,277, then you are working on a number with at least 10 million decimal digits.

Last fiddled with by cheesehead on 2004-07-16 at 02:13
cheesehead is offline  
Old 2004-07-16, 02:31   #6
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

Another thought - The computer you use to test a 10,000,000+ digit number should probably be at least a p3 1 ghz. Anything less will take way too long to finish. A HT enabled P4 at 2 ghz or better is preferred. As a benchmark, a pIII 1.2 ghz machine will take about 7 months to complete a 10 million digit number where a P4 at 2.8 ghz will take about 3 or 4 weeks.

Once you have Prime95 open, click on "test" then "primenet". Make sure the box for "request 10,000,000 digit numbers" is checked and uncheck the other 3 boxes for double checking etc. This will restrict your machine to only do 10M numbers.

Fusion
Fusion_power is offline  
Old 2004-07-27, 13:49   #7
imo
 
Jul 2004

3 Posts
Default

Thanks very much for your responses. I was hoping to tell from Results.txt of the Prime95.exe display exactly what test I was doing. There must be explanations somewhere in the FAQ but I've missed them. Thanks anyway though, it's all very useful info.
imo is offline  
Old 2004-07-31, 14:28   #8
Bundu
 
Bundu's Avatar
 
Jul 2004
Mid Calder, Scotland

5×37 Posts
Default How does this whole prime-testing thing work?

Hi Guys,

Love the site and the concept of searching for Mersenne numbers!!!

I hope I'm not going over old ground so please go easy on me! I wanted to ask a two part question:-

I'm working on Prime95 and on one of my PCs I'm trying a 10,000,000+ number. Does the calculation stop as soon as Prime finds a factor?
If so, should I be excited that I've got to 27,000,000 without it stopping?

Thanks
Mark (Scotland)
Bundu is offline  
Old 2004-07-31, 14:51   #9
jfollas
 
Jul 2004

11102 Posts
Default

Common question... Depends what step you're on.

In the beginning, Prime95 tries to find small factors of the prime using several different methods. If a small factor is found, then Prime95 reports its findings and moves on to another exponent.

If no small factors are found, then you move on to the Lucas-Lehmer primality testing. This is an iterative process (where the results of one step seed the next step) and must run all the way to the end. If the result of the very last iteration is zero, then you found a prime Mersenne.

If you haven't guessed, the Lucas-Lehmer test takes a long time for very big numbers (weeks to months depending on the size of the number and the speed of your machine).
jfollas is offline  
Old 2004-07-31, 14:52   #10
dave_0273
 
dave_0273's Avatar
 
Oct 2003
Australia, Brisbane

1D616 Posts
Default

What you are doing now is actually a LL test. It actually doesn't look for factors. The LL test is a test that will tell us if it is prime or not. At the end of the test if it comes back that it is not prime, we will still not know any of its factors, we will just that know it is just not prime.

If we were to instead to try to fully factorise it, it would take thousands of years. That is why we do the LL test. It is the only way (that is known at the moment) that will give us a result in our lifetime.

However, before the number was given to you, someone would have done a little factoring on it. 10mil digit numbers are factored up to about 2^68 (?) before they are assigned for LL testing. If a factor is found, we know that it isn't prime and so we wouldn't bother doing an LL test on it.
dave_0273 is offline  
Old 2004-07-31, 14:53   #11
dave_0273
 
dave_0273's Avatar
 
Oct 2003
Australia, Brisbane

2×5×47 Posts
Default

Argh, jfollas posted while i was still typing mine. jfollas's is probably a better explanation than what mine is.
dave_0273 is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why have ECM testing for known non-prime Mersenne numbers? sd235 Information & Answers 12 2018-12-06 17:56
Code for testing a prime other than form 2^n-1 MercPrime Information & Answers 5 2013-05-12 22:03
Prime testing software suggestions please. ishkibibble Conjectures 'R Us 15 2013-03-14 08:41
disk died, prime work lost forever? where to put prime? on SSD or HDD? emily PrimeNet 3 2013-03-01 05:49
Primenet gave me a known prime for LL testing Mr. P-1 PrimeNet 3 2011-02-20 09:38

All times are UTC. The time now is 07:35.

Tue Mar 9 07:35:39 UTC 2021 up 96 days, 3:46, 0 users, load averages: 1.71, 1.40, 1.35

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.