mersenneforum.org > Math Curiosity
 Register FAQ Search Today's Posts Mark Forums Read

 2004-02-10, 17:21 #1 ET_ Banned     "Luigi" Aug 2002 Team Italia 484510 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. 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
2004-02-10, 20:12   #2
wblipp

"William"
May 2003
New Haven

94316 Posts

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.

2004-02-11, 08:04   #3
ET_
Banned

"Luigi"
Aug 2002
Team Italia

12ED16 Posts

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

2004-02-12, 00:52   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

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.

2004-02-12, 14:00   #5
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111011012 Posts

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

2004-02-12, 14:41   #6
wblipp

"William"
May 2003
New Haven

237110 Posts

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}

2004-02-12, 15:10   #7
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111011012 Posts

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

 2004-02-13, 17:36 #8 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 1E0C16 Posts 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. :-)

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Aliquot Sequences 2 2016-01-17 07:44 Gordon PrimeNet 1 2015-07-30 06:49 petrw1 Math 4 2015-07-19 02:33 R.D. Silverman GMP-ECM 4 2012-05-10 20:00 JuanTutors Math 3 2004-10-20 04:37

All times are UTC. The time now is 19:17.

Fri Jul 1 19:17:36 UTC 2022 up 78 days, 17:18, 0 users, load averages: 2.36, 2.76, 2.57