This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of
mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
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)reply
For example that's ok, it is a prime
>>>p=65728407627*px(431)- 1
>>>
>>> pow(2,p-1,p)
1L
>>>
But this is wrong,
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)reply
I assume pow(2,p-1,p) is supposed to compute a modular exponentiation 2p-1 mod p, making it a base 2 Fermat prp test, but your result is wrong. The right result is 1. In PARI/GP:
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)reply
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.
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)reply
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)reply
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)reply
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).reply
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)reply
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
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)reply
I have added a short proof (based on cited ref) that A above is false.
Hpablo (
talk) 17:35, 9 October 2013 (UTC)reply
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)reply