mersenneforum.org Interim and Res64 Residues
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-17, 21:51 #1 Primeinator     "Kyle" Feb 2005 Somewhere near M52.. 3·5·61 Posts Interim and Res64 Residues 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. Last fiddled with by Primeinator on 2008-09-17 at 21:52
 2008-09-17, 21:58 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 10AB16 Posts 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.
2008-09-17, 23:15   #3

"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts

Quote:
 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.

2008-09-17, 23:43   #4
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts

Quote:
 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?

2008-09-18, 00:04   #5
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 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.

2008-09-18, 00:31   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 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".)

Last fiddled with by cheesehead on 2008-09-18 at 00:47

2008-09-18, 01:13   #7
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts

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?

Quote:
 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.

 2008-09-18, 01:24 #8 jrk     May 2008 21078 Posts It is the last 64 bits of the remainder. So it is the remainder modulo 2^64.
2008-09-18, 01:26   #9
jrk

May 2008

21078 Posts

Quote:
Originally Posted by Primeinator
Quote:
 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.
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).

Last fiddled with by jrk on 2008-09-18 at 01:27

2008-09-18, 02:52   #10
Primeinator

"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts

Quote:
 It is the last 64 bits of the remainder. So it is the remainder modulo 2^64.
Ahh, the lightbulb.

Quote:
 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.

2008-09-18, 09:25   #11
ATH
Einyen

Dec 2003
Denmark

2×7×223 Posts

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

Quote:
 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__

Last fiddled with by ATH on 2008-09-18 at 09:28

 Similar Threads Thread Thread Starter Forum Replies Last Post smslca Math 0 2012-10-12 06:42 zanmato Software 12 2012-04-18 14:56 Cruelty Software 2 2007-08-13 14:48 Andi47 GMP-ECM 12 2006-06-18 13:08 GP2 Data 2 2003-10-28 22:51

All times are UTC. The time now is 22:50.

Wed May 5 22:50:59 UTC 2021 up 27 days, 17:31, 0 users, load averages: 1.76, 1.56, 1.73