RSA: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$ Say we have chosen $n=pq$, with $p=89,q=97 \implies n=8633$ and $\varphi(n)=88\times96=8448$. Also, if we want the encoding ($e$) and decoding ($d$) exponents to be equal, we need $$(e,8448)=1 \: \: \text{(relatively prime),}$$ $$ed \equiv 1 \pmod{8448} \implies e^2 \equiv 1 \pmod{8448}.$$

How do I go about solving something like this? My first inclination is that $(e,8448)=1$ means that $e$ must be prime, but I'm really not sure.
If you know the factorization of $\phi(n)$, this can be done like this:

The factorization gives you various prime powers as factors of $\phi(n)$, let's call those $p_i^{e_i}$. Then:


For each $p_i^{e_i}$ with $p_i&gt;2$, the roots of the polynomial $x^2 - 1 = 0 \mod p_i^{e_i}$ are $1$ and $p_i^{e_i}-1$ and there are no other roots. This can be proven by using Hensel lifting for the two roots of the polynomial $x^2-1 \mod p_i$.
For powers of $2$, Hensel lifting the polynomial $x^2-1$ also gives you solutions, but it's more complicated if you want to find all of them, because $f'(r)=2r$ will be $0$ for some root $r$. If you want to find just one, then just use $x=1 \mod 2^x$, where $x$ is the power of $2$ in the factorization of $\phi(n)$. Edit: As an example, every odd number is a square root of $1$  modulo $8$, and modulo $16$ the square roots of $1$ are $\{1,7,9,15\}$.
For each prime power you have a set of two roots $r_1$ and $r_2$ (in a formal prove, you should have indices for the prime powers as well). Choose for each prime power either $x=r_1 \mod p_i^{e_i}$ or $x=r_2 \mod p_i^{e_i}$. If you don't want the trivial solutions $1$ and $-1$, make sure to avoid the 'all $1$' and 'all $p_i^{e_i}-1$' roots.
Use Chinese remainder theorem to assemble the solution $x \mod \phi(n)$


Edit: In the question you only wanted square roots of $1$, which is either $1$ or $-1$ mod any prime $p$. More generally, if you want to find square roots of arbitrary elements, there are also algorithms for that, e.g. Tonelli-Shanks, which work for any prime $p$. Hensel lifting then gives you the roots in the prime powers (but you need to adapt the polynomial), and then assemble the solution via CRT.

Edit:
Of course the choice $e=d$ makes the RSA cryptosystem with public key $(N,e)$ completely unsafe - the value of $e$ is public and you have to assume by Kerckhoff's principle that the attacker knows your system, in this case that you use such a defining equation.