20040210, 17:21  #1 
Banned
"Luigi"
Aug 2002
Team Italia
11240_{8} Posts 
Curiosity
I was surfing the link http://www.utm.edu/research/primes/n...casLehmer.html
and noticed this sentence: Code:
Lucas showed that S127 is divisible by M127 thus showing that M127 is prime. This was a extremely difficult calculation since M127 is a big number and S127 is unbelievably large. In fact M127 = 170141183460469231731687303715884105727 and Lucas was only able to perform the calculation since he showed that S127 is divisible by M127 without calculating S127. Luigi Last fiddled with by ET_ on 20040210 at 17:21 
20040210, 20:12  #2  
"William"
May 2003
New Haven
4444_{8} Posts 
Quote:


20040211, 08:04  #3  
Banned
"Luigi"
Aug 2002
Team Italia
2^{5}×149 Posts 
Quote:
S_{127} = (S_{126} * S_{126}  2) mod M_{127} To come back to the sentences "Lucas was only able to perform the calculation since he showed that S127 is divisible by M127 without calculating S127" and "S127 is unbelievably large": S127 has about the same size of S126 or (at most) the square of M127, and Lucas had to compute at least S126. So, what's the point of claiming that he didn't have to calculate S127? To me, that sentence is confusing Luigi 

20040212, 00:52  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
7188_{10} Posts 
Quote:
Quote:
Quote:
M_{i} = 2^{i}  1 M_{i+1} = 2^{i+1}  1 = (2^{i}  1)*2 + 1 = M_{i}*2 + 1 So (ignoring the 1 and +1 terms which become insignificant compared to the M_{i} for large i) each M_{i} is twice the value of, and thus has one more binary digit than, M_{i1}. If we don't do any modulo operation, S_{i+1} = S_{i} * S_{i}  2 Ignoring the 2, which becomes insignificant for large i, each S_{i} is the square of, and thus has twice as many binary digits as, S_{i1}. The size of S_{i} doubles with each step, whereas the size of M_{i} only increases by one digit each step. So the size of M_{i} is approximately 2^i, but the size of S_{i} is approximately to 2^(2^{i}), which becomes much, much larger than 2^{i}. 

20040212, 14:00  #5  
Banned
"Luigi"
Aug 2002
Team Italia
11240_{8} Posts 
Quote:
Anyway, the question was on semantical use of "without computing S_{127}": You actually HAVE TO compute it to mod it. The fact that S_{127} during last mod operation IS NOT as long as it could be if no mod operation (since the start of the algorithm) was performed, is ininfluent: S_{127} is created during last step of the test, so it must be computed; it is the complete sequence of S_{n} that is not completely computed because of mods. Well, I guess I'll have some now... Luigi 

20040212, 14:41  #6  
"William"
May 2003
New Haven
2^{2}·3^{2}·5·13 Posts 
Quote:
S(1) = 4 and S(k+1) = S(k)^{2}2 Note there is NO "mod" in the definition. Following the proof , it's clear that the definition of S cannot include the mod function. The implementation uses the mod function at each stage, so there are probably pages somewhere on the web that sloppily define the calculation with the mod at each stage. But that should really be stated as the caculation at each stage of the modular result {S(k) mod M127} using the relationship {S(k+1) mod M127} = {S(k)^{2}2 mod M127} 

20040212, 15:10  #7  
Banned
"Luigi"
Aug 2002
Team Italia
2^{5}·149 Posts 
Quote:
The proof has no mod, the implementation has (or something like it). I finally got it. (Yeah, whatever...) Forgive me for being somewhat pushy, and for my misuse of capital letters. Luigi 

20040213, 17:36  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·599 Posts 
Luigi,
I think I can speak for many others as well as myself: we admire and cherish your curiosity and somewhatpushiness (for which you need not apologize), and Barely Notice Your Capital Letters. :) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A meaningless curiosity  fivemack  Aliquot Sequences  2  20160117 07:44 
Results Curiosity  Gordon  PrimeNet  1  20150730 06:49 
I see this as a bit of a mathematical curiosity...  petrw1  Math  4  20150719 02:33 
A Curiosity  R.D. Silverman  GMPECM  4  20120510 20:00 
P1 question of curiosity  JuanTutors  Math  3  20041020 04:37 