Talk:Cunningham chain

What is wrong here ?

I wrote a Pythonscript to caluclate #p. It seems to work for smaller numbers. But some values are no primes.

def px(p):

m1 = 1 
msize = p+2
arr = msize*[True]
for k in range(2, msize):
  if arr[k] and k <= p:
    print "add prime ", k
    m1 = m1 * k
  for kx in range(2,(msize+1)/k):
      arr[kx*k] = False   
return m1  — Preceding unsigned comment added by 109.90.224.162 (talk) 15:38, 8 October 2015 (UTC) 

For example that's ok, it is a prime >>>p=65728407627*px(431)- 1 >>> >>> pow(2,p-1,p) 1L >>> But this is wrong,

p=162597166369*px(827)-1

it is no prime. 109.90.224.162 (talk) 15:58, 8 October 2015 (UTC)

162597166369*827#-1 is prime. In PARI/GP:

? primorial(p)=prod(n=1,primepi(p),prime(n))
? isprime(162597166369*primorial(827)-1)
%1 = 1

The decimal digits of the prime is 27922....32009. I don't know Python but either you must test the wrong number or your primality test doesn't work on the number. PrimeHunter (talk) 21:20, 8 October 2015 (UTC)

>>> pow(2,p-1,p) 487546811839854522788113514351408102380541225180427993160810257150139475656609728609344665746903182037353160368602802365213893325348744829646745934070619934848112171595584065295105710885507642648010814634964874504648351390543638828638090415468273304689943046192577167310588645893360778924367913687692538014152679942606520009152126660498855699834124118905528L

No, it must be one, if p is prime.109.90.224.162 (talk) 21:41, 8 October 2015 (UTC)

I assume pow(2,p-1,p) is supposed to compute a modular exponentiation 2^p-1 mod p, making it a base 2 Fermat prp test, but your result is wrong. The right result is 1. In PARI/GP:

? primorial(p)=prod(n=1,primepi(p),prime(n))
? p=162597166369*primorial(827)-1;
? lift(Mod(2,p)^(p-1))
%2 = 1

With PrimeFormGW which found many of the largest known primes:

C:>pfgw32 -b2 -q162597166369*827#-1
PFGW Version 3.6.7.32BIT.20121129.Win_Dev [GWNUM 27.8]

162597166369*827#-1 is 2-PRP! (0.0075s+0.0004s)

Your wrong value has 357 digts and is larger than the 356-digit prime p, so either you are testing a wrong number or using a program that doesn't work on the number. PrimeHunter (talk) 22:53, 8 October 2015 (UTC)

How it works

For every integer n

n x (#p) - 1 mod 6 = 5

and such a number is not divisible by any prime smaller or equal p and therefore quite likely prime. So it is easy to find Sophie Germain primes by testing such numbers.

109.90.224.162 (talk) 19:12, 8 October 2015 (UTC)

Yes, it means no precalculated lists are really required to find safe primes for Diffie-Hellman or Elgamal.

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)

Possibility of unbounded length?

Consider these propositions:

A: there exists a first-kind Cunningham chain of infinite length

B: for every integer n, there exists a first-kind Cunningham chain of at least n elements

C: there exist infinitely many Sophie Germain primes

A implies B, and B implies C. Since the veracity of C is currently unknown, it cannot be known that either A or B is true. Disproving C would disprove A and B, but proving C wouldn't prove anything about A and B.

But still, it would be interesting to know whether either A or B has been disproven by some other means.

To look at it differently, there are four possibilities:

(a) the number of Sophie Germain primes is finite

(b) there are infinitely many Sophie Germain primes, but Cunningham sequences have a maximum length (the set of possible Cunningham sequence lengths is a finite ordinal)

(c) there exist arbitrary long Cunningham sequences, but no infinitely long ones (the set of possible Cunningham sequence lengths is ω)

(d) there exists an infinite Cunningham sequence (the set of possible Cunningham sequence lengths is ω + 1)

So (a) is an open possibility. But is each of the others still an open possibility, or has any of them been disproven? — Smjg (talk) 00:15, 3 June 2012 (UTC)

I have added a short proof (based on cited ref) that A above is false. Hpablo (talk) 17:35, 9 October 2013 (UTC)

Anti cunningham chain

This has zero google hits. Does not seem to be an established thing or at least name. -Koppapa (talk) 09:51, 12 January 2022 (UTC)