2 ms·
I was expecting a real example using some actual numbers and simple operations to demonstrate how this works. Instead there are a couple of vague metaphors that
by loloquwowndueo 2y ago
I was expecting a real example using some actual numbers and simple operations to demonstrate how this works. Instead there are a couple of vague metaphors that don’t explain much about the actual math involved beyond “multiply two primes”.
- d-lisp 2y agoWould you be interested in that ? I could write about it
- abridges6523 2y agoIf you write about it, I’ll read it
- Jtsummers 2y agohttps://www.cs.utexas.edu/~mitra/honors/soln.html https://www.cs.utexas.edu/~mitra/honors/soln.html Worked example using p = 3 and q = 11. φ(n) is the most complex part, but you can take it as shown if you don't care about the proof. For two primes, φ(p * q) = (p - 1) * (q - 1). The proof of this is more complex, and the calculation can get more involved if it's not a pair of primes, but for RSA it's that simple. Coprime can be defined using middle/high school math: two numbers are coprime if gcd(n,m) = 1. They have no common factors other than 1, that's all it means. So 4 and 9 are coprime even though neither are prime. ---- φ(n) is Euler's totient function. It gives you the number of numbers coprime to n in the range 1 <= k <= n. So in the worked example, φ(n) = 20 means there are 20 numbers in that range that have no factors other than 1 in common with 33: 1 2 4 5 7 8 10 13 14 16 17 19 20 23 25 26 28 29 31 32 None of those have 3 or 11 as factors. https://en.wikipedia.org/wiki/Euler's_totient_function https://en.wikipedia.org/wiki/Euler's_totient_function