mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-02-10, 17:21   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112408 Posts
Default 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.
How could he show that without calculating S127 since he should calculate s127 mod M127?

Luigi

Last fiddled with by ET_ on 2004-02-10 at 17:21
ET_ is offline   Reply With Quote
Old 2004-02-10, 20:12   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44448 Posts
Default

Quote:
Originally Posted by ET_
How could he show that without calculating S127 since he should calculate s127 mod M127?
He doesn't need to know the full value of S127 in order to calculate S127 mod M127. He can calculate S1 mod M127, from which he can calculate S2 mod M127, from which he can calculate S3 mod M127 - etc. You never need numbers larger than the square of M127. Prime95 does the same thing, although the M numbers now have millions of digits.
wblipp is offline   Reply With Quote
Old 2004-02-11, 08:04   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by wblipp
You never need numbers larger than the square of M127. Prime95 does the same thing, although the M numbers now have millions of digits.
I don't know why I thought S127 to be equally long or shorter than M127 Ah, I got it. S127 comes from

S127 = (S126 * S126 - 2) mod M127

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
ET_ is offline   Reply With Quote
Old 2004-02-12, 00:52   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

718810 Posts
Default

Quote:
Originally Posted by ET_
S127 comes from

S127 = (S126 * S126 - 2) mod M127
Note that if the mod were not performed, S127 would be approximately the square of S126, and thus would have twice the number of digits that S126 has.

Quote:
"S127 is unbelievably large"
This refers to the value computed without any modulo operation. If the Si are not reduced at each step by a modulo operation, then S127 would have about 2127 (more than 10,000,000,000,000,000,000,000,000,000,000,000,000) binary digits. For comparison, M127 has only 127 binary digits.

Quote:
S127 has about the same size of S126 or (at most) the square of M127
Look at what happens in going from Si to Si+1, compared to what happens when going from Mi to Mi+1:

Mi = 2i - 1
Mi+1 = 2i+1 - 1 = (2i - 1)*2 + 1 = Mi*2 + 1

So (ignoring the -1 and +1 terms which become insignificant compared to the Mi for large i) each Mi is twice the value of, and thus has one more binary digit than, Mi-1.

If we don't do any modulo operation, Si+1 = Si * Si - 2

Ignoring the -2, which becomes insignificant for large i, each Si is the square of, and thus has twice as many binary digits as, Si-1.

The size of Si doubles with each step, whereas the size of Mi only increases by one digit each step. So the size of Mi is approximately 2^i, but the size of Si is approximately to 2^(2i), which becomes much, much larger than 2i.
cheesehead is offline   Reply With Quote
Old 2004-02-12, 14:00   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112408 Posts
Default

Quote:
Originally Posted by cheesehead
The size of Si doubles with each step, whereas the size of Mi only increases by one digit each step. So the size of Mi is approximately 2^i, but the size of Si is approximately to 2^(2i), which becomes much, much larger than 2i.
Thanks Cheesehead, I realized it the day after my posting when I worked a "bit" with the numbers.

Anyway, the question was on semantical use of "without computing S127": You actually HAVE TO compute it to mod it. The fact that S127 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: S127 is created during last step of the test, so it must be computed; it is the complete sequence of Sn that is not completely computed because of mods.

Well, I guess I'll have some now...

Luigi
ET_ is offline   Reply With Quote
Old 2004-02-12, 14:41   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by ET_
You actually HAVE TO compute it to mod it.
No, you have the S definition wrong. The DEFINITION of S is

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}
wblipp is offline   Reply With Quote
Old 2004-02-12, 15:10   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25·149 Posts
Default

Quote:
Originally Posted by wblipp
No, you have the S definition wrong.
Yup.

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
ET_ is offline   Reply With Quote
Old 2004-02-13, 17:36   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Luigi,

I think I can speak for many others as well as myself: we admire and cherish your curiosity and somewhat-pushiness (for which you need not apologize), and Barely Notice Your Capital Letters. :-)
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A meaningless curiosity fivemack Aliquot Sequences 2 2016-01-17 07:44
Results Curiosity Gordon PrimeNet 1 2015-07-30 06:49
I see this as a bit of a mathematical curiosity... petrw1 Math 4 2015-07-19 02:33
A Curiosity R.D. Silverman GMP-ECM 4 2012-05-10 20:00
P-1 question of curiosity JuanTutors Math 3 2004-10-20 04:37

All times are UTC. The time now is 06:33.

Tue Oct 20 06:33:58 UTC 2020 up 40 days, 3:44, 0 users, load averages: 1.46, 1.81, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.