View Single Post
Old 2005-09-20, 00:41   #10
cheesehead's Avatar
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts

Originally Posted by ppo
one interesting thing is that if we do like I suggested in my previous post, S(n-3) seems to be always equal to 2^((n+1)/2), when M is prime. ( I have only tested with some small values of n). Someone has a proof for that ?
Suppose it's true. It wouldn't speed up anything, because one still has to compute all the S(i) mod M values leading up to S(n-3) in order to test whether S(n-3) = 2^((n+1)/2) mod M. And that's exactly what the L-L test already does (except that it continues one more step to compute S(n-2) mod M). There's no time savings.
cheesehead is offline   Reply With Quote