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."
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
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.
If I'm reading this correctly, we've got a nearly guaranteed winner of the Nobel Prize here.
This would be more in line for a Fields Medal than a Nobel Prize.
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
What category? Unfortunately, there's no mathematics Nobel Prize. I realize that they consider applications, but I don't see many in physics, chemistry, medicine, economics, peace, or literature.
...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.
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.
They could have easily taken over the infrastructure of a modernized computer-bent, encryption-shielded society such as the US or Japan.
Primality testing and factorization are not one and the same. It is possible to know that a number is not prime without knowing its factors. Breaking encryption requires factoring the product of two huge primes (it is already known that the number you're trying to factor is NOT prime, so Primes being in P is more or less useless by itself for this particular application), and factorization has yet to be shown to be in P.
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.
Out of interest, will this finding have any impact on the effectiveness of present day cryptography?
Probably not. While it is possible that this research could lead to results in speeding up factoring, a faster algorithm for determining whether a number is prime is not going to compromise the security of RSA.
Your RSA key pair is derived from 2 large primes. The way we generate keys is to randomly test large random numbers to see if any of them are prime. Ergo, we must already have an efficient formula for determining if a number is prime or not.
FYI, the most commonly used algorithm is Euler's formula. Euler's formula doesn't actually tell you if a number is prime, but it will usually give a non-zero output if the number is not prime, so if you run it enough times with different inputs, you can be 99.99999% sure that a number is prime. However, a small percentage of numbers are "pseudoprimes" -- numbers that are not prime but which will also satisfy Euler's formula. Therefore, after you discover a candidate prime, you should use a different (slower) formula to double-check.
Since this is fairly common knowledge among geeks who use encryption, I'm somewhat surprised that so many people here jumped to the same conclusion you did.
-a
How to rationalize theft.
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.
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.
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.
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.
>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
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)
Whether polynomial time is longer or shorter than prime time.
LedgerSMB: Open source Accounting/ERP
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.
ECPP is already polynomial time with theoretical exponent ~6. However, the
best ECPP implementation out there, Marcel Martin's 'Primo', seems to behave
as if it has exponent ~4.5-5.
ECPP is non-deterministic though. But it looks like this one is too.
So this looks as if it may be worse than the state of the art.
I'll wait for Lenstra and Pomerance to say their piece though, before making
my mind up.
FatPhil
Also FatPhil on SoylentNews, id 863
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
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.)
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.
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
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.
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
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...
Where did you find out that they were reviewers?
However, word on teh grapevine I have access to says that it seems
that Henrik Lenstra (not to be confused with Arjen), has already
declared taht he believes the proof to be correct and elegant.
And that's about as high a recommendation as it gets.
I'll try to knock up an implementation of his algorithm some time soon, and
see what the practical big-Oh looks like.
Phil
Also FatPhil on SoylentNews, id 863
These principles ignore the fact that there's a finite amount of time,
matter and energy in the universe.
A P algorithm that can never be performed due to its order or constant
factor has no practical use, only theoretical interest.
Theoretical interest is still very interesting.
Practical presses my bottons more though.
Phil
Also FatPhil on SoylentNews, id 863
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
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.
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
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".
I'm aware that calculating the integer square root function is part of the cost of the algorithm, but even so, it's still a polynomial time algorithm. And even if it weren't, you could make it polynomial by replacing "sqrt(n)" with "n". This would, of course, make the algorithm take *longer* on any practical implementation, but it would be just as correct and trivially polynomial.
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).
what is this "euler's formula" of which you speak? i thought miller-rabin was the most commonly used primality test.
I had trouble finding a good reference for this. As I mentioned before, the Euler test is very fast, but it is vulnerable to pseudoprimes. After you find a candidate, you may want to double-check it with another algorithm, such as Miller-Rabin. Here's a crypto library that uses both.
-a
How to rationalize theft.
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 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
Take all of the prime numbers that have been computed to date, and you could fit it all on a floppy, with probably room to spare for a Word document.
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.
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
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.