a backwards approach to Mersenne testing
 

[url]http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Proof_of_correctness[/url]
[QUOTE]Define [TEX]\omega = 2 + \sqrt{3}[/TEX] and [TEX]\bar{\omega} = 2 - \sqrt{3}[/TEX]; then we can verify by induction that [TEX]s_i = \omega^{2^i} + \bar{\omega}^{2^i}[/TEX] for all [I]i[/I].[/QUOTE]
And as a reminder, [I]M[SUB]p[/SUB][/I] is prime iff
[TEX]s_{p-2}\equiv0\pmod{M_p}.[/TEX]
So, here's my question: Just how hard would it be to calculate [TEX]\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} \pmod{M_p}[/TEX]? I'm guessing it's a good deal harder than the LL test, (because if not, we wouldn't be using the LL test!) but just what difficulties are involved if you use the best algorithms for the exponentiations? (e.g. would it require an impractical amount of memory? Would it take an impossible amount of time? Both?)

Before the guru's weigh in, isn't the lack of a finite representation for square root of three also a problem in the computation?

I think that's a relatively practical test of primality; if properly optimized it should be possible with less than four times the work of the LL test and not much more than twice the memory.

[QUOTE=only_human;236377]Before the guru's weigh in, isn't the lack of a finite representation for square root of three also a problem in the computation?[/QUOTE]

No, you'll keep it in symbolic form.

[QUOTE=CRGreathouse;236389]I think that's a relatively practical test of primality; if properly optimized it should be possible with less than four times the work of the LL test and not much more than twice the memory.[/QUOTE]

?? less than 4 times the work ?? Where did this come from?

[QUOTE=CRGreathouse;236389]I think that's a relatively practical test of primality; if properly optimized it should be possible with less than four times the work of the LL test and not much more than twice the memory.[/QUOTE]

Very interesting! Do they scale at about the same speed or does one become better for very large, or very small numbers? Perhaps in the future, when LL tests need billions or trillions of iterations, it'd be better?

[QUOTE=CRGreathouse;236391]No, you'll keep it in symbolic form.[/QUOTE]

Admission: I have not looked at this.

However, I [i]suspect[/i] that most terms in the
expansion of (2 - sqrt(3))^k will not vanish mod M_p and the number
of terms will grow exponentially as the algorithm progresses.

[QUOTE=R.D. Silverman;236439]Admission: I have not looked at this.

However, I [i]suspect[/i] that most terms in the
expansion of (2 - sqrt(3))^k will not vanish mod M_p and the number
of terms will grow exponentially as the algorithm progresses.[/QUOTE]

Can't we just work under Q[sqrt(3)] ?

[QUOTE=Mini-Geek;236434]Very interesting! Do they scale at about the same speed or does one become better for very large, or very small numbers? Perhaps in the future, when LL tests need billions or trillions of iterations, it'd be better?[/QUOTE]

I haven't looked at it in detail, but my impression is that they would scale at the same rate -- just with a ~300% performance penalty.

[QUOTE=axn;236442]Can't we just work under Q[sqrt(3)] ?[/QUOTE]

Perhaps.

Let K = Q[sqrt(3)] and let O_K be its ring of integers.

We would actually work over the quotient ring O_K/M_p.

I can't see how this would be faster; I'm not sure how to adapt it
so that one could perform weighted discrete convolutions as we do
with L-L.

[QUOTE=R.D. Silverman;236433]?? less than 4 times the work ?? Where did this come from?[/QUOTE]

Never mind. I figured it out. It was simple.