On Fri, Jan 23, 2009 at 6:06 PM, A. Jorge Garcia <[email protected]> wrote: > > I'm still trying to learn a bit about Sage in general and python in > particular. I was trying to code the Lucas-Lehmer Test for primality > of Mersenne Numbers of the form 2**p-1 where p is an odd integer. > > I found this code on wikipedia > > def lucas_lehmer(p): > s = 4 > m = (2**p)-1 > for i in range(0, p-2): > s = ((s*s)-2)%m > return (s==0) > > Can anyone out there please comment on the correctness of this boolean > function? This does not look like the Lucas-Lehmer Test I've seen > before. Isn't the idea is to be able to test large values of 2**p-1 > without calculating 2**p-1, right? This function dosn't do that!
That is not the point of lucas-lehmer. The point is to determine whether or not 2^p - 1 is a prime number more quickly than ... say checking for divisibility by primes up to sqrt(2^p - 1). > > Anyone recall the correct algorithm for this test? > > TIA, > A. Jorge Garcia > [email protected] > http://calcapge.tripod.com > > Applied Math, Physics and CompSci > Baldwin High School & Nassau Community College > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sage-edu" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-edu?hl=en -~----------~----~----~----~------~----~------~--~---
