Discovery Cafe Talk: Tuesday, April 9, 5:30-6:30 PM, MC 108. Pizza to follow immeditaley after!

Speaker: Masoud Khalkhali

Public-key encryption and security of internet communications is based on a certain mathematical hypothesis:factoring a given integer N is a computationally difficult problem. The best current methods take about

$$ O(e^{1.9 (\log N)^{1/3} (\log \log N)^{2/3}})$$

operations. This is almost exponential in log N, the number of digits of N

A quantum computer, running Shor's algorithm, can factor N in

$$O((\log N)^3)$$

steps! This is polynomial in log N, or polynomial time, and a huge improvement over current methods.

This talk will introduce mathematics and physics ideas behind quantum computing and Shor's fast factoring quantum computing algorithm.

## No comments:

## Post a Comment