3 ms·
The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of m
by Qub3d 6y ago
The fundamental mathematical concepts revealed in this answer, especially the use of Euler's totient theorem, are worth pondering because it is this branch of modular arithmetic that Diffie and Hellman first proposed, and then Rivest, Shamir, and Adleman concretely used to produce, well, RSA:
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation
Sadly, quantum supremacy may mean this form of cryptography will soon be dead, but this curious application is why modular arithmetic is a favorite of mine. It was a branch of math that historically had a few niche applications, and then in the 21st century became an underpinning to global capitalism.
- enriquto 6y ago> Sadly, quantum supremacy may mean this form of cryptography will soon be dead I don't think it will be soon, but when it happens it won't necessarily be sad.
- Qub3d 6y agoWell, I suppose I mean sad in the way people are wistful when old technology fades into obsolescence, not because the tech was better (it clearly isn't) but because the times it represents fading with it. e.g. dumb phones, analog TV, CRT monitors, floppy disks...
- uuidgen 6y agoI don't believe "quantum computing" will get us any step closer to breaking RSA. Similar how complex number theory didn't allow us to draw a square with area of -1. To break RSA-N you need a superposition of all the numbers up to 2^N, AFAIK there is even not a hint how to approach it physically.
- danbruc 6y agoA superposition of all n bit integers is no big deal, extracting useful information when performing a measurement is. If you start with a uniform distribution of all n bit integers, you also get each result with equal probability unless you manage to manipulate the system in such a way that the probability of the correct result gets amplified. This is the hard part, finding and implementing operations that selectively boost the probability of the correct result while reducing the probabilities of all other results.
- uuidgen 6y ago> A superposition of all n bit integers is no big deal Is it? How do you do it? The papers I've seen so far shown that given enough measurements we can conclude that the qbits ware in superposition in many cases. I still haven't seen any way to have superposition of all numbers from 0 to 2^n. What you're describing in the rest of your comment is solved by Shor's algorithm. It is quite straight-forward. If we can get the superposition as an input and have working quantum gates it would work. Similar how all we need to draw a square with -1 area is to take a line segment with a length of i, the rest is simple.
- perl4ever 6y agoDidn't I read somewhere that quantum computing basically gets you a factor of 2, like 2^(N-1)? It's a lot but at the same time it's just a bit.
- einpoklum 6y agoIMHO Quantum supremacy is pie in the sky, which will stay in the sky. So, you can probably pursue modular arithmetic safely for the foreseeable future.