## Other

drummers-lowrise

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Caravaggio

Joined: 15 May 11
Posts: 656
ID: 98704
Credit: 42,707,395
RAC: 0

Message 37674 - Posted: 30 Jun 2011 | 1:15:40 UTC

OK, ok, I'm exposing my ignorance. When a wu is complete, and is not a prime, it often refers to the Residue = XXXaXXXXXabcXd etc. What is the Residue?

If anyone can explain residue, say, in terms of beer or pizza, it would be appreciated.

Thanks,

C

Mark Doom

Joined: 21 Jan 11
Posts: 629
ID: 82310
Credit: 132,563,921
RAC: 0

Message 37677 - Posted: 30 Jun 2011 | 3:13:09 UTC - in response to Message 37674.

Not sure..but I've been leaving a lot of residue behind at this party..

Iain Bethune
Honorary cruncher

Joined: 28 Jan 09
Posts: 1588
ID: 34775
Credit: 194,056,043
RAC: 0

Message 37679 - Posted: 30 Jun 2011 | 7:55:28 UTC - in response to Message 37677.

Explanation follows (skip to the third paragraph if you want to know the beer analogy)

When you do an LLR test you start with some small initial number then repeatedly square it and subtract 2 for (n-2) iterations (where n is the n in k*2^n - 1) - this is the iteration counter you see when you running a test on PRPNet.

Clearly the numbers involved get pretty big (even though you do all the arithmetic modulo the prime number you are testing). So, when you get to the end of the iterations, you look at the number you have left - if it is zero, then you have found a prime, if not, then you have a composite, and a large non-zero number. What the residue is is just the lowest 64 bits of the big number - enough that if two computers do the test and come up with the same residue then we can be sure they have done a correct calculation to very high level of confidence.

In terms of beer, you could think of the residue as being a small sample taken from a large tank at the end of the brewing process - it would be impractical to sample the entire tank before bottling and distributing it. Just by looking at a small sample, we can be fairly sure about the rest...

See wikipedia for a full description of the LLR test: http://en.wikipedia.org/wiki/Lucasâ€“Lehmerâ€“Riesel_test

Cheers

- Iain

____________
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!

Caravaggio

Joined: 15 May 11
Posts: 656
ID: 98704
Credit: 42,707,395
RAC: 0

Message 37682 - Posted: 30 Jun 2011 | 9:25:44 UTC - in response to Message 37679.

Iain, you are my hero! (for the day.) That was lucid and concise. Though it wasn't necessary, I appreciate the beer analogy and thank you for the effort.

-C

Gary Craig
Volunteer tester

Joined: 30 Dec 09
Posts: 3213
ID: 52890
Credit: 1,005,618,748
RAC: 0

Message 37759 - Posted: 1 Jul 2011 | 7:47:24 UTC - in response to Message 37682.

Iain, you are my hero! (for the day.) That was lucid and concise. Though it wasn't necessary, I appreciate the beer analogy and thank you for the effort.

-C

I like beer analogies.

It occurs to me that I could have omitted the word "analogies" from that sentence and it would still be grammatically correct and even more true.

--Gary