Understanding Fourier Transform and RSA Encryption
Dive into the world of Fourier Transform pioneered by Joseph Fourier, which decomposes frequencies into constituent parts, and explore how RSA encryption secures data using prime numbers and quantum Fourier transform, making it hard to break. Discover the basics, applications, and significance of these concepts in the digital realm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
FOURIER TRANSFORM AND RSA Nathan Conger
Joseph Fourier (1768-1830) Looked at heat diffusion (1822; The Analytical Theory of Heat ) Showed that many functions can be expressed in terms of an infinite series of trigonometric functions (Fourier Series). https://www.britannica.com/biography/Joseph-Baron-Fourier https://www.britannica.com/biography/Joseph -Baron-Fourier https://mathworld.wolfram.com/FourierSeries.html
What is the Fourier Transform? Decomposing frequency into its constituent parts Desmos Demo https://community.sw.siemens.com/s/article/what-is-the-fourier-transform
https://www.mathworks.com/help/matlab/math/fourier- transforms.html#:~:text=Use%20a%20time%20vector%20sampled,a%20period%20of%2010%20seconds.&text=Compute%20the%20Fourier%20transform%20of%20the%20 signal%2C%20and%20create%20the,)*50%2Flength(y)%3B
Audio Correction 2 Flatten annoying sound 3 Apply Inverse Fourier Transform 1 Apply Fourier Transform
RSA Encryption RSA encryption uses 2 keys: a Public key P = ?1?2, where ?1?2 are distinct prime and a Private key generated by the prime numbers D = ?(?)) The strength of RSA comes from it being immensely difficult to find factors of large numbers. Using the quantum form of the Fourier transform, we can break RSA encryption super quickly using Shor s Algorithm
Shors Algorithm Objective: Get the prime factors ?1,?2 of the Public RSA key N. Algorithm: Let?be some initial guess, 1 < ? < ?, If g|?, then we re done. ?1= ?, ?2=? Otherwise, use Euclid s algorithm to check if gcd ?,? > 1 . ? For any coprime ?,?, ??= ? ? + 1for some ? . ? 2 1 )(? https://en.wikipedia.org/wiki/Shore ? 2+ 1) = ? ? Can be arranged to (? ? 2 1 )(? ? 2+ 1) = ? ?and (? ? 2 1) N or(? ? 2+1) N Find an even ? such that (? Use Euclid s algorithm (on each of our new guesses with N to get ?1,?2 . The difficulty comes with finding ? ?can be found in to 20-30 runs of the algorithm (reduced to 4-8 runs with modifications )
Finding p Quantum computing is probabilistic. I can take make multiple computations simultaneously and get out each output weighted with some probability. Observing the output collapses the probabilities together to get a single output. Input: |1, 0 +|2, 0 +|3, 0 + =>?? ??? ? output: |1, ?1 +|2, ?2 +|3, ?2 + ,0 ??< ?, ? Measure remainder state. This partially collapses output state into |?1, ?? +|?2, ?? +|?3, ?? +... Output is superposition of all inputs with remainder is ?? Property: ??= ? ? + 1and ??= ?2 ? + ?, then ??+??= ?3 ? + ?, ? . ? is periodic Our previous output really is: |?1, ?? +|?1+ ?, ?? +|?1+ 2?, ?? +... Input the superposition |?1, ?? +|?1+ ?, ?? +|?1+ 2?, ?? +...into Quantum Fourier Transform gets the superposition: |1 ? + . Measuring the output collapses it to |? ? +|2 ? +|3 ? for some ?. Repeating the calculation yields different outputs, so using gathered QFT data, we can calculate 1 ?
Shors Example Suppose we want to factor 15. 1) Choose a random guess, say 2. 2)Input superposition |1, 0 +|2, 0 +|3, 0 + =>2? ??? ? output: |1, +2 +|2, +4 +|3, +8 + 3) Measure for remainder. Collapses into superposition with random remainder, say 2. Output: |1, 2 +|5, 2 +|9, 2 + 4) Input into QFT |1 ? +|2 ? +|3 ? + after repeated measure and recalculation 2 5 4, 7 4, 4, 4, even 4 2 1) = 3, ?2 4 2+ 1) = 5 5) ?1 = (2 = (2 6) Euclidean Algorithm: gcd 3,15 = 3 ?1= 3, ?2=15 3= 5
References https://www.britannica.com/biography/Joseph-Baron-Fourier https://community.sw.siemens.com/s/article/what-is-the-fourier-transform https://sites.math.washington.edu/~morrow/336_16/2016papers/tristan.pdf https://riliu.math.ncsu.edu/437/notes3se4.html https://www.quantiki.org/wiki/shors-factoring-algorithm https://www.geeksforgeeks.org/rsa-algorithm-cryptography/
