Slashdot Mirror
Turns out, Primes are in P
zorba1 writes "Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem."
Um, if you don't like nerdy stuff.. I hate to break it to you, but this might not be the place for you. :)
slashdot!=valid HTML
If I'm reading this correctly, we've got a nearly guaranteed winner of the Nobel Prize here.
the ps version looks much better:
http://www.cse.iitk.ac.in/primality.ps
// FIXME: put sig here
I don't know anything about theoretical CS. What's polynomial time?
Steve
Out of interest, will this finding have any impact on the effectiveness of present day cryptography?
For P, it has to be polynomial in the size of _the input_. The input size here is log(n) since it requires log(n) bits to represent n. log(n)^12 hence is polynomial (which i believe their algo guarantees), whereas sqrt(n) is not.
They could have easily taken over the infrastructure of a modernized computer-bent, encryption-shielded society such as the US or Japan. If that is indeed the case, these guys deserve a Nobel Peace Prize for giving this powerful tool to all and not using it as a weapon of war.
This does, however, sound unlikely. Any mathematicians out there care to comment?
What are you referring to as your input size n in O(n)? The number p? The correct size n is the number of digits of p. That algorithm is definitely non-polynomial for that (correct) n.
I am by no means a heavy duty math cruncher or cypherpunk, but how exactly is this going to affect number and factoring? I don't know of any advanced prime number search algorythms, but Sieve of Erothenes (did I get that right?) solved in NP time. (Each number is check is evenly divisible by an earlier prime, and if none found, add to list of primes, lather rinse repeat)If primes can be found in P time, finding the first 50 prime numbers would take the same time as finding the first 50 three hundred digit primes.
While that may not be thrilling at first, let's use the RCA contest for money as an example. We get a 1024 bit number containing 200 digits in decimal formm, which is the product of exactly two prime numbers. We know then that:
1. We only need to find one prime to easily find the other.
2. The digits in the factors can total no more than 200 digits.
3. One of the factors contains less than 100 digits.
Start at 10^100 and count down using this algorythm, and youll find it in P time instead of NP time. It'll still take forever, literally and figuratively, but wouldn't it take significantly less time than before?
Toodles
Toodles D. Clown
it's the only correct reply so far
...then you can bet the NSA has had this algorithm for decades.
Well, encryption based on the multiplication of large primes, anyway.
Yeah... that step in key generation where you check whether a candidate key is prime or not will now be performed with 100% confidence instead of that annoying 99.999999999999999% confidence we used to have.
-a
How to rationalize theft.
They're saying the the time T necessary to determine whether or not an N digit number is prime satisfies this equation:
T N ^ k + a
for some values (can be any finite value) of k and a.
Basically, it's a statement about how well an algorithm scales to REALLY large numbers.
hm... I'm not sure why it removes comparison symbols when set to plain text... oh well, I wrote out "is less than" this time
They're saying the the time T necessary to determine whether or not an N digit number is prime satisfies this equation:
T is less than N ^ k + a
for some values (can be any finite value) of k and a.
Basically, it's a statement about how well an algorithm scales to REALLY large numbers.
No, because find primes was classified as NP, 3-SAT and others are NP-Complete which are a "superclass" of NP problems.
They've figured out how to determine if a given number is prime in P time. That, by itself, doesn't break modern public key cryptographic systems. In order to do that, you would need to be able to factor a given number into its two prime factors in P time (a different problem).
preview is your friend
For those of you wondering about the implications for cryptography, this does not imply that composite numbers can be factored in polynomial time. This algorithm is simply a primality test -- that is, it tells you whether or not a number has any proper divisors (in polynomial time), but it doesn't tell you what these divisors actually are. Determining whether a number is prime has always been considerably easier than finding the prime factorization.
In fact, for schemes like RSA -- where the key is the product of two large primes -- we already know that the number is composite, by definition, so a more efficient primality test doesn't give us any new information.
Cheers,
IT
Power corrupts. PowerPoint corrupts absolutely.
This may seem like a strange question, but isn't a non-prime that passes the 99.99999999999% check just as good as a prime in encryption? I mean, seriously, is anyone really going to notice it's not prime? Sure, they could accidently stumble on the 'wrong' factors while trying decode it, but, seriously, halving the time to decode your message isn't a huge mistake, considering we're talking on the order of centuries at least. ;)
If corporations are people, aren't stockholders guilty of slavery?
From looking at the algo, I can't figure out what 'x' (or maybe it's a chi) is? Can someone help? I've looked it over, but couldn't find a definition of it. I'm also assuming that the 'if (r is prime)' line is a recursive call to itself? Also, how do we determine 'q' the 'largest prime factor of r-1' ? Another recursive call to get the factors? I must admit, I'm kind of lost by the algo, but it's still interesting.
Things you think are in the Constitution, but are not.
It's funny when I read the comments, and I see all kinds of stuff that reminds me of my Discrete Structures class (we did the P and NP stuff at the end)...
Makes me wonder what this means for computer theory, but if you think about it, polynomial time can still be slow for very large n with very big powers... although not as bad as an exponential with large n's (assuming you go out far enough that the exponential will grow faster then the polynomial)
Kudos to the team that discovered this
There are only 10 kinds of people in this world... those who understand binary and those who don't
Cracking any specific key-length is P, but cracking RSA in general remains NP, since that method requires checking a number of potential primes proportional to 2^(N/2) or so where N is the key size.
I'm dead tired and will look at the paper in the morning. But right now I have a problem with step 6:
"Let q be the largest prime factor of r-1"
Won't getting q boost the thing back into power n complexity?
look here.
If by "superclass", you mean problems that are (thought to be) harder than the other set of problems, then yes.
But technically speaking, NP-complete problems actually form a "sub"class of NP problems.
And yes, primes is not _known to_ be a NP-complete problem, so this doesn't really affect complexity of 3-SAT directly.
There are 2 different problems:
1) Determining if a number is prime [is 909 prime?]
2) Determining the factors of a number [what are the factors of 909?]
This article claims to be able to solve problem 1 in Polynomial time.
However, problem 2 is MUCH harder, and that is the one which will break cryptography as we know it. This article does not claim to solve problem 2, so we're safe for now.
Maybe, maybe not. If that non-prime happens to be 2^2031, I bet it'll make your encryption really weak. ;)
Uh, no. Just because you can tell whether a number is prime in polynomial time, doesn't mean you can find the factors of a number in polynomial time, as I understand it.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Aha... is that based on a precomputed sieve with 10^100 elements, by any chance? ;-)
(it's googol, by the way. Google.com is obviously not prime, based on the fact that they haven't IPO'd yet)
Thank you. I'm glad someone finally pointed out that we already have a classical (as opposed to quantum) probabilistic algorithm for determining primality. Every other fool on this board is running around wearing his/her tin hat and shouting about RSA being defunct. All this does is push primality testing from the BPP complexity class into the P complexity class. It is significant in the sense that it weakens the argument for BPP being larger than P.
Of course, we also have a polynomial-time algorithm for prime factorization (Shor's Algorithm). It's just that it requires a quantum computer, which is difficult to build. So far, the biggest number factored is 15... 1024 bit keys will be safe for a while yet. I believe it's 15 - 20 years until they're broken, if Moore's Law holds for quantum computers in terms of maximum number of qubits possible (so far, it roughly has, but then, we're only at about 7 qubits).
Ignore the parent post, since it is wrong. The previous poster did a much better job of explaining the concept of polynomial time.
An NP-complete problem does not take 8 times the age of the universe to solve. This completely missed the point. Every P or NP problem can be expressed in terms of a variable "n", which represents the input size. There are many practical problems where the best-known P algorithm is slower than the best NP algorithm for typical values of n. However, computational theory tells us that as n increases, the P algorithm will eventually beat the NP one.
-a
How to rationalize theft.
google v. [common] To search the Web using the Google search engine,
`www.google.com'. Google is highly esteemed among hackers for its
significance ranking system, which is so uncannily effective that many
users consider it to have rendered other search engines effectively
irrelevant. The name `google' has additional flavor for hackers because
most know that it was copied from a mathematical term for ten to the
hundredth power, famously first uttered by a mathematician's infant
child.
---------
googol
n : a cardinal number represented as 1 followed by 100 zeros
(ten raised to the power of a hundred)
There is a HUGE difference between the two.
Buying a Dell computer is equivalent to dropping the soap in a prison shower.
mathematicians have been pondering over that prob for decades.. if that works out we'll have fresh prespective of univ..(remember the pendulum, algorithmic univ theories)
Now, if you have a number n, you run this algorithm, say 20*log(n) times. If the algorithm says it is prime on all executions that it is prime, you know damn sure it is. If it says it isn't, you are sure it isn't. There is a rediclously tiny probablity that if the algorithm claims that it is prime in all executions, that it is still not prime. This probablity is so small, that it can be essentially ignored. Now, random bits are cheap nowadays, so this is quite satisfactory. This is in fact the algorithm that turned the RSA crypto system into a practical and useful algorithm, because suddently finding primes became easy.
To break RSA, and become really famous, one has to come up with a polynomial time algorithm for factoring. It might even be that RSA can be broken without factoring, but this is still an open question (I think).
Ahh, and BTW. Polynomial time means polynomial time in the size of the input. So if the number is n, the size of the input is O(log(n)), and the running time needs to be O( (log(n))^(O(1)) ).
Ok. End of boredom.
No, most messages will decode incorrectly.
Consider a simple public key encryption algorithm based on the fact proved in any beginning number theory book that for primes p, q
a^x = a (mod pq) if x = 1 (mod m)
where m = (p - 1)(q - 1)
Now choose your favorite number f and use Euclidean algorithm to efficiently find a number g such that
fg = 1 (mod m)
You may have to try another value of f if the Euclidean algorithm terminated before reaching 1, but it won't take many guesses. Now publish the number f and mod m as your public key and keep g private.
Someone sends text t to you by sending t^f (mod m).
Now you just raise that message to the power g and reduce mod m to recover the original text. (This follows immediately by combining the above statements).
Finally, I'll get to the point. This algorithm is simply busted if p and q are not prime because t^fg will not equal t mod m unless you are very lucky. In fact, if you want to add a bunch of nines to your percentage certainty, just encrypt and decrypt a sample message text and verify that it works.
You guys always say things like "so what?" or "that's old". C'mon guys, go outside and smile.
This result, if true, is very interesting from a theory standpoint.
As far as practice, it's fairly irrelevant. Probabilistic primality testing can be done in constant time with bounded error.
The Miller-Rabin test will tell you if a number is prime with at most 1/4 probability of error. That sounds ridiculous, but the catch is that you can iterate it using a random parameter. Do the test twice and your probability drops to 1/16. Do it fifteen times and your chances of being wrong are about one billionth.
If you're truly paranoid, do it 50 times. That'll bring the error rate of the algorithm magnitudes below the error rate of your hardware.
---
Dum de dum.
Freedom is not the license to do what we like, it is the power to do what we ought.
That "proof" would have killed my CS professor.
...that in praxis it doesn't really matter if problem is P or NP when P is 100000000000000000*n while NP solution could be 0.00000000000001*(2^n) - the complexity class is nice thing but not all.
Uhh..
Pardon my french, but isn't sqrt(n) is better than log(n)^12?
I hate replying to my own posts, but upon further inspection, I realized that sqrt(n) > log(n)^12 for large n.
Yet, sqrt(n) is still polynomial time.
Your are right i meant the first thing, thanks for the correction.
>I'm not sure why it removes comparison symbols when set to plain text...
Slashdot removes left angle brackets in an attempt to stop abuse. Since it still lets raw right angle brackets through for old style quoting (which I prefer), the left ones have to go on unverified tags.
To display a left angle bracket despite that you'll need to type its ISO code, which renders the bracket unusable for tags (which is a good thing).
ie: < is entered with this: <
Just something to note down FFR. Oh, and can be handy if you want to try to slip through some important, on-topic simple tables or ascii art. Sometimes. But not lately.
- o
<
\__/
If you could be told what you can see or read, then it follows that you could be told what to say or think - BoC
No. I was just using the fact that any algorithm is O(1) if you specify an upper bound on n.
The algorithm is:
Precompute Tmax = number of seconds to determine if a number near 10^100 is prime.
1. Compute if x is prime, taking T seconds.
2. Sleep for Tmax-T seconds.
3. Output answer.
-a
How to rationalize theft.
So I'm already sensing the level of confusion rising as this is a very confusing topic. Here's a quick review. Note: I'm going to do this on a higher level and not start talking about Formal Languages as this is not the place to teach it. So in loose terms, Problems that in P are easily solveable. For example, sorting is a problem in p. Proof: I can sort a set of n numbers in no worse than n^2 time using a bubble sort. (Yes - I know there's faster but this is an example). The bubble sort just compares every number to every other number. Assuming you didn't optimize the algorithm you'd compare each number to every other number and they'd be sorted in no worse than n*n = n^2 comparisons. So what is NP? NP are problems that given a proposed solution we can verify that the solution is correct or not in polynomial time. An example of this is factoring. (note: it is not known whether factoring is in P). Given current methods we know factoring a big number into its prime factors. But if I was to tell you that p=q*r you could very quickly multiply q*r and see if it is equal to p and "verify" my answer. Another way to think about it is you can try out one branch of computation in polynomial time. So what is NP-complete? NP complete problems are is follows. A problem is NP-Complete iff 1) The problem is in NP 2) A solution in polynomial time to this problem would yield a polynomial time solution to all other problems in NP. That is, no other problem in NP is harder than NP-Complete and if one NP-Complete problem is solveable in Polynomial time than all of NP is solveable in polynomail time, P=NP and you will win doctorates and a nobel prize, turing award and a million bucks from the clay institute for proving this. Sigh - you are probally still confused.. :)
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
a Proof is not rigorus if it depends on unproven theorems. There are many examples if theories that were thought to be true and were later proved to be false. This proof relies on nothing more than a little abastract algebra, some number theory and good ole plain algebra..
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
3-sat isnt it 3-cnf-sat? or is cnf typically dropped?
When in doubt, parenthesize. At the very least it will let some poor schmuck bounce on the % key in vi. (Larry Wall)
Firstly, you only need to check up to the square root of n as anything larger will not be a prime factor. Secondly the algo you suggest is MUCH larger than n^k where n is the LENGTH OF THE INPUT NOT THE SIZE OF THE NUMBER!
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
15 to 20 years is not a long time, I remember when it was 15 years to Y2K. It wasn't the disaster that it was beaten up to be, but it did cost a lot of money to remedy.
Encryption is pretty low level stuff, so the ramifications could be large for many systems.
Microsoft - Where would you like to go today, Maybe Jail?
Whether polynomial time is longer or shorter than prime time.
LedgerSMB: Open source Accounting/ERP
You can break RSA in polynomial time.
Let pq be a public key. For integers n sqrt(pq) check if n | pq. Each division takes O((pq)^1.58) time (see any algorythem book for proof).
So you have O(sqrt(pq)) * O((pq)^1.58) which is just slightly larger than O((pq)^2) and less than O(pq^3). Improving only slightly over brute force gets you down below squared time.
Someone posted above that the actual size of input, grows as log(n), so the actuall speed of the algorithm is sqrt(2^i) or 2^(i/2), where i is the number of bits in the input.
Play Command HQ online
I forgot to put in the punch line.
The problem is not that you can't crack RSA in polynomial time as the numbers grow, but rather that means that you are cracking RSA in exponential time as the number of digits grow. Incidentally the best you can do so far is O(e^1.58) (which comes from the division problem).
We give a deterministic O((log n)**12) time algorithm for testing whether a number is prime.
[Sorry, the Slashdot filter does not allow me to superscript the 12.]
The algorithm takes O(log2(n)**12) time, where n is number being factored. If we optimistically assume that this algorithm can test the primality of a 16-bit number in one microsecond, then here is how long it would take to test time primality of some larger numbers.
I don't know what a realistic base time for this algorithm really would be, and I don't know where the cross over point against existing exponential time deterministic primality testing algorithms would be, but at least this provide a sense of how log2(n)**12 grows.
The time it takes to calculate with a variation of this algo is ~ [(n + 1) / 2]! , no?
I thought that would be in P time but I see it cannot.
"Allez Cusine!"
umm...wouldn't it be easier to just loop from 2 to n-1 (n = the number you are checking for prime) and to see if they divide it?
and no prime * prime is not prime
Well, I'm not sure if you mean factorial or excitement with that exclaimation mark but either way thats much larger than the input size of the number. NOT THE CARDINALITY OF THE NUMBER. i.e. if a number has n digits it won't be poly to that!
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
I was refering to factorial.
"Allez Cusine!"
I was just suggesting a raw, non optimized algo for something like this. by z = n+1 ,z = z / 2 and then checking all products, which is z! but that ins't P time I see now so I'm sure many algo's like this already exist and are much slower than the P algo.
"Allez Cusine!"
I'm not sure what Primes look like or even what they are but having them in my P can't be good for the ole' prostate.
Factorial grows faster than exponential! watch: polynomial time: 2^2=2 3^2=9 4^2=16 10^2=100 Exponential: 2^2=4 2^4=16 2^10=1024 Factorial; 2!=2 4!=24 10!=3,628,800 See what I mean?
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
I think there's an error in your algo. Shouldn't it be t^f (mod pq) and message^g (mod pq)?
Bill - aka taniwha
--
Leave others their otherness. -- Aratak
"If you can determine if a number is prime in polynomial time, you can break RSA in polynomial time."
Awww fuck polynomial time.... I'm still waiting for somebody to determine it in STOP! hammer time...
Doooooooo doo doo doo, doooooooooooooooooooo do - Can't crack this!
---
God that was stoopid... sleeeep goooood!
Yes, and I realize this. To be honest, I have very little business discussing higer math as I am not *bad* at math but do not have the dedication to it. A couple years of Calculas is all I really want to ever have. I can derive and use integrals among other things.
:)
I like discrete math/logic more anyways,
Thank you for clarifing a couple things for me though.
"Allez Cusine!"
Um. Aren't they the same number ...) is a 1 followed by 100 zeros, just as 10**2 is a 1 followed by 2 zeros.
10**100 (10 * 10 * 10
Indeed, primality has been known since the 80's to belong to the class RP (problems solvable in expected polynomial time by a randomised algorithm). It has never (in recent years) been suspected of being NP-complete. Most experts don't even think factoring is NP-complete.
(All this assuming P!=NP, or else all these distinctions collapse.)
-Kevin
You have to escape < with <, because otherwise the parser wouldn't be able to tell when an element tag was beginning or you meant less than. > isn't required to be escaped for this reason, because it is clear whether it is closing a tag or not. You also have to escape the ampersand, because otherwise the parser would have to scan ahead to know if you were specifying an entity like or you just meant & and whatever.
No. Polynomial time, as was said, is polynomial in terms of the input. Input b bits and n is (worst case) on the order of 2^b so now sqrt(n) is about sqrt(2^b)=2^(b/2) which is far worse than polynomial in b.
Free Java games for your phone: Tontie, Sokoban
But I set it to plain text! Shouldn't slashdot automatically replace my (less-than) symbol with < or whatever?
Since slashdot doesn't seem to be doing that I feel like the mode shouldn't be called "Plain Old Text".
Ah well. I'm just bitter because I screwed up twice in a row.
There seems to be endless fascination with P vs NP problems, and I just can't understand how it could possibly matter. Aren't there infinitely many "polynomial times" that are complete disasters?
Isn't n^1000000000000000000 polynomial time?
Flat5
how long have you guys been waiting for a topic on prime numbers, it's like your entire lives have been building up to this point. hurray!
100% Pure Evil With The Look And Feel Of Wholesome Goodness
this work was done by undergrads for their senior honors thesis under Dr. Agarwal's supervision. Isn't that amazing!!! Dr Agarwal was also my undergrad advisor- he is one amazing fellow and damn smart too!! I just wish my honors thesis had been even a fraction of this...
log2(16) = 4
...
log2(32) = 5
log2(64) = 6
log2(128) = 7
log2(256) = 8
by your assumption a*log2(16)^12 + b = 1 ms
for simplicity, let's ignore the constant b.
then:
a*log2(16)^12 = a * 4^12 = 1 ms (by assumption)
a*log2(32)^12 = a * 5^12 = 14.5 ms
a*log2(64)^12 = a * 6^12 = 129.75 ms
a*log2(256)^12 = a * 8^12 = 4096 ms
___
If you think big enough, you'll never have to do it.
well ERH is a million dollar problem (literally) !! Claymath.org, so i wouldn't bet my money on a proof which relies on ERH.
Note that this algorithm takes O((log n)^12). For this to actually be faster than, say, factoring n directly, and assuming a multiplicative factor of 1 in the order statistic, n has to be at least 3*10^22, or roughly 75 bits long. This algorithm is probably very ineffective at factoring small integers.
This post expresses my opinion, not that of my employer. And yes, IAAL.
Oops! But with your correction, it works.
15 - 20 years until they're broken...
Hmm... you know, I've been thinking... if anyone actually saves some of those packets floating around on the 'net, it my be possible to decrypt ALL of them in that time frame. In other words, even if it's encrypted, be aware that it may not be secure for the remainder of your life, perhaps much, much less. I wonder if I'll have the same credit card numbers in 15 years. Alternatively, I wonder if anybody will think about this more than a year before it's possible.
Another interesting case where it's faster to wait for the hardware than to start chugging away with what we've got right now.
sig fault
Assuming you meant "wouldn't call", division is definitely "considerable". Remember we are talking about large numbers. Try doing long division on paper for 35184535666823 divided by 4194319 (answer is 8388617) and you can see there is some work involved, even with these small numbers.
The paper method of long division is O(n^2) and it turns out it can be done more efficiently: As I understand it, you can do division in the steps required for multiplication. Therefore the number of operations required to divide two n digit numbers is bounded by the best multiplication which is O(n lg n lg lg n) (from Knuth Volume II).
This is about 57 for 10 digits and about 182 for 20 digits. You can see that doubling the number of digits here more than triples the required number of operations to compute this result! Likewise 30 digits require about 6 times more operations. You can see that the "n times" grows faster than the number of digits. Thus, division gets slower and slower the more digits you have to divide.
-Kevin
A single iteration of the Miller-Rabin test does not take constant time. The time taken involves a number of multiplications mod p (mostly repeated squaring). Both the number of math operations and the difficulty of each one increase with p.
It is therefore polynomial in the size of p, and not constant.
Oops! Yes, this is completely true. Anything that involves multiplications is obviously not going to be constant in the size of the input.
I should offer my head on a platter to Prof. Rabin! I took his class on randomized algorithms...
(If I wanted to be petulant, I could blame the Motwani & Raghavan book for modeling multiplies as unit cost, but that ain't gonna fool anyone. =)
---
Dum de dum.
Freedom is not the license to do what we like, it is the power to do what we ought.
-Kevin
I'm not sure what you meant by that last line, but you're wrong. Your argument is the converse of the argument made, which doesn't follow.
Your first sentence is wrong. Your second sentence is correct, but unrelated.
:-)
The fact that you know the factors of a prime doesn't tell you anything about what you know about the factors of a non-prime (unless you know the prime to be a factor of the non-prime, of course).
When being pedantic, you'd better double-check that you are right
The Tao of math: The numbers you can count are not the real numbers.
On the MaxOSX it looks great (I'm guessing they use the Mac's native font rendering), but on my XP box it looks like something from the mid 80's compared to the cleartype that everything else is done with.
don't get me started on the ActiveX control...
I thought things that sounded the same but were spelled differently were homophones. I thought homonyms were spelled the same with different meaning.
YOUR NIT HAS BEEN PICKED!!!
or
). But since you can still type, say, , or in plain text mode, it can't automatically translate your '<' into '<', or else those tags wouldn't work.
What you want is to either type out the '<' and '&', or, probably what you really want is to:
use Extrans or Code modes (Code is just like Extrans except formatted in a fixed-width font). I'm using Extrans to type this message right now, since it has so many '<'s.
The PRP tests used to check numbers for compositeness or probable primality
actually test to see if this exponentiation procedure works.
RSA does work with carmichael numbers instead of primes, for example, because
a^c == a (mod c) for all a s.t. (a,c)==1, c a carmichael number
Try it - it works!
Phil
Also FatPhil on SoylentNews, id 863
...if he HAD found a way to do factoring in P time... gotta wonder what would happen if he took a holiday to the states - I'm sure SOMEONE would try to have a go at him for breaking encryption
Yup - cracking 128-bit AES by brute force is O(1) too, because the key size
is fixed at 128 bits.
Phil
Also FatPhil on SoylentNews, id 863
It will only be a matter of time before somebody finds a flaw in the paper. I suppose I will give it a bash.
First of all, to the best of my knowledge, none of the prime algorithms are NP-complete, so even showing that one of them runs in polynomial time will still not answer the question of whether P = NP.
Second, as some other readers have pointed out, this will probably not make a dent in the integrity of crypto systems, since the factoring problem becomes no easier. Take RSA for example. We know that the messages are composite numbers, but I bet you'll keep your computer more than busy for the next few eons trying to factor a 1024 bit composite.
There is a brilliant probabilistic algorithm (due to Rabin and I think Miller) for checking primeness which allows one to arbitrarily choose the likelihood of an error.
So anyways, don't get to excited at the prospect of the fall of the Western world's security, because if anyone posed such a threat, it would be in the interest of many countries to have such a person eliminated.
"I hate people who fabricate unintelligent quotes to add to their work seemingly by some 'anon' sage" -- anon
NP-complete problem are no superclass of NP, but they are considered to be the hardest problems in NP. "The hardest problems in NP" means that if one finds and deterministic polynomial algorithm for a NP-complete problem, you could use this algorithm as a subprocedure for any problem in NP (every instance of a problem in NP can be reformulated as an instance of this NP-complete problem in det. pol. time) and therefore P=NP.
But it is more likely that there exists no det. pol. time alg. for any NP-complete probleme and so P != NP)
No, most messages will decode incorrectly.
So, if the key obviously doesn't work, then you can assume that the modulus isn't prime and try another.
In fact, following that argument through, you could have a test suite of various messages to encode. If they work, you can be reasonably sure the number is prime. Obviously, with this approach you'd need to be reasonably sure you had a prime, otherwise you'd waste a lot of time.
Disclaimer: I dropped out of Uni level Maths before I got to anything particularly hard, so most of this is over my head.
-Kevin
While I haven't gone through the presentation in detail,
I wrote a paper back in 1990 about a prime number sieve that was basically an O(n^2) algorithm.
It basically worked by finding out if numbers were composite, but the algorithm used could be "inverted" to tell you if a number was prime or not by telling you if it was composite or not.
It was very well suited to parallel implementations, too.
"Sometimes the truth is stupid." - Lawrence, creator of Prime Intellect
Ah you know most people who use the pair key system of encryption never have to worry about whether primes are factorable or not..
Single key encryption is only for windows slobs!
PGP forerver!
Don't Tread on OpenSource
Is there a reason why the underlining in PDF is out a fair bit?
It would be a truly horrible test for prime numbers if any even number greater than 2 passed.
From a theoretical point of view.
As someone who's incredibly interested in theoretic computer science, this is a fascinating and very important result.
Practically it may not have much of an effect. It is in P, but that doesn't tell you how long it actually takes to run. It could be that the algorithm takes an inpractical time to run, although refinements to the algorithm might be made to speed it up.
This will also have little impact on the problem of factoring, unless the maths used provides a new approach to that problem.
Great news though.
I'll have to read the paper now.
cause you're going back to P. Didn't you hear professor? You do the trying, we do the dividing.
Only ... algorithms like RSA will be broken. Symmetric-key cryptosystems will be unaffected.
As far as I know, public key crypto based on a discrete logarithm will be unaffected as well.
Will I retire or break 10K?
Yeah what the hell is this intelligent discussion. Lets go back to "Linux is uhh cool teehee". Or how about "Cowboyneal sure has a big hat, yup".
The input size here is log(n) since it requires log(n) bits to represent n. log(n)^12 hence is polynomial (which i believe their algo guarantees), whereas sqrt(n) is not.
Nonsense. Sqrt(n) is less than n for all n, therefore O(sqrt(n)) is even better than O(n).
for i = 1 to sqrt(n):
if i divides n: n is NOT PRIME, stop.
if loop runs to exhaustion, n IS PRIME.
Now, this simple minded deterministic algorithm has runtime O(n^0.5). Thus primality is in P. Why is this simple, elementary result unknown to slashdotters?
The true achievement of this paper is that a speed up from polynomial time to fast polynomial times. That primality testing is in P, is KNOWN FACT. All those people expounding on the ramifications of Primality being in P and its implica5tions for factoring are talking out of their ass.
As others have pointed out, n is the size of the input, i.e. the number of bits representing the number. A number that requires e.g. 20 bits to write (i.e. has a 1 in the 20th place) would then be between 2^19 and 2^20 (if we start counting at 1, so the 20th place corresponds to 2^19). Thus the input for p has size approx. lg2 p and so the for loop requres sqrt(p) ~ sqrt(2^n) = 2^(0.5 n) steps. This is exponential time.
You must always be careful not to confuse the size of the input with what it represents.
John_Chalisque
Whatever idiot modded me as "off topic" doesn't know ANYTHING about complexity and p/np. 3-sat doesnt exist. its 3-cnf-sat 3- conj. normal form - satis. problem.
When in doubt, parenthesize. At the very least it will let some poor schmuck bounce on the % key in vi. (Larry Wall)
There is a lot of extraordinary undergraduate research being done in the United States. For two obvious examples, look at the work done by the students of Feank Morgan and at Harvery Mudd College
Matthew Kudzin
I wonder if I'll have the same credit card numbers in 15 years.
My CC company tends to send me a new one every few years (right before the old one expires) with a new number. When does your card expire? What does your CC company do around that time if it doesn't send you a new number?
Wheeeee
Indras> It's always easy to tell if a number is divisible by three, just add all the digits together, and if the result is divisible by three, then so is the original number.
:) but here are a few exampes that should satisfy your curiousity.
HaeMaker> Got a proof for this?
You need to use these few Number Theory modulas rules:
Eq 1. m mod m = 0 [defn. of modulas]
and
Eq 2. (a mod m) + (b mod m) = (a + b) mod m
and
Eq 3. (a*m) mod m = 0
If you want a better handle on where Eq. 2 comes from, look at an analog clock.
i.e.
What is 11am + 9 hours expressed in am/pm format?
= (11+9) mod 12
= (12 + 8) mod 12
= (12 mod 12) + (8 mod 12)
= 8 pm
Similiarly for Eq 3.
The reason why (X mod 9) and (x mod 3) are interesting is because anytime you have 10 mod X = 1, you can use some mod tricks.
0 mod 3 = 0
1 mod 3 = 1
2 mod 3 = 2
3 mod 3 = 0
4 mod 3 = 1
5 mod 3 = 2
6 mod 3 = 0
7 mod 3 = 1
8 mod 3 = 2
9 mod 3 = 0
10 mod 3 = 1
INANT (I'm not a Number Theorist so please correct me if any of this is wrong!
Now 909 mod 9 is:
= (900 mod 9) + (9 mod 9)
= (100*9 mod 9) + 0
= 0
Lets try 911 mod 9:
= (100*9 mod 9) + (11 mod 9)
= 0 + (9 mod 9) + (2 mod 9)
= 0 + 0 + 2
= 2
and 974 mod 3
= (300*3) + (74 mod 3)
= 0 + (24*3 mod 3) + (2 mod 3)
= 0 + 0 + 2
= 2
Cheers
It's the Sieve of Eratosthenes. A number n is of size log(n). This is a deterministic algorithm; why bring up NP? What is the time complexity of division? And here's a hint: you start with n-digit (n=100) numbers and present an algorithm that runs in time 10^n. This is in P?
Has anyone actually read the paper? The algorithm is outlined, with a complexity analysis. Don't forget, P-time doesn't mean usable.
Unlimited growth == Cancer.
> Probabilistic primality testing can be done in constant time with bounded error.
You don't really mean constant time. Just looking at the number is already linear time!
Miller-Rabin is also polynomial time (admittedly, a much better polynomial than this).
I went to school with this guy at IIT, Kanpur. He is smart, and had a great advisor, Somnath Biswas for his PhD. Looks like IIT,K did away with their policy not to hire people educated at IIT,K, since he is a professor there now. Maybe they made an exception.
charmer
I know its bad netiquitte to reply to one's own post, but I can clarify the proof in a much simpler way:
When given a decimal digit d (equal to 0 thru 9), what is: d * 10 mod 3 equal to ?
Using our mod rules:
= (d*9 + d) mod 3
= (d*9) mod 3 + (d mod 3)
= (d*3*3 mod 3) + (d mod 3)
= 0 + (d mod 3)
That is, any digit times 10 mod 3 is equal to that digit.
Similiarly we can extend this to any power of 10.
e.g. d * 100 mod 3
= (d * 100) mod 3
= (d*99 mod 3) + (d mod 3)
= (d*33*3 mod 3) + (d mod 3)
= 0 + (d mod 3)
We can use the same proof for when finding d*10 mod 9.
So, using our previous example:
What is 974 mod 3 = ?
= (900 + 70 + 4) mod 3
= (900 mod 3) + (70 mod 3) + (4 mod 3)
= (9 mod 3) + (7 mod 3) + (4 mod 3)
= (9 + 7 + 4) mod 3
= 20 mod 3
= (2 mod 3) + (0 mod 3)
= 2
The local expert says that the buzzword in the crypto community is that the algorithm is apparently correct. The fact that is so elementary makes it less likely to be wrong.
We will have to wait a few days to be certain...
The authors also conjecture that if certain things are true, the algorithm could be changed to an O(logn**3) algorithm, which would be quite practical, perhaps competitive with the probablistic tests.
In practice, most public-key crypto algorithms formerly used 512-bit or 1024-bit keys, and are tending to do 2048 bits today. A few paranoids use longer keys just because they can, but 2048 is generally believed to be good enough. Existing factoring technology has cracked 512-bit keys, and I think the longest successful crack is about 640 bits. Dan Bernstein's factoring machine proposal has led some people to abandon trust in 1024-bit keys, though other people think that's premature.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
We can easily do this:
x is Prime in question
P is set of all primes
if ( x elemOf P ) Then
output X
end if
Duh.
You probably got confused by the quoting of the posting from streetlawyer I answered to. The italic stuff is actually what he quoted from ipfwadm.
;-)
His (streetlawyer's) first sentence is "No it isn't.", which is wrong, because the statement of the quoted sentence is correct (as you yourself re-state).
And that his second sentence it correct, we agree anyway
The Tao of math: The numbers you can count are not the real numbers.
From the paper:
<i> In 1983, Adelman et al achieved a major breakthrough by giving a eterministic algorithm for primality that runs in (log n) ** O(log log log n) </i> <br>
in contrast, this paper suggests an algorithm that runs in (log n) ** 12, which means that the 1983 algorithm would run better for numbers less than:
<strong>
n = (2 ** (2** (2 ** 12)))
</strong>
-- charmer
Just think... all this time spent by mathematicians, and it turns out that urologists are the ones who find the primes!
I thought the division problem was already an O(nlgn) problem, as product is.
There is already an algorithm which can find out if a number is prime or not, and has been around for some time. Or, at least, it can say that a number is "probably" prime. And, if that probability is, say 2^400 - 593, (i.e. 0.9999999...), then in practical terms this is good enough. When you get to probabilities that are so high that computer component failiure is more likely, it ceases to matter that the solution isn't quite perfect.
Discovered by Micheal O. Rabin, it depends on the notion of integers being a "witness". If one witness number can be found, the number is not prime. According to theory, if the number is not prime, then more than half of the integers in the set {2, 3, ... , n - 1} are witnesses. So obviously, the more numbers tested for "witness capability", the lower the chance of the number being prime.
A witness number is defined to be any integer w satisfying either of the two conditions below:
So this discovery, is not, in fact, anything that will lead (at least directly) to anything new at all.
Why doesn't some Math's dude just make a massive, and I do mean massive prime nubmer database??? There are lots of people who love putting terabytes of data into databases why not do it with something useful like Prime numbers???? Then have it avialble on-line. Lets really test the limits of MySQL.
Well, Prof. Manindra Agarwal is an established theoretician and is the "first" author of the paper.. When several authors contribute nearly the same research in a paper, the tradition is to list the names in alphabetical order (last names). These authors - Agarwal, Kayal and Saxena seem to be that.
>>>Well, Prof. Manindra Agarwal is an established theoretician and is the "first" author of the paper.. When several authors contribute equally in a research, they are listed alphabetically. Agarwal, Kayal and Saxena seems like that.
Everyone in slashdot drops his name, but you, sir, have quoted from his books.
Therefore, you have the largest hoodaddy in the thread.
(My time between girlfriends is polynomial)
http://pcblues.com - Digits and Wood
Ah you know most people who use the pair key system of encryption never have to worry about whether primes are factorable or not..
I'm working more on the physics side of quantum computing, not the computer side, so I don't know quite as much about crypto as I'd like. I can see how it might be possible to have perfect forward security (which is what you're talking about) in a real-time two-way communcation scenario, but not in a one-way asynchronous situation like PGPed emails.
Can you elaborate? I couldn't find anything with a Google search.
In fact, both of these problems are at most O(n), and can be solved the same way.
For each in test n%i=0. if there exists a i such that n%i=0 then the number is not prime. If you're trying to factor a product of two primes, then you've found one factor (and the other is easy to find:).
In fact, the fastest algorythm that we've discovered for factoring a product of two primes is O(sqrt(n)). The problem is that 'n' is so big---1024 bits (oh for a constant time algorythm:)
Anti-disclaimer: I did indeed take a cryptography course a few years back.
Tim
Carpe post meridian
Your worst case performance is going to be rather crappy :)
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
A few years ago, they only updated the date. They changed the number on my most recent card because they added some digits, no idea if they're going to change it next time.
The point was less about my CC specifically, and more about "which numbers have I sent across the 'net that I'd rather nobody know?" I'm sure there are a few, from vital things to personal information that is supposed to be confidential.
sig fault
no single letter variables... it's a stupid practice and anyone who condones it is an asshole.
p ; myLoopCounter++)
FFS, anyone who has a rule that you're not allowed to use i as a loop counter deserves to be dragged out into the street, beaten around the head with printouts of the Win95 codebase, then exiled to Redmond for the rest of their life, as they obviously aren't familiar with even the most basic of accepted practices.
I can just see you sitting there, late at night, typing
for (myLoopCounter=1; myLoopCounter<=maximumIterationsAllowedForThisLoo
while the rest of us are in the pub. Ah well, your loss.
nuff said
Best Slashdot Co
You can have perfect forward secrecy for dynamic communications, but the standard perfect forward secrecy algorithm (Diffie-Hellman) can also be cracked by a quantum computer.
-a
How to rationalize theft.
YM NTM/DTM, not NFA/DFA.
I mean that, aside from the mathematics, for full-time crackers and coders chunks of the number line might have a kind of political geography, with sections of the naturals known or believed by insiders to contain primes used by this intelligence agency or that surveillance group for this or that kind of encryption. The task might be ridiculously huge overall, but in local regions of the naturals, sections of suitable keys for some applications or machines might seem worth mapping, in someone's view.
In that context, surely a new classical primality test [especially if used to develop an improved probabilistic primality test] might make quite a difference, indirectly, to helping someone much more quickly factor large composites, no?