Type of work I'm doing

[Mr. P-1]

Originally Posted by LaurV

That method you describe is far too inefficient. LL test is a more efficient method. Comparing the "school method" you describe, with LL test, is even worse then comparing a snail with a supersonic airplane. We are talking about the same speed proportion, except that in the case of LL versus "school method", you have to add few thousand zeroes at the end of the speed number, in the favor of LL tests...

Several million more like.

Note to the original author: We are not saying that an LL test is several million times faster than trial division as a method of primality testing. That would be adding just 6-7 zeros at the end of the speed number.

If it was several billion times faster, that would be adding 9-10 zeros. Several trillion times faster would add 12-13 zeros.

Instead of using a single computer, we could distribute the task across many. Suppose every atom in the universe is a computer. Some estimates put that number at about 10⁸⁰ That would add about 80 zeros to the speed factor.

The LL test is much faster than that. Words cannot express how much faster adding several million zeros to the speed number is. The human mind cannot picture it.

Now turn that around. If an LL test takes three weeks, think how long it would take to prove our numbers prime using TF alone.

[Mr. P-1]

Originally Posted by LaurV

The only work type which is affected by the memory amount is the "stage 2 of P-1/ECM", which you don't normally do if you do "first tests" or "world records", etc.

Acually there is quite a high chance that a newly assigned first time test will need P-1 pretesting.

Even for that, not the speed is affected, but the chance to find a factor (i.e. more memory increases the chance).

I don't think that's correct, even in practice.

What actually happens is, unless the client has sufficient memory to make using the Brent-Suyama extension worthwhile (multi-gigabytes on numbers in the current test range), more memory increases the speed at which the client is able to complete stage 2 to particular limits. However, the client takes this into account when computing those limits, preferring to increase the limits (thereby increasing the chance of finding a factor) in exchange for spending more time, when the memory allocation is generous.

I could so happen, I suppose, that the effect of this is to exactly cancel out the time saving, but I don't think it does, and I can think of no reason why it should.

[Mr. P-1]

Originally Posted by Unregistered

Ah, I see. But I don't understand it. If a number is a composite, then you find that out be finding the smallest divisor.

Actually it is the other way around. If we find a factor (it doesn't matter whether or not it is the smallest), then the number is composite.

If we don't find a factor, then we need to use another method to determine whether the number is prime or composite. That method is the LL test.

If it's a prime, you have to test all the possible divisors? Or is the LL-algorithm different from this?

Totally different.

The LL algorithm itself is quite simple:

1. Start with the number 4.
2. Square it and subtract 2.
3. Repeat step 2 p-2 times, where p is the exponent you are testing.
4. If the result is divisible by Mp then Mp is prime. If not then Mp is composite.

What makes this feasible (i.e., millions of zeros faster than TF) is that it requires only about p operations, while TF would require about 2^p operations.

The algorithm is simple enough that any high-school programmer could implement it. (In fact, one did). Implementing it efficiently is another matter, as is understanding why the algorithm works in the first place. A good explanation can be found here, though you will need a certain level of mathematical sophistication to be able to understand it.

Thats weird, I didnt think my machine was old or slow in this context. Yeah, about 3 weeks according to the schedule to complete LL on a world record number. But the TF did go much faster than what the schedule said.

That's because TF has only a small chance of finding a factor Obviously it would be a waste of time to spend weeks and weeks trying to find a factor which might be successful, when an LL test will definitely decide the matter. Factoring is like playing roulette. We "bet" a small amount of compute time that we will find a factor. If we win, we save two lengthy LL tests. Most of the time we lose, but we only lose the compute time we steaked.

Of course we only do this as long as the odds are in our favour. Over millions of tests, the project comes out ahead. Roulette isn't really a gample for the casino, is it?

The Prime95 says that the chance of finding a world record prime, running 4 threads, were about 1:115,000. And also that it will take about 3 weeks to complete this.

It seems unvalid to me, but if it actually is true, then the chances are better than in the "lottery" that we have here, which are about 1:5,000,000. Hehe.

That calculation is based upon an unproven conjecture about the distribution of primes among the Mersenne numbers.

[TheMawn]

If you were to give a person just enough information about what a prime number is, and asked them to tell you how they would determine the primality of a number, they would probably give you the most naive way that exists. Dividing a number k by every number up to k and seeing if one of them returns a whole number.

Next, one might realize that you don't need to divide a number by, for example, 4. If a division by 4 gives a whole number, then so does a division by 2. A much better way is to divide by every prime number up to k. Next, a person might notice that if, for example, you were to divide the number 173 by 17, you would get a smaller than 17 because 17 x 17 is 289. You don't even need to try 17 because if it DID give you a whole number, it would be smaller than 17 and you already tried all the ones smaller than 17! You can then eliminate all the prime numbers equal to or larger than the square root of k.

We've gone from trying all numbers up to k to trying all the prime numbers up to the square root of k. This is essentially what trial factoring is. It's a very brute force kind of method.

My video card, a GTX 670, can factor 2^60892163-1 to 2⁷⁴ in about 5 hours. That is checking every single prime number up to roughly 18 sextillion. It takes about twice as much time to check every factor between 2^x and 2^x+1 as it does 2^x-1 and 2^x. So, going up to 2⁷⁵ would take another 5 hours. 2⁷⁶ would take 10 hours.

Assuming the trend continues, the time it takes to trial factor is O(2ⁿ). To check 2^60892163, you would need to go up to 2^30446082 which is 2^30446008 times longer than 10 hours.

It would take my video card around 2^30446011 hours to do that. The universe is about 2⁴⁷ hours old.

[TheMawn]

It would take my video card around 2^30446011 hours to [try every prime factor for M60892163]. The universe is about 2⁴⁷ hours old.

I want to say this in it's own post since people might not read the whole thing I posted just previous to this.

[chalsall]

Originally Posted by Mr. P-1

Acually there is quite a high chance that a newly assigned first time test will need P-1 pretesting.

I disagree on this point.

While a few hundred first time LL tests were assigned without P-1 pre-done after the last Mersenne Prime was announced, we're back to the point where all LL tests are assigned with P-1 already done.

[LaurV]

Originally Posted by Mr. P-1

I could so happen, I suppose, that the effect of this is to exactly cancel out the time saving, but I don't think it does, and I can think of no reason why it should.

I (also) disagree on this (different) point. I however, may be wrong. OTOH, the explanation you give in your last paragraph is quite right (about how the things happen). We only disagree on duration and the reason is explained below.

If you read the link I provided above, about how GIMPS intelligently chooses the B1 and B2 limit, you will see that the story is "time related". If you spend the time T to do LL test, then maybe you can save two times T if you find a factor. So, how long time (x% of T) should you spend doing TF and P-1? It depends of the chance to find a factor.

If you have a method with a higher chance to find a factor, it makes sense to chase that method longer (in time). So, logically, it is viceversa than one should expect. But you can't chase that chance too long, as your odds improve only logarithmically, reported to the time you spend doing it (P-1, in our case). So, in case a factor is not found, you lost precious time, which would have been better invested in doing LL from the start. Therefore there is a "cutoff" somewhere, and that cutoff (B1 and B2) have to be intelligently chosen, to maximize the chance of finding a factor in a limited time (x% of T), but the time is still the limit. So, at the end, the time variation is tiny. Adding more memory to the stage 2, you will work about the same time on that P-1 assignment, but you might get luckier.