Interim and Res64 Residues

[Primeinator]

Can anyone point me to a source to help understand what the Interim Residues and Res64 residues actually mean or indicate? (i.e., the difference between the letters, numbers, etc). Thanks.

[Mini-Geek]

The letters and numbers are hexadecimal (base 16), which is represented with 0-F. I think the res64/interim residues is the last 64 bits of the residue encoded in hexadecimal, but I'm not sure on this.

[cheesehead]

Originally Posted by Primeinator

Can anyone point me to a source to help understand what the Interim Residues and Res64 residues actually mean or indicate? (i.e., the difference between the letters, numbers, etc). Thanks.

Mini-Geek is correct.

In the Lucas-Lehmer test's series of iterations, the result value of the final iteration (which is zero only if the number being tested is prime) is called the residue.

An "interim residue" is the value computed at some iteration before the last one.

Because these residues can be millions of bits long, it has been traditional to save only the last (right-most, low-order) few bits of it for later comparison. A "Res64 residue" means the last 64 bits of a (full) residue value.

In the "old days", some saved residues were only the final 15 bits.

For an explanation of hexadecimal notation, see the Wikipedia article at http://en.wikipedia.org/wiki/Hexadecimal.

[Primeinator]

For an explanation of hexadecimal notation, see the Wikipedia article at http://en.wikipedia.org/wiki/Hexadecimal.

Thank you. That clears up what each character represents. Now my question is this (as the above Wiki article did not clarify this well): What does a string of these characters mean? It was all well and good to know that A means 10 or F equals 15 or 7 equals 7. However what does AA02FIF8BCFB0F1C mean and how could you so easily spot "fake" residues seen in the posts relating to M45 and M46?

[Mini-Geek]

Originally Posted by Primeinator

Thank you. That clears up what each character represents. Now my question is this (as the above Wiki article did not clarify this well): What does a string of these characters mean? It was all well and good to know that A means 10 or F equals 15 or 7 equals 7. However what does AA02FIF8BCFB0F1C mean and how could you so easily spot "fake" residues seen in the posts relating to M45 and M46?

The string of characters is the same as how you might say in decimal 43112609 to mean 4*10^7 + ... + 9*10^0, except you might say something like AA02FF8BCFB0F1C (BTW "I" isn't a possible hex value, as hex consists only of 0-9 and A-F) for (all in base 16 BTW where "10" means 16 in decimal) A*10^E + ... + C*10^0.

The fake residue is so easily spotted because the way to generate it is known, and becomes pretty easy to see when you look at the binary of the residue. See http://www.mersenneforum.org/showpos...9&postcount=25 for more information, which can be summed up in that certain parts of the exponent are taken in binary and used as certain parts of the fake residue.

In case you're wondering why hex is used here for the last 64 bits instead of binary, it's because hex can use a fourth the space that binary does to show the same thing, while still showing a close connection to the binary digits.

[cheesehead]

Originally Posted by Primeinator

Now my question is this (as the above Wiki article did not clarify this well):

Hmmm ... you're right. Although it says "base-16" and "numeral system with a radix, or base, of 16" right up at the top, it therafter assumes the reader knows all that "base" implies. There seems to be no explanatory (not just bare numbers) example of decimal-to-hexadecimal or hexadecimal-to-decimal translation, and not until the "Binary translation" section does it explain a binary-to-hexadecimal translation.

The subsection "Division-remainder in source base" under "Converting from other bases" gives an algorithm that is correct as far as I can tell, but no explicitly-worked-out example (tsk, tsk). Then, in the next subsection, "Addition and multiplication" under "Converting from other bases", is, at last, an _explanatory_ conversion of hexadecimal B3AD to decimal 45997. Hard to find, under a misleading subheading, and no demonstration of decimal-to-hexadecimal conversion!

- - -

Here may be a better explanation:

"How to convert between decimal and hexadecimal numbers" at http://www.ehow.com/how_2264926_conv...l-numbers.html

(Ignore the in-joke "Oct 31 = Dec 25".)

[Primeinator]

Alright, then I understand how to get the decimal representation of the hexadecimal residue. Now, is that decimal remainder the remainder of the modulo arithmatic in the Lucas Lehmer test?

The fake residue is so easily spotted because the way to generate it is known, and becomes pretty easy to see when you look at the binary of the residue. See http://www.mersenneforum.org/showpos...9&postcount=25 for more information, which can be summed up in that certain parts of the exponent are taken in binary and used as certain parts of the fake residue.

[jrk]

It is the last 64 bits of the remainder.

So it is the remainder modulo 2^64.

[jrk]

Originally Posted by Primeinator

It means the residues on those exponents are made-up, not the actual residue from completing the test (this is a way to mask the new prime from being widely known before it is verified).

[Primeinator]

It is the last 64 bits of the remainder.

So it is the remainder modulo 2^64.

Ahh, the lightbulb.

It means the residues on those exponents are made-up, not the actual residue from completing the test (this is a way to mask the new prime from being widely known before it is verified).

This part I understand, but what "makes" one bit of hexadecimal look suspicious over another? I tried the link, but it does not work.

[ATH]

Here is a more detailed explaination of the fake residue algorithm: residue.txt

Originally Posted by Primeinator

This part I understand, but what "makes" one bit of hexadecimal look suspicious over another? I tried the link, but it does not work.

Since it involves the exponent mod 16 and since a prime number can only be 1,3,5,7,9,11,13,15 mod 16 the fake residue will always start with one of these possibilities:

0x1248, 0x36C8, 0x5A48, 0x7EC8, 0x9248, 0xB6C8, 0xDA48, 0xFEC8

Looking at the fake residues used there are many common sequences which make them look "suspicious", like 7EC801, C8012, 8013 and so on.

real M39: 13466917 0x5A4800136C936D__
real M40: 20996011 0xB6C80125A48000__
real M41: 24036583 0x7EC80125B6DB7E__
real M42: 25964951 0x7EC80136C8136C__
real M43: 30402457 0x92480137EC937F__
fake M44:29225803 0xB6C80136DB7FED__
fake M45:20314069 0x5A480124936DA5__
fake M45:43021553 0x1248125A492480__
fake M46:32428427 0xB6C80137FEDB7E__