Slashdot Mirror
Another Breakthrough in Prime Number Theory
Battal Boy writes "From aimath.org: Dan Goldston and his Turkish colleague Yalcin Cem Yildirim have smashed all previous records on the size of small gaps between prime numbers. This work is a major step toward the centuries-old problem of showing that there are infinitely many 'twin primes': prime numbers which differ by 2, such as 11 and 13, 17 and 19, 29 and 31,...I am especially proud of this achievement as Yalcin is a close friend of mine from way back! You may also want to check out the Mercury News Article and Dan Goldston's home page where you can see a photo of Dan's back being slowly but surely broken by two of his children ..." Finding patterns in primes seems to be all the rage.
Ok, so there are infinite twin prime numbers but what about secondary numbers? Have we just given up on them?
Checking out my form of escapism.
Here I thought the patterns-in-primes thing was already solved by Jodie Foster and Matthew McConaughey..
This is certainly a signficant advance in mathematics... prime numbers are one of the most enigmatic, yet useful aspects of number theory. What I'm really curious to see is whether or not this will help the efforts to find a more efficient algorithm for factoring a number into its prime factors. (A multiple of two very large primes is an integral part of RSA encryption, as well as other schemes.)
-- Apple: Where Microsoft wants to go today.
Funny, I can't see their server getting slashdotted anytime soon...
Don't make fun of this. This is vitally important. Finally we'll know.. wait what are we doing again? Prime number theory? Fuck it gimmie a beer
Any research that can make dealing with prime numbers easier can make cracking RSA asymmetric encryption (the most widely used atm) easier, and thus directly affect your privacy.
Apart from that, of course it's extremely boring, but so is everything, until you think of the applications.
Daniel
Carpe Diem
Both of those are solved problems. Differential equations can model them well... Yes, I know that wasn't your question, but you know the joke about the mathematician in the burning building, right?
-- Apple: Where Microsoft wants to go today.
There's a small joke that goes around in the academic world
Biologists like to think they are chemists. Chemists like to think they are physicists. Physicists like to think they are mathematicians. And mathematicians like to think they are god.
Seriously, think of how much of what we learn boils down to our understanding of numbers, systems, and patterns within them. Mathematics, whether you like it or not, is really a beautiful and elegant subject that very few truly understand.
I was waiting for a better time to break this, but I guess now is good to. I have made a groundbreaking discovery in prime numbers.
No prime numbers can be divided by any number that falls inbetween the number one and the number itself! And, even more exciting, a rule that applies to all prime numbers. All prime numbers can be factored with the number one, but none can be divided by zero.
I hope none of you had anything important "encrypted" with PGP. Just stick to padless one-time pads for *real* security.
After I get the National Math Foundation to classify two as an odd number (and it is really odd considering it's the only even prime number) I'll have my third discovery that all prime numbers are odd validated.
I'd love to post more, but I really must get back to working on my perpetual motion machine. I was so close before, but recently I seem to have lost my bearings. Once I'm done I'll be heralded as the greatest man in the realm of science friction.
Have you read my journal today?
here
Conversely, having knowledge of more prime numbers also means that new encryption tech can be based on those new theories and enhance privacy. It's kinda a double edge sword...
This has nothing to do with encryption, nothing to do with RSA, nothing to do with practical applications at all. Factoring and cryptography is only a small part of the ocean that is number theory. Please don't automatically assume that anyting about number theory or prime is related to encryption and practical applications. This one certainly isn't. This is about twin primes: the authors have proven that the gaps between consecutive primes are small, asymptotically smaller than the logarithm of the number. This *might* lead to attacks on the twin prime conjecture. Nothing is known yet. This is highly theoretical work. Appreciate pure mathematics, with its beauty, for its own sake.
One reason that it is intuitivly possible that there are an infinite number of twin primes is that it is possible to generate numbers that are relativily prime. For example, multiply the first three primes: 2,3, and 5. You get 30. Add or subtract one from 30 and you will get a number that is relatively primet to 2, 3, and 5. In this case you get 29 and 31. Both happen to be prime numbers. We've found a twin.
The hard part of proving there are an infinite number of twins is finding a way of showing that your relatively prime numbers are truely prime. IE, in this case that neither is divisible by a higher prime such as 7, or 11.
Next step is to find prime numbers differing by 1.
When prime numbers were first discovered, don't you think everyone initially thought "Great... Who cares about these numbers that have no other factors?" In fact, if I was around when they were first discovered, I bet I would have thought it was a completely meaningless discovery. Who would have thought that later on, prime numbers would become a vital part of encryption? Anyway, my point is that although right now this seems to be of little practical value, who knows what future 'breakthroughs' will be based upon it? Perhaps someone will be inspired by this and come up with a revolutionary way allowing RSA to be cracked in microseconds? And even if no practical use is discovered any time soon, it's still one more thing better understood.
________________________________________________
suwain_2
How exactly does one hold on to frictionless bearings? Do you use [http://www.archive.org/movies/details-db.php?id=2 74]Johnson & Johnson plastic wraps to stick to them?
Several scientists were asked to prove that all odd integers higher than 2 are prime.
..."
http://www.math.utah.edu/~cherk/mathjokes.html
Mathematician: 3 is a prime, 5 is a prime, 7 is a prime, and by induction - every odd integer higher than 2 is a prime.
Physicist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is an experimental error, 11 is a prime. Just to be sure, try several randomly chosen numbers: 17 is a prime, 23 is a prime...
Engineer: 3 is a prime, 5 is a prime, 7 is a prime, 9 is an approximation to a prime, 11 is a prime,...
Programmer (reading the output on the screen): 3 is a prime, 3 is a prime, 3 a is prime, 3 is a prime....
Biologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 -- results have not arrived yet,...
Psychologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime but tries to suppress it,...
Chemist (or Dan Quayle): What's a prime?
Politician: "Some numbers are prime.. but the goal is to create a kinder, gentler society where all numbers are prime... "
Programmer: "Wait a minute, I think I have an algorithm from Knuth on finding prime numbers... just a little bit longer, I've found the last bug... no, that's not it... ya know, I think there may be a compiler bug here - oh, did you want IEEE-998.0334 rounding or not? - was that in the spec? - hold on, I've almost got it - I was up all night working on this program, ya know... now if management would just get me that new workstation tha just came out, I'd be done by now... etc., etc.
Saskboy's blog is good. 9 out of 10 dentists agree.
I don't think this will help cracking RSA in anyway. I even believe this will even strengthen the RSA encryption. RSA is based upon the fact that it is very difficult (as in there is no trivial way) to factor a composit number into two primes. And these new theories won't help factorization. Ofcourse, if there is indeed a usufull pattern, it may help to find the primes---that are required for factorization---faster, but the person who uses the RSA-technique can do this too. This will allow the this person to find even bigger primes faster then usuall, so even if the cracker can find possible usufull primes faster, he has to try a whole lot more to facter the composite number. And since trying out a factor to see if the is part of the composite takes much longer time, I only see benefits for the RSA encryption scheme.
You know it makes sense, a little reminder from jointm1k.
Strictly speaking, negative numbers can be prime, however, -x is prime if and only if x is prime, so number theorists usually just deal with the positive ones.
As for "counting as factors," one has to look at the definition. An irreducible is a number (well, non-unit element of a ring) such that every factorization has a unit as one of the factors. In the integers, 1 and -1 are the units.
A prime is a number such that if it divides a product, it divides one of the factors. In the integers, these come down to the same thing.
this joke?
An engineer, physicist, and mathematician are all challenged with a problem: to fry an egg when there is a fire in the house. The engineer just grabs a huge bucket of water, runs over to the fire, and puts it out. The physicist thinks for a long while, and then measures a precise amount of water into a container. He takes it over to the fire, pours it on, and with the last drop the fire goes out. The mathematician pores over pencil and paper. After a few minutes he goes "Aha! A solution exists!" and goes back to frying the egg.
Sequel: This time they are asked simply to fry an egg (no fire). The engineer just does it, kludging along; the physicist calculates carefully and produces a carefully cooked egg; and the mathematician lights a fire in the corner, and says "I have reduced it to the previous problem."
riding round the world on an old motorcycle
It's posts like these that make me wish there was a mod option of "What the??" I am lost lol ;)
Indeed, take Buffon's Needle Problem for instance. whoda thunk it.
"Not knowing when the dawn will come, I open every door." - Emily Dickinson
Short answer: Yes, -3 is prime in the integers.
Long answer:
So 3|6 because 6=3*2, and (-3)|6 because 6 = (-3)*(-2), and so on.
As an example of this, 48 = 6*8. 3|48, so for 3 to be prime, we would need either 3|6 or 3|8.
Since 3|6, it passes the test in this case (but remember, the condition has to be true for all pairs of integers.)
since 3|a if and only if (-3)|a (Proof: Slashdot post is too small to contain it
You want boring? Then go and take a look at the PDF papers on this site.
Are they boring? Yes, exruciatingly and mind numbingly so...
Did they help us win the Second World War? err...yes
A cynic is what an idealist calls a realist...
Mathematicians described the advance -- announced at a conference in Germany -- as the most important breakthrough in the field in decades.
Personally, I think the technique for provably determining the primality of an arbitrary number in polynomial time -- "PRIMES is in P" -- was a more unexpected result. It's always seemed like the probability of a twin prime occuring on the number continuum was a limit approaching but never quite reaching 0 -- an artifact of the number of previous primes already "exposed" approaching, but never reaching infinity. But actually sitting down and proving this -- excellent! Very cool.
--Dan
How about calculating the rate of ring growth in trees as well?
One per year.
See you in stockholm!
Fleur de Sel
You can't use statistics or probabilities as proofs :)
:) )
:)
I don't think you'll find anyone that will make a wager that there aren't an infinite amount of twin primes, but there is no definitive proof.
Basically, for all prime numbers less than the square root of the number between two primes, it's easy to see that it is possible that their multiples could add up to either be on this middle number or at least more than 3 or more away. Pretty much the theory is only going to show that numbers that are a multiple of 2 and 3 are possibly between 2 prime numbers. Pick any number not a multiple of 2 and 3 and a number on either side will either be divisible by 2 or 3. I would assume that a proof could be extended through this by saying that there would have to always be another multiple of a prime number that happens to land one away from a multiple of 2 and a multiple of 3 for every number 2^x*3^y (for all x,y where 2^x*3^y>Q and 2^x*3^y is prime there exists a number z such that z divides 2^x*3^y+1 or z divides 2^x*3^y-1).
This is a little trickier considering it has already been proven that there is no number > than some number I can't remember at the moment such that it is divisible by all prime numbers less than it's square root. (there are no numbers that have both factors > it's square root... easily proven
With weird things like this going on with prime numbers it's hard to tell. Despite your obvious instincts that there should be a number x that happens to be a multiple of all prime numbers less than it's square root and still be large, it just isn't so.
Everytime you find something else about prime numbers, there is yet more questions about them. If this gets proven, the next logical step would be to prove that there are infinite number of prime numbers that are 2x apart from each other. If it gets disproven, we'll want to see exactly where it stops being true, and why. From there, we will only find more questions than answers
Karma Clown
From the Mercury News:
``Mathematicians described the advance -- announced at a conference in Germany -- as the most important breakthrough in the field in decades."
Oh, & proving Fermat's Last Theorem in 1995 was just another undergraduate exercise?
(For the non-math-nerds, proving true Fermat's Theorem -- that the formula a^n * b^n = c^n was insolveable where n is greater than 2 -- was considered for three _centuries_ to be _the_ principal challenge in mathematics. The man who did this -- Andrew Wiles -- spent about 30 years working on this, & succeeded only after a second try.)
Geoff
I think I see a trend here. Maybe for them it really would be easier to muzzle the entire internet than to produce p
Small gaps between consecutive primes
:= lim_inf(n -> +inf, (p_(n+1) - p_n) / log(p_n))) = 1
Recent work of D. Goldston and C. Yildirim
What are the shortest intervals between consecutive prime numbers? The twin prime conjecture, which asserts that p_(n+1) - p_n = 2 infinitely often is one of the oldest problems; it is difficult to trace its origins.
In the 1960's and 1970's sieve methods developed to the point where the great Chinese mathematician Chen was able to prove that for infinitely many primes p the number p + 2 is either prime or a product of two primes. However the well-known ``parity problem'' in sieve theory prevents further progress.
What can actually be proven about small gaps between consecutive primes? A restatement of the prime number theorem is that the average size of p_(n+1) - p_n is log(p_n) where p_n denotes the nth prime. A consequence is that
delta
In 1926, Hardy and Littlewood, using their ``circle method'' proved that the Generalized Riemann Hypothesis (that neither the Riemann zeta-function nor any Dirichlet L-function has a zero with real part larger than 1/2) implies that delta = 2/3. Rankin improved this (still assuming GRH) to delta = 3/5. In 1940 Erdös, using sieve methods, gave the first unconditional proof that delta 1. In 1966 Bombieri and Davenport, using the newly developed theory of the large sieve (in the form of the Bombieri - Vinogradov theorem) in conjunction with the Hardy - Littlewood approach, proved delta = 1/2 unconditionally, and then using the Erdös method they obtained delta = (2 + sqrt(3))/ 8 = 0.46650... . In 1977, Huxley combined the Erdös method and the Hardy - Littlewood, Bombieri - Davenport method to obtain delta = 0.44254. Then, in 1986, Maier used his discovery that certain intervals contain a factor exp(gamma) of more primes than average intervals. Working in these intervals and combining all of the above methods, he proved that delta = 0.2486, which was the best result until now.
Dan Goldston and Cem Yildirim have a manuscript which advances the theory of small gaps between primes by a quantum leap. First of all, they show that delta = 0. Moreover, they can prove that for infinitely many the inequality
p_(n+1) - p_n (log(p_n))^(8/9)
holds.
Goldston's and Yildirim's approach begins with the methods of Hardy-Littlewood and Bombieri - Davenport. They have discovered an extraordinary way to approximate, on average, sums over prime k-tuples. We believe, after work of Gallagher using the Hardy-Littlewood conjectures for the distribution of prime k-tuples, that the prime numbers in a short interval [N, N + lambda log(N)] are distributed like a Poisson random variable with parameter lambda. Goldston and Yildirim exploit this model in choosing approximations. They ultimately use the theory of orthogonal polynomials to express the optimal approximation in terms of the classical Laguerre polynomials. Hardy and Littlewood could have proven this theorem under the assumption of the Generalized Riemann Hypothesis; the Bombieri - Vinogradov theorem allows for the unconditional treatment.
This new approach opens the door for much further work. It is clear from the manuscript that the savings of an exponent of 1/9 in the power of log(p_n) is not the best that the method will allow. There are (at least) two possible refinements. One is in the examination of lower order terms that arise in his method. Can they be used to enhance the argument? The other is in the error term Gallagher found in summing the ``singular series'' arising from the Hardy-Littlewood k-tuple conjecture. There is reason to believe that this error term can be improved, possibly using ideas in recent work of Montgomery and Soundararajan (``Beyond Pair - Correlation''.)
It is not clear just how far this method can be pushed and what other problems might be attacked using his new ideas; at this point we can't rule ou
-Homer Simpson
Maybe we can use it to figure out this prime number thingy.
new encryption tech can be based on those new theories
And the terrorists will win! Quick, ban math!
Not so fast with the assumption that people protecting information can just automatically make use of new techniques. The idea with encryption is that you transmit your information over an insecure channel. This means that the bad guys already have copies of your information, encrypted using the techniques you used. If new techniques become available, you can't go back and use them on your old data, because it's already been transmitted. Therefore, in an arms race where cryptography and cryptanalysis proceed at equal rates, all the information you already own becomes increasingly vulnerable.
People (or agencies) holding a portfolio of critically sensitive information that has already been transmitted (and therefore probably intercepted in encrypted form) have a vital and sustaining interest in research into prime numbers. In many case their interest is in having such research stopped. It will be interesting to see what happens to super-smart but real-world-naive math Ph.D candidates if and when high efficiency factoring techniques become the subject of dissertations....
-Graham
There is a small missunderstanding here. The smallest gap between two primes is 1 (between 2 and 3). But there is only this one pair of primes (2, 3) with such a small gap. But the next smallest gap 2 happens several times, between 3 and 5, 5 and 7, 11 and 13, 17 and 19 etc.pp.
So the question is: Does this happen at very large primes too? Are there primes between 10^50 and 10^55 which are just 2 apart? Note that the primes get more and more seldom, if you move at higher numbers.
The mathematic society knows since a long time that the distance between two neighbouring primes p(n) and p(n+1) is smaller than log(p(n)). But log(p(n)) grows also steadily, even much more slowly than p(n).
The mathematic society knows also that surprisingly small gaps between prime numbers happen von time to time. So the best number known until now was that there is an infinite number of primes p(n), where p(n+1) - p(n) was smaller than log(p(n)) * 0,22... (which grows also, but very, very slowly...)
The breaking news is, that now the factor 0,22... got improved to 0, which doesn't grow at all.
That means: there is an infinite number of primes, for which (p(n+1) - p(n))/log(p(n)) is quite close to 0.
This means: There are infinite often pairs of primes whose difference is quite small... It could easily be that the difference is 2 for an infinite number of pairs, which is not proved yet, but at least the minimal distance of two neighbouring primes does not grow beyond a very low number.
Don't worry - the reason you don't follow what he's saying is because he's
karma-whoring and trying to spout something theat looks vaguely mathematical.
e.g.:
"""
Ofcourse, if there is indeed a usufull pattern, it may help to
find the primes---that are required for factorization---faster,
"""
Which is patent nonsense. Finding non-trivial primes is in no way required
for factorisation.
It's not required for trial-division (they're all trivial), pollard rho,
pollard P-1 (all trivial), williams P+1 (all trivial), ECM (all trivial),
shanks' squfof, the Quadratic sieve (all trivial), or the Number Field Sieve
(all trivial). Have I missed any? Oh yes I have - it's also not required for
Euler's algoritm, Legendre's algoritm, Fermat's algorithm, or Lehman's
algorithm. Nor for the Continued Fraction algorithm. There are some more
esoteric ones (Bach's cyclotomic technique, gaussian rings, hyperelliptic
curves etc) too, and they don't require it either.
All techniques apart from trial-division simply have the factors drop out
using a GCD of the composite number and the _difference between two elements_
in the ring of residues. The difference in the techniques is how you
generate the two elements that you are taking the difference of. You don't
actually generate the prime factor that will drop out at all.
THL.
Keeping
a) the cost to break it should exceed the value of the information it protects
and importantly
b) the time to break it should exceed the useful lifespan of the information it protects
So, hopefully, as the information that has already been transmitted over an insecure network becomes more vulnerable, it *should* also become less valuable because, quite simply, it's becoming old and useless. Ultimately, almost all cryto can be broken given the right amount of time. This is a given, and should be taken into consideration from the start.
Ummm, those piValue's are there because sin takes an argument in RADIANS. If Math.sin used degrees instead, that lines would be
All it is doing is psedurandomly generating an ANGLE and taking the sine of it to determine the X component of the needle's direction vector.Your comment reminds me of the people who saw
in Fortran programs and assumed that meant that on September 9th, 1999, all the Fortran code would stop working!ASCII stupid question, get a stupid ANSI
In the ring of polynomials with real coefficients, the units are the constants (zero-order polynomials), and so a polynomial like x+1 is considered "prime", although the term "irreducible" is usually used instead when talking about polynomials.
In the ring of rational numbers (which also happens to be a field), all non-zero numbers have multiplicative inverses, so all rational numbers are prime (in the rationals) making it a not very useful concept there!.
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?
I love mathematics (especially stuff like Category Theory, Lambda-calculi, etc...), but why does Slashdot always post number theory stories? You can try to view all of math through numbers, but you are missing out on allot of structure by doing so.
With RSA, I thought you wanted "strong primes," not just primes.
In general I don't think that is the case, but some special uses of RSA makes that requirement. The "safe primes" are harder to find because there is not that many of them.
But finding primes is a different task than factoring numbers. The algorithms for finding primes is a lot more efficient than factoring, if they weren't RSA wouldn't make much sense. There is an algorithm that will find a prime and a proof it is a prime, with a minor modification it will produce "safe primes". The proof basically consits of a factorization of p-1 together with a recursive proof that the factors are primes. The reucursion ends when you reach the prime 2, because p-1 will then be 1 and has the empty set as its prime factorization. There is a litle more to the proof than this, but in fact if you are just given a list of all the primes involved in the primality proof you can easilly reconstruct the entire proof.
But usually you don't need a proof, so instead you use a probabilistic algorithm for veryifying primality. You can write a very efficient algorithm that gives sufficiently small probability of ending up with a non-prime. If the probability that one of your "primes" is not a prime is as small as the chance of the attacker finding your prime by his first random guess, that is not a problem.
Do you care about the security of your wireless mouse?
"A hint of his sense of humor can be found on his Web site, which features a photo of Goldston, seemingly dozing off, as two small kids climb on his back. He and his wife, Ryoko, have three children -- Shota, 7, Aiko, 5, and Makoto, 3."
Can we can expect his next theorem to deal with prime triplets?
Here is a counterexample for your 'proof':
(2*3*5*7*11*13)-1 = 30029 is prime
(2*3*5*7*11*13)+1 = 30031 = 509*59 (composite)
If q is the product of a set of primes P, then q+1 and q-1 are relatively prime to each p_i, i.e.
(q+1) % p_i = 1, and (q-1) % p_i = p_i - 1. However there are no guarantees about the relative primality of q with respect to some prime p not in P.
If the p_i in P are consecutive starting with 2, then we do know that Q+-1 must either by prime itself, and thus larger than any prime in P, or a composite of 2 or more primes, each of which is larger than any prime in P.
Given the set of all known primes, we can always generate a new unknown prime, thus expanding our set, and therefore guaranteeing the set of all primes is infinite.
I'm giving the direct link.t ml
http://www.cse.iitk.ac.in/news/primality.h
Every triple of that form contains at least one number that can be divided by 3. If you want all numbers to be prime, the number 3 itself has to be among the three numbers, hence the triple 3,5,7, is the only one. (short idea of the proof, the full one would require a few more lines of text)
I intend to live forever, so far so good.