Quantum Computers are Getting Closer To Cracking RSA Encryption

By -
Recent work by Isaac Chuang, an MIT physicist and electrical engineer, illistates the progress that is being made towards a quantum computer that could crack the RSA algorithm. Read the article here.

Recall that RSA is based off of the inability of computers to factor the product of two large primes. Proofs for this can be found in Fermat's Little Theorem and Euler's Theorem like we talked about in class. Quantum computers use quantum computing with qbits instead of normal 1 or 0 bits. Qbits can be a mix of both 1 and 0 simultaneously and exist in a state that is referred to as a superposition.

Peter Shor, an MIT math professor, came up with an algorithm to factor large numbers with a quantum computer back in 1994, but testing it has been slow because of the difficulty of creating a stable quantum computer. Although I tried to understand how the algorithm works, I think I would need a better understanding of physics to fully grasp the algorithm. If you want to take a look read about it here. The major take away is that the algorithm can be completed in polynomial time (2O(log n)) as opposed to exponentially time (2o(n)), which when dealing with such large numbers, it's a monumental difference.

The recent finding was that a five-atom quantum computer (5 qbits) based on an ion trap process was able to calculate the factorization of 15 when it was previously thought to take at least 12 qbits. Although these are still small processes, quantum computers are continuing to improve and it is believed that in the next 15-30 years,  quantum computers will be made that can crack todays RSA algorithms.

The thought of securing data online without the RSA algorithm or methods based on the factoring problem is something people are starting to worry about. With quantum computers, the way in which data is kept secure would be all but destroyed. Chuang believes that we will start to to see quantum encryption methods that will inscribe sensitive data into the very states of atoms (maybe this could be your life's work?). It will be interesting to see the new quantum methods that are created and whether number theory could be used to create these algorithm. Regardless, quantum computing is definitely something that could change our lives drastically in the coming decades.

Comments

Post a Comment

Popular posts from this blog

Common counting techniques

By Natasha -
Image
Before we go too far with proving various clever binomial coefficient identities, let's try counting some things with them. Stars and bars We know that there are " n  choose  k " ways to pick  k  children out of a group of  n  children (assuming we can tell the children apart). But what if we add an indistinguishable element to the story? Unlike our distinguishable children, let's say we have some identical candies to hand out. One natural question is: How many ways are there to hand out  k  indistinguishable candies to  n  distinguishable children? Here's where the stars and bars come in. Let's say we have 3 children and 8 candies. We can think of the candies as the "stars." The 3 children can be thought of as candy receptacles (sorry, kids), distinguished only by their order from left to right. So here's one way we could distribute the candy: ***|****|* In this case, the first child/candy receptacle gets 3 candies, the second gets 4
Read more

"Pyramid Numbers" Fun Fact!

By -
Similar to the set up for the triangular numbers, "pyramid number," or \(P_n\), refers to the required number of dots for a \(n\) triangular base pyramid that has \(n\) dots per side on its base. And here is a fun fact for \(P_n\): $$\sum_{n=1}^{\infty}{\frac{1}{P_n}} = \frac{3}{2}$$ To prove this equality, we first may need some kind of formula for \(P_n\) so that we can do something with the LHS. As you may have found in homework, "Pyramid numbers" are a series of numbers right next to "triangular numbers" in Pascal's triangle. Therefore we know a general formula for \(P_n\): $$P_n = {n+2\choose 3} = \frac{(n+2)\cdot (n+1)\cdot n}{3!}$$ Now, we can rewrite the LHS and try to split the sum expression: $$\begin{eqnarray} \sum_{n=1}^{\infty}{\frac{1}{P_n}} &=& \sum_{n=1}^{\infty}{\frac{1}{(\frac{(n+2)\cdot (n+1)\cdot n}{3!})}}\\ &=&3!\sum_{n=1}^{\infty}{\frac{1}{(n+2)\cdot (n+1)\cdot n}}\\ &=&3!(\frac{1}{1\cdot 2 \cd
Read more

Parallelogram Identity Proof (Using Stars and Bars Technique)

By -
The parallelogram identity in Pascal's triangle states that, given an entry \({n \choose k}\) in Pascal's triangle, \({n \choose k}-1 = \) the sum of the entries included in the rectangle that is straight above entry \({n \choose k}\) and also includes the apex of Pascal's triangle. This equality can be expressed as a double sum as follows, $${n+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{n-k}{n-i-j \choose k-i}$$.  We can prove this by using the stars and bars technique that we are familiar with. For easier explanation, let's first rewrite the double sum expression above in another form (but mathematically equivalent). Set \(r = n-k\), we have  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$.  Let's assume we have \((k+1)\) stars and \(r\) bars. As we have already known, \({r+k+1 \choose k+1}\) counts the number of different star-bar sequences. This implies that maybe we can try to interpret the RHS as another way to count almo
Read more