mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2008-09-17, 21:51   #1
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default 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
Primeinator is offline   Reply With Quote
Old 2008-09-17, 21:58   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AB16 Posts
Default

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.
Mini-Geek is offline   Reply With Quote
Old 2008-09-17, 23:15   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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.
cheesehead is offline   Reply With Quote
Old 2008-09-17, 23:43   #4
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3·5·61 Posts
Default

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?
Primeinator is offline   Reply With Quote
Old 2008-09-18, 00:04   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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.
Mini-Geek is offline   Reply With Quote
Old 2008-09-18, 00:31   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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
cheesehead is offline   Reply With Quote
Old 2008-09-18, 01:13   #7
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts
Default

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.
Primeinator is offline   Reply With Quote
Old 2008-09-18, 01:24   #8
jrk
 
jrk's Avatar
 
May 2008

21078 Posts
Default

It is the last 64 bits of the remainder.

So it is the remainder modulo 2^64.
jrk is offline   Reply With Quote
Old 2008-09-18, 01:26   #9
jrk
 
jrk's Avatar
 
May 2008

21078 Posts
Default

Quote:
Originally Posted by Primeinator View Post
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
jrk is offline   Reply With Quote
Old 2008-09-18, 02:52   #10
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M52..

3×5×61 Posts
Default

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.
Primeinator is offline   Reply With Quote
Old 2008-09-18, 09:25   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×7×223 Posts
Default

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


Quote:
Originally Posted by Primeinator View Post
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
ATH is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
residues and non residues of general quadratic congruences smslca Math 0 2012-10-12 06:42
Compare interim files with different start shifts? zanmato Software 12 2012-04-18 14:56
RES64: PRP vs. LLR Cruelty Software 2 2007-08-13 14:48
Saving interim residues of huge P-1? Andi47 GMP-ECM 12 2006-06-18 13:08
Interim iterations in status.txt are not random 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

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.