ElevenSmooth FAQ
M(3326400) = 23326400-1
|
ElevenSmooth FAQ
M(3326400) = 23326400-1 |
We search for previously unknown prime factors of 23,326,400-1.
We do it for fun. Every time we find a factor, we've learned something that's never been known before. We make a contribution to a generations long endeavor that is tracked and updated regularly.
We do it whenever our computers are turned on, running a program at low priority so that it never delays our usual applications, but progresses while the computer is waiting.
We run the ECMclient program. ECMclient handles the rest.
ECMclient reaches across the internet to get an assignment from the ECM Server. It then runs the ECM program once at low priority to calculate one curve. When the ECM program finishes, the ECMclient program checks to see if the time set in the configuration file has been reached. This time is the set by the line "maxfreq=30"; for a time longer than 30 minutes, increase this value. Until the time is reached, the ECM program runs more curves. After the time has been reached, the ECMclient program reports back to the ECM Server and gets a new assignment. When a factor is found, the ECMclient program reports immediately.
Many primitive factors and Aurifeuillian factors (see math questions) are known for 23,326,400-1. An assignment is one of these factors and a level for the ECM program to work at.
The ECM program looks for factors of its assigned number using the Elliptical Curve Method. Each time the ECM program runs, it computes one curve. Each curve has a chance of finding a factor. The probability of finding factors varies with the size of the factors and with the B1 and B2 parameters. The amount of effort varies the B1 and B2 parameters. See the Math Questions for more information.
Each composite number has a name that tells about the number. The name of this number is 2_11880P.C853. This name means that the number belongs to the primitive part of 211,880+1, and the number is a composite of 853 digits. The final part means that this assignment is to use ECM curves at the level B1=250000.
It means the ECM program is 10% complete on Stage 1 of the current curve. The numbers after the colon will increase until they reach 100. During Stage 2 this line always says "2:000" - the display does not change during stage 2. After Stage 2 finishes, another curve will be run unless it's time to contact the ECM Server. The counter will return to 1:000 when Stage 1 of the next curve begins.
ElevenSmooth uses software written by other people and made freely available on the web. The version of ECM we use doesn't update the percentage during Stage 2, so the ecmclient program cannot update. Source code is available, but there is work ongoing for a new release. I've decided to wait and see if the next release fixes this.
In number theory, " Smooth" means that a number completely factors into small primes. "11-Smooth" means that no prime factors exceed 11. Examples of 11-smooth numbers are 33, 77, 121, 242, and 231; the largest prime factor for each of these numbers is 11. The largest prime factor of our exponent, 3326400, is 11, so 3326400 is 11-smooth:
The Special Project uses GIMP's program Prime95 to work on all primitives of M(3326400) simultaneously. As a practical matter, this is a search of the 82 primitive factors with exponents that are a multiple of 25 or whose size is over ten thousand digits; the other 63 primitive factors are in the ECM server and have already been searched to higher levels. Prime95 uses Fourier Transforms for its mulitiplications, which makes it much faster on the largest composites. Prime95 works on the full Mersenne number, so the subfactor composites are tested "for free." Hence, as long as any work is planned for the largest composites, it is more efficient to do all the composites using Prime95.
Stage 1 of the Special Project searched for factors of 15 digits (B1=2K) and found forty new factors. Stage 2, searching for 20 digit factors (B1=11K), found 11 new factors. Stage 3, searching for 25 digit factors (B1=50K), is in process now.
There are some disadvantages to using Prime95. It requires more attention to download the updated factor files, run the program, and then email the results file. It also tries the patience of some people; at stage 3 each curve takes 15-20 Gigahertz hours. That's not too bad for 82 simultaneous tests, but they don't get the satisfaction of seeing the individual tests rack up. We are considering the tradeoffs for future work in the Special Project.The Special Project is currently open to people who have completed at least one full week on the ECM server. Shortly after the completion of one week you should receive an invitation at the email address in your configuration file. If you have been missed, contact me.
Explanations and instructions are on the Download Page.
You can download a plain copy of the program or you can remove the icon from your copy. You can download a plain copy directly from Tim Charron's site. You can download the free program Resource Hacker to remove the icon. Resource Hacker will also allow you to change the icon to one of your choosing; that's how I put the ElevenSmooth icon into Tim's program.
Every time I watch somebody new, I find things that need to be explained better and things that I forgot. Fixing these small things has been keeping me pretty busy, but there are some bigger things I work on between these small urgent issues. The things planned right now, in the roughly the order I expect to tackle them, are
Prime factors of Mersenne numbers are occasionally useful to mathematicians. For example, NFSNET factored M(713)=2713-1 to help in Richard Brent and Paul Zimmerman's research into primitive trinomials, which have applications in cryptography, coding theory, and random number generation. Factors of Mersenne numbers are also central to the study of covering sets for Sierpinski, Riesel, and Brier numbers. The Cunningham Project has been collecting Mersenne factors (and other factors) since 1925. There is enough interest that Will Edgington updates the file of known factors every few weeks on his web site.
If a number has a 15 digit factor, then each run of the Elliptical Curve Method with B1=2000 has one chance in 25 of finding that factor. Smaller factors will be found with higher probability, larger factors will be found with smaller probabilility. For 20 digit factors we set B1=11000; that gives one chance in ninety of finding a 20 digit factor. We run 25 curves with B1=2000, then 90 curves with B1=11000, then 300 curves with B1=50000, etc. The ECMserver program keeps track of the curves and raises the B1 value when enough curves have been run.
In reality, the chance of finding a number depends on the B2 value, too. The previous paragraph is correct for the traditional use of B2 = 100 * B1. The newest version of the ECM uses higher values of B2, so it has higher probability of finding a factor. But there isn't yet a new version of the ECMserver.
Very few of the people that use ECM understand how it works. The best that most of us can do is to understand Jim Howell's explanation. If you already understand elliptic curve arithmetic, you might understand Paul Zimmerman's description of ECM in The Elliptic Curve Method.
If a divides n, then we know from algebra that (xa-1) divides (xn-1) and (xa+1) divides (xn+1). Hence, for every divisor "a" of the exponent "n", we know that (2a-1) is a factor of (2n-1) and that (2a+1) is a factor of (2n+1). The factors (2a-1) and (2a+1) are called Algebraic Factors.
Because 33 and 77 (and other numbers) divide 231, we know that (233-1) and (277-1) (and other numbers) are algebraic factors of (2231-1). You can remove the contributions of these algebraic factors from (2231-1). When you have removed all contributions of all algebraic factors, the part that is left is called the primitive part.
Note that to calculate the primitive part you cannot just divide by the algebraic factors. In the example, (233-1) and (277-1) both have factors of (211-1). If you divide (2231-1) by both of these numbers, you will divide by the factor (211-1) twice, but (2231-1) has this factor only once. Calculation of the primitive primitive part requires compensating for these multiple contributions.
When we find factors, we report them to Will Edgington according to the primitive part they belong to. Will's files show only the factors of primitive parts directly. To get complete factorizations you must also look up the factors of the algebraic factors.
As described above, we need to account for the multiple contributions that happen because small algebraic factors are themselves factors of multiple large algebraic factors. To organize this, first list all the factors in ranks, where the factors in each rank have the same number of prime factors. For the exponenet 231 (=3 x 7 x 11), there are four ranks:
| 1. Three Primes: | 231 |
| 2. Two Primes: | 21, 33, 77 |
| 3. One Prime: | 3, 7, 11 |
| 4. Zero Primes: | 1 |
Consider the case of (2125-1). When we divide this by the algebraic factor (225-1), we have also divided by the algebraic factor (25-1), but we only divided by this factor once. There is no need to also multiply by (25-1) because there has been no multiple division to compensate for.
First find the product of the distinct odd primes taken only once - this is the "basic" exponent. Form the expression for the primitive part of the number with the basic exponent. Then find the ratio of the exponent to the basic exponent. Increase every exponenent in the expression by this ratio.
For example, to calculate the primitve part of (21386+1), we first find that the distinct odd primes are 3, 7, and 11, and the basic exponent is 231. The expression for the primitive part of (2231+1) is show above. The multiplicity is 1386 / 231 = 6. Hence the primitive part of (21386+1) is
Aurifeuillian factors are "kind-of" algebraic factors.
They are derived from the polynomial factorization
If "n" is an exponent that has Aurifeuillian factors, and "p" is a prime that is equal to 1 or 7 mod 8, then the "minus factor" for n, usually called Ln, divides the larger minus factor, Lpn. Likewise for the plus factors, called "M", Mn divides Mpn. For the other odd primes, where p is equal 3 or 5 mod 8, there is a "crossover," so Ln divides Mpn and Mn divides Lpn.
Continuing the examples, for p=7 and n=7*22=154, we have the Aurifeuillian factors:
Consider p=3 and n=3*22=66. This has the Aurifeuillian factors:
Except for the crossover issue, the divisibility and multiplicity issues for Aurifeuilian factors are identical to those issues for algebraic factors. Hence you can proceed in the same manner, determining the basic exponent, listing the factors in ranks, multiplying and dividing factors based on their rank, and apply the ratio. The small complication is that you must determine for each factor whether to use the L-Aurifeuillian (the "minus" one) or the M-Aurifeuillian (the "plus" one) to preserve the divisibility according to the divisibility rule.
Aurifeuillian factors split algebraic factors into two nearly equal components. Aurifeuillian Primitive Parts split Algebraic Primitive Parts into two nearly equal components.
The standard approximation for situations where there are many independent "opportunities" with a low probability of "success" in each opportunity is the Poisson probability distribution. This says the probability of having exactly "k" successes, if the expected (or average) number of successes is λ (lamda), is
This approximation becomes exact in the limit, as the number of "opportunities" becomes larger and the probability of success becomes smaller in such a way that the expected number of successes stays constant at λ (lambda). One use of this approximation is estimating the probability that a number has "k" divisors in a range, often for zero divisors in the range. We will also use this approximation below to estimate the probability of zero successes in "N" elliptical curve factoring attempts.
If the size range isn't too near the square root of our number, and we don't know of any other factors, then a reasonable heuristic is to observe that the probability a number "x" is prime is, according to the Prime Number Theorem, about 1/ln(x), and if x is prime, the probability x divides our number is 1/x. Adding this up, the number of primes expected in a range is:
The ECM algorithm is usually described as working on integers of 15 or 20 or 25 etc digits, depending on the value of B1. Twenty-five digits numbers range from 1024 to 1025, so we can guess that the ECM algorithm will find, roughly, numbers from 1022 to 1027 when working on twenty-five digit numbers. Ln(27/22) = 0.2048, so on average we would expect there to be about one prime factor in this range for every five composites considered. For other ranges the heuristic is:
| Size | B1 | Expected | Size | B1 | Expected | Size | B1 | Expected | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 15 digits | 2K | 0.3483 | 35 digits | 1M | 0.1452 | 55 digits | 110M | 0.0918 | ||
| 20 digits | 11K | 0.2578 | 40 digits | 3M | 0.1268 | 60 digits | 260M | 0.0841 | ||
| 25 digits | 50K | 0.2048 | 45 digits | 11M | 0.1125 | 65 digits | 850M | 0.0776 | ||
| 30 digits | 250K | 0.1699 | 50 digits | 43M | 0.1011 | 70 digits | 2.9G | 0.0720 |
These numbers apply directly for most of the primitives in the ElevenSmooth project. The major exceptions are those numbers which have Aurifeuillian factors. For those numbers we know a factorization of the primitive, and these estimates apply to each of those factors, resulting in twice as many expected factors of a given size.
First of all, there must really be a factor of the appropriate size; see the earlier question for information about this. Even if the factor exists, the probability of finding it on a particular curve depends on the B2 level as well as the B1 level. A common choice is to set B2 as 100 times B1; Previous versions of GMP-ECM used this convention, the Alpertron Java applet uses this, and ElevenSmooth uses this with Prime95 in the Special Project. Version 5 of GMP-ECM, the program ElevenSmooth uses with the ECM server, has improvements for Stage 2. To take advantage of these improvement, the default B2 value is higher, resulting in a higher probability of finding a factor on each curve. The following table shows the probabilities in the form "1 out of n".
| Size | B1 | 1:100 | ECM5 | Size | B1 | 1:100 | ECM5 | Size | B1 | 1:100 | ECM5 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 15 digits | 2K | 25 | 30 | 35 digits | 1M | 1800 | 1100 | 55 digits | 110M | 49000 | 22000 | ||
| 20 digits | 11K | 90 | 90 | 40 digits | 3M | 5100 | 2900 | 60 digits | 260M | 124000 | 52000 | ||
| 25 digits | 50K | 300 | 240 | 45 digits | 11M | 10600 | 5500 | 65 digits | 850M | 210000 | 83000 | ||
| 30 digits | 250K | 700 | 500 | 50 digits | 43M | 19300 | 9000 | 70 digits | 2.9G | 340000 | 120000 |
We can use the Poisson Approximation (see above) to answer this question. First we find λ (lambda), the expected (or average) number of times we will find this factor in N trials. This is "N" divided by the appropriate number from the table. We are most interested in the probability of finding the factor zero times (k=0), because subtracting that from one gives the probability of finding the factor one or more times.
When you perform the "full set" of curves, the value of λ (lamda) is "1", the probabilty of not finding the factor is (1/e), and the probability of finding the factor at least once is 1-(1/e).
Sam Wagstaff, the present keeper of the Cunningham Project, says it ”seeks to factor the numbers bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n.” The history of the Cunningham Tables has been to extend the base 2 tables in every edition. Because 23,326,400-1 has many algebraic factors, ElevenSmooth finds factors for many exponents, including small exponents such as 21485-1 and 21575-1. You can see the ElevenSmooth factors in Mersenne order by clicking on the Mersenne column header on the Factors Page. So Elevensmooth is, at least philosophically, part of the Cunningham Project and the Cunningham Tables will grow into our factors.
The major activity of the Great Internet Mersenne Prime Search (GIMPS) is searching for prime numbers. But there is also a part of GIMPS that is factoring 2n-1 and 2n+1. ElevenSmooth is, at least philosophically, part of this aspect of GIMPS.
Not unless there is a theoretical breakthrough. Theory provides methods to find factors up to 50 digits (ECM, P-1, P+1), and theory provides methods to factor numbers up to 180 digits (250 digits if they have a special form). Faster hardware and larger networks of computers might raise these limits by 10 or 20 digits, but only the invention of a new factoring technique could take us much beyond that.
When it isn't fun anymore. Our smallest factors will become candidates for the NFSNET Project after they have been tested for factors up to 50 digits. So even if we stop finding factors, we will be making progress towards the eventual factoring of these numbers.
I was originally interested in partial coverings for the Seventeen or Bust project. A covering can be reused if the size of the new covering is a multiple of the old size. For example, a covering of size 36 can be reused within a covering of size 72. I kept multiplying by one more small number until I reached 3,326,400. The possible numbers in a covering of size "n" are exactly the prime factors of 2n-1, so I became interested in the factors of 23,326,400-1. I learned that many factors were unknown but within reach of factoring technology; thus was born the ElevenSmooth Project. None of these additional factors have been useful for Seventeen or Bust, but I've become hooked on finding them.
|
 |
|
 |
|
I used the free program giftrans to find and change the palette. I wrote the GIFtrans.xls Excel Spreadsheet to automate the color changes. Detailed instructions are in the Recoloring Tutorial.
Copy the file "favicon.ico" to your home directory - the directory with index.html. That's all.
It is possible to use a different name for the icon file,
and it is possible to use different icons on each page.
For example, this page should be showing a blue version of the ElevenSmooth icon instead of the standard green version.
To display "name.ico" for a page, you must include the following line in the head section of the page:
Googling "HTML sortable table" will turn up many accolades for Erik Arvidsson's WebFX Sortable Table. Download it and follow the instructions. I found it easy to add new sorting rules for cases that did not exactly fit his three methods. See my sortabletable.js file for more information.
You can change the background of an entire row or an entire table by putting the "id" attribute inside the row or table tag.
The "Subject" Field on the Contact Page changes based on the link you clicked. For example, this link sets the Subject as Help while this link sets Special Project. The URL for the Contact Page includes an extra string on the end; after "ElevenContact.html" there is a question mark and a short string. In the source code for the page, JavaScript creates the input field using "document.write()" commands. JavaScript reads the short string using "location.search.substring(1)", and writes the <option selected> tag based on comparisons with that value.
Most pages on this web site have an identical cluster of navigation links on the bottom of the page.
As the site grows and evolves, these links change.
I make the changes only once to change the links on all pages.
If you examine the source code, you will find, at the end,
The Print Screen key will put a bitmap image of the screen into the Windows clipboard. From there you can paste the image into many applications, including PhotoEditor, Paint, and Word. I usually pasted into PhotoEditor (Start>Programs>MicroSoft Office>PhotoEditor), then crop the picture (Images>Crop) to the desired size, then save as JPEG or GIF.
Microsoft Word has a pretty good GUI equation editor. Create an equation by Insert>Object>Microsoft Equation. Use the toolbar to build the expression. When you have the expression built in the Word Document, leave the equation edit mode by clicking outside the equation box. Then select the whole equation box and enter the equation editing box by pulling down Edit>Equation Object>Open. This will open its own window which includes custom sizing through View>Zoom. Select an appropriate size then capture a screen image (see previous question).
The Contact Page sends me an email every time somebody clicks "Send" - no further action is required by the user. This requires a "server side" function by the computer that is hosting your web site. Of the thousands of functions that can be done "server side," Earthlink only permits three for free, and this is one of them. Earthlink has a basic page and an advanced page describing their system. Your web host probably provides this service, too, although the details may be different.
If your web host will not provide this service, you can try the HTML Mailto capability. When it works, it opens the user's email program with a pre-composed message. Laurie D.T. Mann has a simple descripion. The Web Design Group has more details, including the advice that "mailto" will fail for many users and information about services.
Most Internet Service Providers (ISPs) provide a small amount of free web space with their accounts. MY ISP, Earthlink, permits up to six email addresses and provides 10 Mbytes of web space with each address. I created a new email address called "ElevenSmooth" and I use those 10 Mbytes.
I bought the domain name from Web.com I did not buy any additional services.
I signed up for the free DNS and domain management account at ZoneEdit.com. Up to five domains can be managed under the free account. Following the ZoneEdit FAQ, I changed the Name Servers and created a Web Forwarding for elevensmooth.com and www.elevensmooth.com.
If you find one of these web tips useful, a great way to say "thank you" would be to donate a week of your idle, wasted computer cycles to the ElevenSmooth Project. The Download Page will get you started.
Every time we find a new factor, there is a small thrill of having learned something that nobody has ever known before - something that the world cares about enough to track. There is also a small thrill of victory over a recalcitrant number that was hiding its factors. There is a satisfaction in using our computers during the idle times that it is normally waiting for keystrokes. There is a sense of history in knowing that we are contributing to a factorization project that has been going on for generations and will continue into the unforeseeable future, each generation using the best tools known at the time to uncover factors of larger and larger numbers. And there is a camraderie with our fellow searchers, having found a few people that share these same passions and pleasures.