What's the basic LLR equation?

jasong · 2012-02-19, 15:33

I'm wondering the basic LLR equation. Not the FFT stuff, but the basic math problem it's applied to.

I'm going to show it to my friends and see if can see the white all the way around their irises(wrong word?) when they realize just how big the numbers being dealt with are.

Hmmmm, just Googled it, and there might not be an actual equation. To be honest, I thought it was something like:

[2^(2^n-1)]/n then check to see if the remainder is 0.

Edit2: I meant no OBVIOUS ALGEBRAIC equation.

science_man_88 · 2012-02-19, 15:42

Quote:

Originally Posted by jasong

I'm wondering the basic LLR equation. Not the FFT stuff, but the basic math problem it's applied to.

I'm going to show it to my friends and see if can see the white all the way around their irises(wrong word?) when they realize just how big the numbers being dealt with are.

Lucas–Lehmer–Riesel test

jasong · 2012-02-19, 16:06

Yes, science man :) that's what I Googled before I posted my edits.

Unfortunately, their eyes will probably glaze over if I try to explain it to them, I was hoping for a literal algebraic equation even though the actual numbers are unbelievably gigantic.

Actually, though... Well, with some exponents you start with 4, square it and subtract 2, square that and subtract 2, square THAT and subtract 2...I think I can explain that adequately.

Hmmmm, might still be able to do this.

TimSorbet · 2012-02-19, 16:32

Utilizing modular arithmetic, the numbers are only ever as large as k*2^n-1 (i.e. the number you're testing). If we didn't have that benefit, hm...
(LL/LLR are practically interchangeable for this discussion; the difference that comes from different starting points is negligible) It's sequence A003010. At index 0, it's 4. By index 6, it has 37 digits. Running the LL test for M7 requires you to go to index 5. MM7 has 39 digits. So the sequence that is at the heart of the LL/LLR tests makes numbers roughly 2^N, where N is the number you're testing. For LLR tests, this means checking if a number of about the size 2^(k*2^n-1) divides k*2^n-1. For a megabit prime, this has over 10^300,000 digits (for comparison, a billion has 10 digits, and a googolplex has 10^100+1 digits). For the largest known prime, this has almost 10^13,000,000 digits. In general, for a x-digit number, the sequence would go to about 10^x digits if not for modular arithmetic. In case you didn't notice, there's nothing here special about base 10. For any base b: for an x-digit (in base b) number, the sequence would be about b^x digits.
Notice that I only say the number's approximate size. This is because getting the exact value would be most simply stated as the LL sequence formula, which is not easy to intuitively grasp the size of.

jasong · 2012-02-20, 03:33

Yes, Mini-Geek, I understand. The numbers we're dealing with are frickin' huge, and only modular arithmetic allows us to get an answer.

2012-02-19, 15:33	#1
jasong "Jason Goatcher" Mar 2005 110110110011₂ Posts	What's the basic LLR equation? I'm wondering the basic LLR equation. Not the FFT stuff, but the basic math problem it's applied to. I'm going to show it to my friends and see if can see the white all the way around their irises(wrong word?) when they realize just how big the numbers being dealt with are. Hmmmm, just Googled it, and there might not be an actual equation. To be honest, I thought it was something like: [2^(2^n-1)]/n then check to see if the remainder is 0. Edit2: I meant no OBVIOUS ALGEBRAIC equation. Last fiddled with by jasong on 2012-02-19 at 15:43

2012-02-19, 16:32	#4
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 11·389 Posts	Utilizing modular arithmetic, the numbers are only ever as large as k2^n-1 (i.e. the number you're testing). If we didn't have that benefit, hm... (LL/LLR are practically interchangeable for this discussion; the difference that comes from different starting points is negligible) It's sequence A003010. At index 0, it's 4. By index 6, it has 37 digits. Running the LL test for M7 requires you to go to index 5. MM7 has 39 digits. So the sequence that is at the heart of the LL/LLR tests makes numbers roughly 2^N, where N is the number you're testing. For LLR tests, this means checking if a number of about the size 2^(k2^n-1) divides k2^n-1. For a megabit prime, this has over 10^300,000 digits (for comparison, a billion has 10 digits, and a googolplex has 10^100+1 digits). For the largest known prime, this has almost 10^13,000,000 digits. In general, for a x-digit number, the sequence would go to about 10^x digits if not for modular arithmetic. In case you didn't notice, there's nothing here special about base 10. For any base b: for an x-digit (in base b) number, the sequence would be about b^x digits. Notice that I only say the number's approximate size. This is because getting the exact value would be most simply stated as the LL sequence formula, which is not easy to intuitively grasp the size of. Last fiddled with by TimSorbet on 2012-02-19 at 16:49*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Diophantine Equation	flouran	Math	7	2009-12-12 18:48
Solve this equation	davar55	Puzzles	52	2007-06-26 21:41
Possible solutions to an equation:	Vijay	Math	6	2005-04-14 05:19
Time to prp equation	jasong	Math	2	2005-03-11 03:30
Cuberoot Equation	koal	Puzzles	3	2003-07-03 11:58

2012-02-19, 16:06	#3
jasong "Jason Goatcher" Mar 2005 3×7×167 Posts	Yes, science man :) that's what I Googled before I posted my edits. Unfortunately, their eyes will probably glaze over if I try to explain it to them, I was hoping for a literal algebraic equation even though the actual numbers are unbelievably gigantic. Actually, though... Well, with some exponents you start with 4, square it and subtract 2, square that and subtract 2, square THAT and subtract 2...I think I can explain that adequately. Hmmmm, might still be able to do this.

2012-02-20, 03:33	#5
jasong "Jason Goatcher" Mar 2005 3×7×167 Posts	Yes, Mini-Geek, I understand. The numbers we're dealing with are frickin' huge, and only modular arithmetic allows us to get an answer.