Here's my attempt at trying to explain what, at an abstract level, RSA is doing:
Imagine taking the powers of p mod n. If p and n have no common factor, then successive powers of p will take on all values less than n, in a sequence starting with 1, p, p^2, p^3, ... and eventually loop back to 1. There are exactly n values from 1...n, so the sequence loops back exactly after the nth power; in other words, p^n mod n == p, or p^(n-1) mod n == 1. This is known as Fermat's Little Theorem.
More colloquially, if you start with a number < n, and exponentiate it enough times mod n, you will get back to where you started. If you exponentiate it a fewer number of times, it will become some other number on this "circle", but you can then take that number and exponentiate it a further suitable number of times to get back to the original one. This is the RSA encryption and decryption, with the exponents being the public and private pieces of the key. The details of how those numbers are chosen involve more maths, but this is basically the principle of how RSA works.
Comments
Here's my attempt at trying to explain what, at an abstract level, RSA is doing:
Imagine taking the powers of p mod n. If p and n have no common factor, then successive powers of p will take on all values less than n, in a sequence starting with 1, p, p^2, p^3, ... and eventually loop back to 1. There are exactly n values from 1...n, so the sequence loops back exactly after the nth power; in other words, p^n mod n == p, or p^(n-1) mod n == 1. This is known as Fermat's Little Theorem.
More colloquially, if you start with a number < n, and exponentiate it enough times mod n, you will get back to where you started. If you exponentiate it a fewer number of times, it will become some other number on this "circle", but you can then take that number and exponentiate it a further suitable number of times to get back to the original one. This is the RSA encryption and decryption, with the exponents being the public and private pieces of the key. The details of how those numbers are chosen involve more maths, but this is basically the principle of how RSA works.