[sage-edu] Lucas-Lehmer Test
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! Anyone recall the correct algorithm for this test? TIA, A. Jorge Garcia calcp...@aol.com http://calcapge.tripod.com Applied Math, Physics and CompSci Baldwin High School & Nassau Community College --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "sage-edu" group. To post to this group, send email to sage-edu@googlegroups.com To unsubscribe from this group, send email to sage-edu+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-edu?hl=en -~--~~~~--~~--~--~---
[sage-edu] Re: Lucas-Lehmer Test
On Fri, Jan 23, 2009 at 6:06 PM, A. Jorge Garcia 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 > calcp...@aol.com > 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 sage-edu@googlegroups.com To unsubscribe from this group, send email to sage-edu+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-edu?hl=en -~--~~~~--~~--~--~---
[sage-edu] Re: Lucas-Lehmer Test
In a message dated 1/23/2009 9:12:19 P.M. Eastern Standard Time, wst...@gmail.com writes: 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). OK, I stand corrected. But what if 2**p-1 is huge, will this function really save significant processing time? Also, I used this predicate method as follows: for p in range(3,1,2): if lucas_lehmer(p): print p, 2**p-1. On this range of odds from 3 to 1, p was always prime, and all prime numbers p gave 2**p-1 prime. I thought that if 2**p-1 is prime, then p is prime, but not all prime values of p will give 2**p-1 prime. HTH, A. Jorge Garcia calcp...@aol.com http://calcpage.tripod.com Teacher & Professor Applied Mathematics, Physics & Computer Science Baldwin Senior High School & Nassau Community College **A Good Credit Score is 700 or Above. See yours in just 2 easy steps! (http://pr.atwola.com/promoclk/10075x1215855013x1201028747/aol?redir=http://www.freecreditreport.com/pm/default.aspx?sc=668072%26hmpgID=62%26bcd=De cemailfooterNO62) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "sage-edu" group. To post to this group, send email to sage-edu@googlegroups.com To unsubscribe from this group, send email to sage-edu+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-edu?hl=en -~--~~~~--~~--~--~---
