Combinatorics

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

In class we proved that if \(m\) and \(n\) are coprimes (i.e. \(gcd(m,n)=1\)),  then \(\varphi(mn) = \varphi(m)\varphi(n)\). In this article we will discuss what will happen for \(m\) and \(n\) in general. In other words, given \(gcd(m,n)=d\) for some \(d\in\mathbb{N}\), what can we say about \(\varphi(mn)\)? Let's first do prime factorization for both \(m\) and \(n\), then $$m = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$ $$n = q_1^{r_1}q_2^{r_2}...q_j^{r_j}$$ Consider \(gcd(m,n)=d \geq 2\). Then \(m\) and \(n\) have at least one common prime factors. Assume the prime factorization expressions for \(m\) and \(n\) above are written in the way that \(m\) and \(n\)'s common prime factors are written at the beginning and aligned correspondingly. i.e. \(p_i = q_i\) for all \(1\leq i \leq c\) for some \(c\leq min(j,k)\). Then we can say the prime factors for \(m\) and \(n\)'s common divisor, \(d\), are \(p_i\)'s where  \(1\leq i \leq c\). Then $$\begin{eqnarray} \varphi(mn)