Curiosity

[ET_]

I was surfing the link http://www.utm.edu/research/primes/n...casLehmer.html

and noticed this sentence:

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

[wblipp]

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.

[ET_]

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

S₁₂₇ = (S₁₂₆ * S₁₂₆ - 2) mod M₁₂₇

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

[cheesehead]

Originally Posted by ET_

S127 comes from

S₁₂₇ = (S₁₂₆ * S₁₂₆ - 2) mod M₁₂₇

Note that if the mod were not performed, S₁₂₇ would be approximately the square of S₁₂₆, and thus would have twice the number of digits that S₁₂₆ has.

"S127 is unbelievably large"

This refers to the value computed without any modulo operation. If the S_i are not reduced at each step by a modulo operation, then S₁₂₇ would have about 2¹²⁷ (more than 10,000,000,000,000,000,000,000,000,000,000,000,000) binary digits. For comparison, M₁₂₇ has only 127 binary digits.

S127 has about the same size of S126 or (at most) the square of M127

Look at what happens in going from S_i to S_i+1, compared to what happens when going from M_i to M_i+1:

M_i = 2ⁱ - 1
M_i+1 = 2ⁱ⁺¹ - 1 = (2ⁱ - 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_i-1.

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_i-1.

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ⁱ), which becomes much, much larger than 2ⁱ.

[ET_]

Originally Posted by cheesehead

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ⁱ), which becomes much, much larger than 2ⁱ.

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 S₁₂₇": You actually HAVE TO compute it to mod it. The fact that S₁₂₇ 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₁₂₇ 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

[wblipp]

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

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 mod M127}

[ET_]

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

[cheesehead]

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