Talk:Cunningham chain

From Wikipedia, the free encyclopedia

[edit] Finding Large Primes

I would like to apologize for an edit that I made. PrimeHunter got rid of them and, after reading his reasons, they seem like good ones. The edit pertained to generalizing Cunningham Chains to "Cunningham Trees" and "Cunningham Dags". I will say that, from my personal experience with Wikipedia pages, sections which seem to be "off topic" or even "original research" nevertheless continue to exist provided that they are very small, almost perfunctual. Where do we draw the line between a quick quip, which anyone reading the page would consider to be quite obvious (even without actually seeing said quick quip), and actual "original research"? —Preceding unsigned comment added by 131.123.41.22 (talk)

I restored your above edit to this talk page as I had already written an answer to it. It's about this diff which I reverted. Many existing articles do contain inappropriate Wikipedia:Original research for a long time, but added content should follow policies and guidelines, not imitate bad content in other articles. Editors can disagree whether something is OR or relevant, but it seemed clear to me for "Cunningham Trees" and "Cunningham Dags" which gave no verifiable source. Almost any math concept can be varied somehow (Cunningham chains are a variation of Sophie Germain primes), but Wikipedia should not be first to give a variation, and your variation was so large that I would no longer relate it to Cunningham chains. Your section started "Of course, if all we want to do is find a large prime, then we might ask why it specifically has to be a chain rather than a tree or even a DAG". But nobody claimed the goal was to find a large prime (which there are far better ways to do). Cunningham chains are chains by definition as the name indicates, and were not invented to find large primes. By far the most common way to find the largest known primes is testing individual numbers of the form k*2^n+/-1 for small k (k=1 for Mersenne primes), without thinking about chains, trees, or graphs. There a few things "anyone reading the page would consider to be quite obvious". Many readers of this page will not know when it's easy to prove that a large number is prime, and then your edits may be confusing. For example, people might think your suggestions are more likely to produce primes than random odd numbers, considering your "we eventually find some fantastically large prime numbers". PrimeHunter 14:34, 10 January 2007 (UTC)

Can somebody find a source which allows me to add this?

Finding Large Primes

Of course, if all we want to do is find a large prime, then we might ask why it specifically has to be a chain rather than a tree or even a DAG (directed acyclic graph). For example, let P1 through P7 be odd primes. P1 through P4 are easily veriafiable by trial division. P5-1 equals a power of 2 times a power of P1 times a power of P2. P6-1 equals a power of 2 times a power of P3 times a power of P4. Finally, P7-1 equals a power of 2 times a power of P5 times a power of P6 times a power of P3 times some R whose prime factorization is unknown and/or irrelevant. In the case of P7, we'll say R is not divisible by any of 2, P5, P6 or P3 and that it is less than (P7-1)/R (i.e., the factored portion). P5 and P6 are easily verifiable by Lucas's classical [n-1 test] and P7 is easily verifiable by the classical [n-1=F*R] test based on [Pocklington's Theorem]. If we continue building this table from the bottom up, we eventually find some fantastically large prime numbers. We also see that it is not a Cunningham chain but, instead, can be thought of as a kind of "Cunningham DAG". If we modify this example such that P7-1 is not divisible by P3, then it becomes something we can think of as a "Cunningham tree" which, in this case, is still not a chain. —Preceding unsigned comment added by 131.123.41.22 (talk)

If you came up with it on your own then it seems unlikely there is an acceptable source. To me it looks like an arbitrary and uninteresting way to construct large numbers which will be easily provable when they happen to be prime. Any number (maybe limited to around a million digits) of the form N-1 or N+1 will be easily provable with PrimeForm, if it's actually prime and the product of known prime factors of N is at least the cube root of N (people usually choose N with all prime factors known). PrimeHunter 14:34, 10 January 2007 (UTC)

I (Jens Kruse Andersen) have actually worked on something called "Prime trees" on a blog. [1] It could also have been called something like "Generalized Cunningham trees", but it's not suitable for Wikipedia or as a source to your edit. PrimeHunter 14:53, 10 January 2007 (UTC)

Agreed. Like I said, maybe I was fooled by the bad examples I saw on other Wikipedia pages (Where you said, "Many existing articles do contain inappropriate Wikipedia:Original research for a long time"). In any case, it is precisely because the method is "uninteresting" (insofar as it is not much of an intuitive leap to take a number of known primes, multiply them together along with a random portion and add 1) as a "way to construct large numbers which will be easily provable when they happen to be prime" that I hypothesize, in this discussion page, that someone must have already thought of it. —The preceding unsigned comment was added by 24.164.108.87 (talk) 15:32, 10 January 2007 (UTC).

Note: 131.123.41.22 = 24.164.108.87. Please sign talk page comments with ~~~~. Getting an account also has advantages. Avoiding varying IP numbers is just one of them.

Many have thought of the general method without any relation to Cunningham chains. I could easily find forum posts and similar (e.g. by myself [2]) about it, but they don't satisfy WP:RS. Unless a reference specifically speaks of Cunningham chains and something like your P1 to P7 (which is what I considered an uninteresting example of the method), I see no reason to add it to the article. PrimeHunter 16:14, 10 January 2007 (UTC)