plarq
Crazy forever
Well, WWII cryptography will be deciphered almost immediately by modern electronic computers. So there's no surprise. Computer architecture kind of things.
Ask a Mathematician!
- Thread starter IdiotsOpposite
- Start date
I think these hopes are justified, at least for the next decades.
But even if quantum computers would obsolete classical cryptography, wouldn't they also immediately make quantum cryptography possible, which is even harder to crack?
Mise
isle of lucy
Well it would take time to develop quantum computing encryption algorithms, whereas methods to brute force existing cryptographic algorithms already exist. Quantum computers would be able to encrypt stuff really really fast, but not necessarily more securely; you'd need to develop new algorithms in order to do that.
Kozmos
Jew Detective
That reminds me about that one xkcd about encryption and how rather than breaking the code it would be just much easier to pipe wrench the guy who knows the password.
meromorph
Chieftain
Quantum computers do not necessarily obsolete classical cryptography, they are just able to break some of the most widely used systems. There is a whole field of research called "post-quantum cryptography" about classical cryptographic systems that we can move to using once large scale quantum computers become a reality. Here is a recent book on this subject:
http://www.springer.com/mathematics/numbers/book/978-3-540-88701-0
Post-quantum cryptography is about classical crypto systems which are secure against quantum attacks. This is separate from research into quantum cryptography, which aims to build a quantum crypto system that is secure against both classical and quantum attacks.
People have been working on designing quantum cryptographic systems since the 1980s. The advantage of quantum crypto systems is not just speed, but that they can provide a fundamentally better level of secrecy than could ever be achieved with a classical crypto system.
The reason for this is that the uniquely quantum property of entanglement can be used to detect eavesdroppers. The basic example is that if two quantum bits, b1 and b2, are entangled, then it is impossible to even look at b2 without disturbing b1. Therefore when a quantum message is compromised by an eavesdropper, the sender and receiver can detect this.
The situation I described above leads to a protocol called "quantum key distribution", where party A can send a secret key to party B (the key is a randomly generated number) , and they only use the key if they can verify that there was no eavesdropper. In practice, the eavesdropper may try to use "quantum hacking" to learn information from the quantum bits without disturbing their entanglement, so just as in classical cryptography we have a sort of arms race between people proposing new crypto systems and people finding attacks that break those systems. There is a lot more research to be done, but the basic idea that quantum entanglement guards against eavesdroppers has prompted enormous interest in quantum cryptography. There are already relatively small quantum key distribution networks being built from fiber optic cable:
http://news.bbc.co.uk/2/hi/science/nature/7661311.stm
http://www.springer.com/mathematics/numbers/book/978-3-540-88701-0
Post-quantum cryptography is about classical crypto systems which are secure against quantum attacks. This is separate from research into quantum cryptography, which aims to build a quantum crypto system that is secure against both classical and quantum attacks.
Mise said:
People have been working on designing quantum cryptographic systems since the 1980s. The advantage of quantum crypto systems is not just speed, but that they can provide a fundamentally better level of secrecy than could ever be achieved with a classical crypto system.
The reason for this is that the uniquely quantum property of entanglement can be used to detect eavesdroppers. The basic example is that if two quantum bits, b1 and b2, are entangled, then it is impossible to even look at b2 without disturbing b1. Therefore when a quantum message is compromised by an eavesdropper, the sender and receiver can detect this.
The situation I described above leads to a protocol called "quantum key distribution", where party A can send a secret key to party B (the key is a randomly generated number) , and they only use the key if they can verify that there was no eavesdropper. In practice, the eavesdropper may try to use "quantum hacking" to learn information from the quantum bits without disturbing their entanglement, so just as in classical cryptography we have a sort of arms race between people proposing new crypto systems and people finding attacks that break those systems. There is a lot more research to be done, but the basic idea that quantum entanglement guards against eavesdroppers has prompted enormous interest in quantum cryptography. There are already relatively small quantum key distribution networks being built from fiber optic cable:
http://news.bbc.co.uk/2/hi/science/nature/7661311.stm
Mise
isle of lucy
I see, thanks for the explanation and the link!
By the way, you can order a quantum computer with 128 qbits today.
http://www.dwavesys.com/en/products-services.html
I'm not sure how this improves the time to factorize big numbers. I think the minimum number of qubits that is required for the factorization rises with the size of the number to factorize.
http://www.dwavesys.com/en/products-services.html
I'm not sure how this improves the time to factorize big numbers. I think the minimum number of qubits that is required for the factorization rises with the size of the number to factorize.
Certainly for the next decade, but beyond that I wouldn't be so sure. It is a hot field at the moment. And if you want to keep something secret for a long time this might become relevant.
Not necessarily. Quantum computers are not a prerequisite for quantum cryptography and do not necessarily make it possible. A quantum computer has to transmit quantum information only over a short distance, but quantum cryptography requires long distance quantum communication. There are concepts of distributed quantum computing which would require quantum communication, but fundamentally these are different problems. For example, if there was a successful implementation of a solid state quantum computer with superconducting qubits, this would not help quantum cryptography at all (except for invalidating many classical schemes).
But ti seems that the problems of long distance quantum communication are easier to solve than those of a scalable quantum computer, so when the first quantum computer to crack RSA comes along, quantum cryptography might be well established already.
In fact, you can already commercially buy complete quantum cryptography systems. Those are not without problems (for example, they don't use single photons but weak laser pulses), but are already beyond the proof of concept.
But one has to keep in mind, that although the protocol may be inherently secure, the implementation is not. The best cryptography system does not help you, if the computer itself is compromised (at one point the information has to be decrypted to be useful) or you fall prey to the 5$-wrench security hole.
meromorph
Chieftain
D-wave is not building a general purpose quantum computer, and their machine is not able (or intended) to factor integers.
The computer that D-wave is building uses a process called "quantum adiabatic optimization." The key word is "optimization", an important general class of problems in mathematics and computer science where the goal is to minimize (or maximize) some function. Perhaps the most famous optimization problem is the traveling salesman: given N cities marked on a map, find the path of minimum distance that connects them all.
More generally, suppose you have a function f(z_1, z_2, ... , z_n) where each of the z_i are 0 or 1 (so f the domain of f is n-bit strings). For n = 128 and some particular types of functions f, D-wave claims that they can find the minimum of f faster than any classical machine that exists on earth today.
To summarize, D-wave is not building a universal quantum computer, but rather a machine specifically designed for a certain kind of optimization problem. There are many potential applications of fast optimization, such as pattern recognition and computer learning, but not every type of problem can be solved by optimizing. No one knows how to express integer factorization as an optimization problem, and it is probably not possible to do so.
To answer your other question, Shor's algorithm factors a number N in time O((log N)^(1/3)) and uses space O(log N). In other words, to factor 1024-bit RSA encryption we need a few 1000s qubits. However, error correction and fault-tolerance are a very important part of building a realistic quantum computer, and including these processes we would need 10,000 or even 100,000 qubits to really use Shor's algorithm.
Fortunately, a universal quantum computer with only 20-30 qubits would be very useful for research in physics and chemistry, so the time of useful quantum computers might not be as far off as suggested in the above paragraph. Even though D-wave claims to have 128 qubits, many people dispute the claim (maybe the electrical signals they are measuring aren't really quantum effects, but just classical thermal noise), and even if we accept the claim then their optimization machine isn't intended to solve the physics and chemistry problems that need only 20-30 qubits to be useful.
IdiotsOpposite
Boom, headshot.
Indeed it was. I'll be honest and say I didn't know that much about quantum cryptography, but now I feel like I've understood a lot more.
Blue Emu
GroFAZ
Is it true that mathematicians who specialize in the mathematics of infinites can only count up to three? (aleph-null, aleph-one and c)
In other words... have any of the higher infinities ever found anything to count?
In other words... have any of the higher infinities ever found anything to count?
IdiotsOpposite
Boom, headshot.
There are higher levels of infinity than the three you named, yes. In fact, there are infinite infinities! However, almost all of these infinities do not correspond to anything most people deal with (like, for example, the natural numbers, or the continuum).
EDIT: Using the beth numbers, there ARE two others. (Note that Beth-null is equal to Aleph-null, and Beth-one is greater than or equal to Aleph-one. The continuum hypothesis is equivalent to the statement Beth-one = Aleph-one = c) The first is Beth-two, which is the cardinality of the set of functions from R^m to R^n, or the cardinality of the power set of the reals. The second is Beth-omega, which I believe is the smallest uncountable cardinal.
meromorph
Chieftain
There is a lot more to count if we work infinite ordinals, rather than infinite cardinals.
Two infinite cardinals are equal whenever there is a bijective function between them, and this relatively coarse notion of equality makes the cardinal hierarchy simple. With the ordinals we use a tighter notion of equality: ordinals are totally ordered sets, and two infinite ordinals are equal only if there is an order-preserving bijection between them.
To explain this, first define the finite ordinals:
0 = {}
1 = {0}
2 = {0,1}
.
.
.
n = {0, 1, ... , n -1}
These are called successor ordinals, the rule for successor ordinals is:
n + 1 = n union {n}
Given any ordinal number A, which is a totally-ordered set, we construct it's successor by taking the union of A with {A}. Ordinals which are not successors are called limit ordinals. The first limit ordinal is also the first infinite ordinal:
w = {0, 1, 2, ... }
(read w as lower case greek omega, that is the standard notation). Now is the fun part, define the the successor of omega:
w + 1 = {0, 1, 2, ... , w}
and, as ordinals, omega is not equal to its successor. This is because there is no order preserving bijection between w and w + 1. Let f: w + 1 -> w be a function, then f cannot be order preserving, because f(w) has to be larger than f(1), f(2), ..., f(n) for every n, but since f(w) is a natural number (it's in w) it can't be larger than every natural number.
In fact, the successor of an ordinal A is never equal to A, it's always a new ordinal greater than A. So we get a sequence:
1, 2 , ... , w , w + 1, w + 2, ...
what comes after the ... ? Well that's another limit ordinal, w + w:
1, 2 , ... , w , w + 1, w + 2, ... , w + w, w + w + 1, ....
If we continue this we'll get to w*w = w^2. We can keep it up until w^w. We can even keep going to w^w^w^...*w times*... .
That last ordinal I just described, w^w^w^...*w times*... , is merely countable, it has the cardinality of aleph_0.
So even though there is only one countably infinite cardinal, there are countably infinitely many countably infinite ordinals. It turns out that the "infinity plus one" strategy in the playground game of "name the largest number you can" is well founded after all.
plarq
Crazy forever
Man this is a math thread, not a physics thread.
meromorph
Chieftain
You mean the discussion about quantum computation? Here is an excellent textbook published by the American Mathematical Society:
Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium
Physics isn't math?
It's a subset of applied math...
Other discussion stuff:
I didn't have any real issues with Real Analysis, but I had already taken several other rigorous proof based classes before. I get the feeling it's not that bad, but for many people it's there first "real" math hence the horror stories.
So I'm currently sitting around waiting to see if I got into any grad schools, fun stuff
Any ideas on what to do if I don't get in anywhere? I was thinking of applying to Wall Street banks, tech companies, and NSA/CIA to do crypto stuff. But I know for most of that a b.S. won't cut it. Bottom line I refuse to go do crappy non-technical math workHave you taken the Putnam? I got a 12 last year and I think I got two solid problems this year so 20ish hopefully? Definitely one of my better math experiences, I'de definitely suggest participating to any other math majors if you can.
GhostWriter16
Deity
Do you actually believe everyone who struggles with Math is stupid? (Addressed both at Zelig and the threadstarter.)
And what do you mean by that? Also, what are your thoughts on the following comic?
If my teacher tried the second approach, I'd say "Alright fine, I'm never gonna be good at math anyway." And my teacher basically already does the first approach (I do work to pass but I really don't care if I retain it past the class. More focused on History and English.Question: Does anyone who wants to be in a historical or legal profession really need anything more than geometry.
On some level yes I do, it's obvious to me but when I explain it to people and they look at me like I'm speaking French I think to to myself that there is probably something medically wrong with them.
But I know better than to say anything and I can usually look past it, both my girlfriends have struggled with math and it didn't bother me too much.
Question: Does anyone who wants to be in a historical or legal profession really need anything more than geometry.
Not the actual math, but the reasoning skills are very valuable in legal for sure maybe less so for history.
