View Single Post
Old 2012-02-19, 16:32   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

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.

Last fiddled with by Mini-Geek on 2012-02-19 at 16:49
Mini-Geek is offline   Reply With Quote