Perhaps more than any other single institution in the world, the Santa Fe Institute has played a seminal role in developing much of the mathematical and computational structure and conceptual framework underlying complex systems. Today that framework is being exploited to understand the relationship…
Caesar shifted each letter three places in the alphabet. Much of modern computer science was born in the effort to break the Nazi Enigma code, and Cold War spies used code books that fit inside a walnut. Nowadays, the cryptography we depend on every day — for instance, to send our credit card information when we buy something on the Web — relies in turn on the mathematics of prime numbers. But in 1994, Peter Shor discovered that a future quantum computer could crack our cryptosystems by breaking large numbers into their prime factors. Cris will start by describing how these cryptosystems work, and how a quantum computer could break them. (Nothing beyond high-school math, he promises!) He’ll end by giving a personal view about whether quantum computers can be built — and what kinds of cryptography could remain secure even if and when they are built.