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."
News for Math Geniuses, Algorithms that matter?
"All I can tell the "lesser of two evils" folks is that if they keep voting for evil, they'll keep getting evil."-Lp.org
If I can find primes in polynomial time, can I do 3-sat in p too?
I can tell if a number is prime via:
bool isprime(p)
for i = 2 to sqrt(p)
if p mod i == 0
return false
endif
endfor
return true
endfunc
If I'm not correct, that algo is O(n), thus polynomial, thus in P. But for very large p, that algo is impractical.
Things you think are in the Constitution, but are not.
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?
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?
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
Bah.... so what? I have developed an algorithm that will determine if any number less than a google is prime in O(1). Above a google it degrades pretty fast, though.
-a
How to rationalize theft.
Does the eating of asparagus affect the presence of primes in P?
Inquiring minds want to know!
...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.
which equation?
ok so you can tell if soething is a prime pretty quick. Does this help you factor large numbers pretty quick? It's been a while... or else what is the point...
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.
I haven't seen the paper yet (slashdotted, go fig), but I'm guessing this doesn't have a big bearing on crypto systems or factoring. As the poster wrote, the algorithm is not optimized, and I imagine that it's _very_ inefficient. While P is faster than NP (for the most part), P!=Fast .... this algorithm could be polynomial on the length of input and still be exceedingly slow. Don't buy that quantum cryptography PCI card yet :-)
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).
It doesn't let you factor large numbers. This paper is almost purely of academic interest.
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
NP-complete problems form a subclass of NP problems.
You don't get it - the whole RSA algorithm is based on the difficulty of factorizing large numbers. If you can determine if a number is prime in polynomial time, you can break RSA in polynomial time. The factor might of course still be impractically large, but such a result would be sensational if true.
Now, on the other hand, I would rate the probability that this article holds to 0.1%....
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.
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?)
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.
plzdiekthx
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.
my contact lenses are sticking to my corneas.
I was about to mod you up ... but then I read your sig. Anyone with a sig about moderation needs to be bitchslapped.
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.
...couldn;t you figure out if a number is prime by taking the number you want to see if is prime, start at 2 and muliply that by every number until it is greater than the number you want to see if is prime, if not then go to 3 and repeat until a number * 2 > than your number?
This isn't elegant but I'm assuming it would work. I'm not a math wiz, only some calculas but could someone tell me why I'm wrong?
Also, that is in polynomial time I beleive.
Also, is the product of 2 primes always prime?
Thanx.
"Allez Cusine!"
>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
Even worse is a polynomial time algorithm that runs in O(n^1000000000000000). Even O(n^1000) is quite bad.
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?
Factoring primes is going to be found to be in P, and all over the world, dead slashdot readers will also be found in pee.
This is old news (1997). If one looks at TAOCP Volume 2, third edition, page 396, there are three mentioned algorithms. One algorithm operates at O(log n)^5, proves with rigor, and depends on the proof of the extended Riemann Hypothesis(tm). There is also aother that is in (log n)^O(log log log n) that does not depend on unproven hypothesises, yet is not exactly P.
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?
it's algorithm, fuckface.
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.
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.
I haven't read the PDF (Acrobat for Linux doesn't render it for whatever reason), but this sounds like it would be a good thing. RSA already does a quick check to see if generated key is prime. If this is more efficient, maybe this would make keys faster/more secure?
Preview is *MY* friend.
FAPFAPFAPFAP
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.
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!
Randomized polynomial time is NOT the same as polynomial time. In the CS theory literature, it is not known if RP=P (randomized polynomial time = polynomial time).
./ when stories that require any amount of CS sophistication is required. All the people who've never taken a theory course come out of the woodwork, and spout their own beliefs as if they were liquid gold.
I love reading
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.
but the rest of it is a mess.....
Step 6: Let q be the largest prime factor of r-1
Step 7: ???
Step 8: Profit!
big deal. corners of my mouth move. so what? I did that with linux years ago.
the guy admits he has no idea what he's talking about; it may by an ignorant question but it's hardly a troll!
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
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.
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.
If you're going to try to be funny, please be successful at it.
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.
You'd instantly know that 2^n, n>1, is not prime anyway.
What a long, strange trip it's been.
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
No it isn't. If you know that X is prime, you know that its factors are 1 and X.
Yes, I know, I know.
-- the most controversial site on the Web
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...
It turns out that both Kayal and Saxena are undergraduate students, and the result is developed out of their final-year project thesis. When was the last time that a Senior at a US university produced a result of this calibre? Answer: Never been done.
Computer Science at IIT, Kanpur, incidentally, has traditionally been the most difficult course to gain admission into in the IIT system. About 250,000 applicants write a grueling entrance test (the JEE) to get admission to about 30~40 seats in CS/IITK.
Finally, a result to make all that selectivity worthwhile.
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.
What is 'n'?
Hehehehe
Is it the total of bits of the number?
Or is it the number?
Stupid demonstration.
JCPM
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
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
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.
Did it occur to you that Microsoft might not want Adobe to have a decently-rendered universal document format on their platform? This is, after all, Microsoft -- the company which changes the .doc format every chance they get in order to enforce an artificial monopoly.
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
I don't care what they say - i, p and other one letter variable names suck even for loops. Get another job because you're a loser.
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 polynomial-time like Hammer-time?
Invoicing, Time Tracking, Reporting
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?
And
"
As for hyperlinks, it would be nice to have them in a "Plain Old Text" mode, but I've never seen anything I'd refer to as "Plain Old Text" include clickable hyperlinks. I think ideally there'd be a third mode, but maybe I'm just a dreamer.
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).
That's very rude and racist too. Someone mod this down
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 has been pointed out, Rabin-Miller is how one finds primes in practice.
Even Adleman, Pomerance, and Rumely's deterministic algorithm runs in time (log n)^{O(log log log n)}. That's not polynomial, but it's pretty nice. Contrast to this, which is (log n)^{12}. Now, 12 e^{e^{e^{12}}}, which is an absolutely huge number (perl thinks it's close enough to infinity for it).
Conclusion: This is really cool, but not yet practical. However, as the authors say, it may be possible to improve the bounds.
Anything can be cracked in hammer time... provided a big enough hammer.
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.
You have to go out "far enough" in the exponential because N^x+1/(x+1)! > N^x/x! you have to keep going until N/X is negligable. Exp(a*N) always grows faster than N^n regardless of how small a is (a>0)
> 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).
It's the first sensible post in this subthread.
It's illustrative of a common phenomenon in mathematics. We've known since Goedel that mathematics isn't completely decidable, and we've known since Chaitin that mathematics is even "almost all" undecidable. Yet the fact remains that most problems we are actually interested in seem to be tractable.
So while it's easy to prove that there are problems that can't be done in less than O(n^1000000) time, empirically such a problem never seems to be a worthwhile or interesting problem. The division between polytime and exptime has proven to be a good one in practice even if it's theoretically possible to get a really bad polytime algorithm.
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
Let's take a count:
/theoretical CS major to assimilate exactly how it works.
How many could go beyond Lemma 3.1 ??
My guess is that, it would take atleast a week for even a math
That seems to work. Is there a proof for it? If there is a proof, does anyone have an argument why this isn't polynomial.
While it's convenient to think of it as meaning "non polynomial" it really means nondeterministic polynomial. That means it can be solved in polynomial time but only on an NFA (as opposed to a DFA).
I'm not sure you you are complaining about. He raised a valid agument and supported it with facts. I see no problems in the post by the post by the "pedantic ass".
The first sentence is correct. If there is an error please state what it is. The second sentence is also correct. He is absolutely right about factorization not being the same as knowing primality. Actually there have been fast algorithms for determining primality for years. How do you think all these crypto programs generate primes to use in the keys? The difference is that the older algorithms are statistical in nature and this new one is not.
Interesting idea but there are two problems.
1) There are a _ton_ of 100 digit prime numbers.
2) There are already very fast algorithms for determining primality. How does that jive with the publication of this paper? The algorithms are current statistical. i.e. we are 99.999% certain this is a prime. The new algorithm is not. For your application 99.999% might be good enough.
damn fine joke.
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
It *is* still NP. It has still not been determined whether P and NP are separate sets (P is a subset of NP, but they may be equal), so factorization will always be in NP, unless someone discovers a P-time algorithm for an NP-complete problem (and thus proves that NP and P are one and the same).
. html
Definitions:
P: Problems that can be solved in polynomial time. ("P" stands for polynomial.)
NP: Stands for "nondeterministic polynomial time" (NOT non-polynomial) where nondeterministic is just a fancy way of talking about guessing a solution (A quantum computer could solve an NP problem in P time, because quantum computers are nondeterministic in nature. I beleive a paper was written recently stating that P=NP in the realm of quantum computing). On a more readily accessible level, an NP problem is one that can be verified given a certificate (solution) in polynomial time.
For a bit more info, see:
http://www.ics.uci.edu/~eppstein/161/960312
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.
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
I thought the division problem was already an O(nlgn) problem, as product is.
Of course, one should note that not all computer or math theories map equally well onto real-world problems. Some of them fit nicely. The halting problem is a good example of one that doesn't.
In the case of the halting problem, the key to its solution is recognizing that a program's semantics are only known when you examine it in the context of its environment, something which theoretical computer science often ignores.
Computers are finite state machines, with deterministic state transitions (hardware bugs notwithstanding). If you really wanted to do so, you could definitively determine whether a program would halt by exhaustive testing. Run it once. If the system has twenty trillion states, it can take at most twenty trillion minus one instructions to either A. repeat a state (in which case the program will not halt) or B. halt.
That's an extreme example because the number of states is mind-boggling in most systems, but a good approximation can be achieved by looking at only the different states in certain components (e.g. certain registers, RAM, etc.), and by limiting the problem domain, you end up making the solution easier.
In certain cases, public key encryption can be cracked trivially. PK encryption has pattern weaknesses and short data weaknesses that can be exploited. The fact that you can't recover the private key doesn't always mean you can't recover the encrypted data.
Again, if you limit the domain of the problem, it often ceases to be a hard problem. The real question then becomes how one could limit the complexity of breaking RSA. There's a lot of work going on in that area, as I recall. It will certainly be interesting to watch.
120 character sigs suck. Make it 250.
This is so pathetic. Every time any cs-theoretic problem is mentioned on /., everyone comes out of hiding clamoring for people to explain the issue, asking for an explanation P and NP, or making grand statements based on nothing but an undergraduate math background, if that.
Get a clue. Using google is much more useful than being a leech and expecting other people to explain everything to you. These threads can be condensed down to a handful of useful and funny comments. The rest of you should STFU and read a book.
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.
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
So primes are in p, huh? Maybe that's why it tastes the way it does.
Seeing as how Adobe is the one that attacked Dmitry Skylarov, maybe we shouldn't be encouraging use of their products anyway.
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
Then what's he doing with that "Jump to Conclusions" mat? ;-)
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.
Our code base has a very, very, very low bug rate and no one is ridiculous enough to create such an assinine variable name.
i doesn't mean shit to anyone, and therefore is a crappy name for a variable. The fact that you buy into the age-old adage that you can use crappy names for loop variables indicates you don't have the ability to think for yourself.
Find a new profession.
I read this and could tell right away this guy was a moron. I've seen his type before. He has a minimum extreme and a maximum extreme and doesn't believe in anything else in the middle. The fact that he thinks that "i" and "maximumIterationsAllowedForThisLoop" are the only two options brings home that he is a junior programmer (or never progressed up to that level).
Also, not everyone programs in C/C++. He assumes you do - another indication of "black and white thinking". While he's at the pub, I'm sure you and yours are producing quality code.
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?
I wrote a little FAQ that answers allot of the questions that were asked here, and resolves allot of the misconceptions. You can read it at http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.h tml
Enjoy!
--Anton