Algorithm for determining whether two imaginary quadratic numbers are equivalent under a modular transformation Let $\Gamma = SL_2(\mathbb{Z})$.
Let $\mathcal{H} = \{z \in \mathbb{C}\ |\ \mathcal{Im}(z) &gt; 0\}$ be the upper half complex plane.
Let $\sigma = \left( \begin{array}{ccc}
p &amp; q \\
r &amp; s \end{array} \right)$ be an element of $\Gamma$.
Let $z \in \mathcal{H}$.
We write $$\sigma z = \frac{pz + q}{rz + s}$$
It is easy to see that $\sigma z \in \mathcal{H}$ and $\Gamma$ acts on $\mathcal{H}$ from left.

Let $\alpha \in \mathbb{C}$ be an algebraic number.
If the minimal plynomial of $\alpha$ over $\mathbb{Q}$ has degree $2$, we say $\alpha$ is a quadratic number.
There exists the unique polynomial $ax^2 + bx + c \in \mathbb{Z}[x]$ such that $a &gt; 0$ and gcd$(a, b, c) = 1$.
$D = b^2 - 4ac$ is called the discriminant of $\alpha$.
Since $D \equiv b^2$ (mod $4$), $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$).
Conversly suppose $D$ is a non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). Then there exists a quadratic number $\alpha$ whose discriminant is $D$.

Let $D$ be a negative non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$).
We denote by $\mathcal{H}(D)$ the set of quadratic numbers of discriminant $D$ in $\mathcal{H}$.
By this question, $\mathcal{H}(D)$ is $\Gamma$-invariant.

My question
Let $\alpha, \beta$ be explicitly given elements of $\mathcal{H}(D)$.
Is there algorithm for solving the following problems?
If yes, what is it?


Determine whether there exists $\sigma \in \Gamma$ such that $\alpha = \sigma \beta$.
If there exists such $\sigma$, determine the components of the matrix $\sigma$.


Remark
My motivation for the above question came from this and this.
We do not need the assumption that $\alpha$ and $\beta$ are quadratic. We can do the test for any two points in the upper half plane.

The crucial concept is the fundamental domain: the region $F$ in which a point $z$ satisfies $-1/2\leq\text{Re}(z)&lt;1/2$ and $|z|&gt;1$ or $|z|=1$ and $\text{Re}(z) \leq 0$. Points in $F$ cannot be mapped onto each other by modular transformations, apart from $z=i$ which can be mapped onto itself. However, the images of $F$ under modular transformations cover the upper half plane. This is a standard construction: http://en.m.wikipedia.org/wiki/Modular_group

A strategy for testing whether two numbers are equal modulo a modular transformation is to map them both into $F$. In the remainder of this answer I will define such a function.

The transformations $z \mapsto z+1$ and $z \mapsto -1/z$ are modular transformations and in fact generate the group. I will show that iterating $z \mapsto g(f(z))$ maps any point into $F$ in a finite number of steps, where:

$$f(z) = z - \lfloor \text{Re}(z)+1/2 \rfloor$$
$$g(z) = z \text{ if } z\in F \text{ else } -1/z$$

Suppose $\text{Im}(z)&lt;1/3$. Let $w=f(z)$. Then $-1/2\leq\text{Re}(w)&lt;1/2$, and the imaginary part is unchanged, so $|w| &lt; \sqrt{13/36}$. Let $z'=g(w)$. Then $\text{Im}(z')&gt;(36/13)\text{Im}(z)$. Therefore, we need to iterate the mapping $z \mapsto z'$ at most $-\log_{36/13}(\text{Im}(z))$ times to ensure $\text{Im}(z) \geq 1/3$.

From this point two further iterations of $z \mapsto g(f(z))$ suffice to map $z$ into $F$, as I will now show.

After $z \mapsto f(z)$, we also know $|\text{Re}(z)| \leq 1/2$. It's then possible that $z \in F$ and we're finished. If not we also know $|z| \leq 1$. Those four bounds describe a shape with four sides: two circles and two straight lines.

After $z \mapsto -1/z$ (the action of $g$ in this case) we have a different shape. The first bound ($\text{Im}(z) \geq 1/3$) maps to $|z-3i/2| \leq 3/2$. That's a circle of radius $3/2$ centred on a point with zero real part. We can weaken it to $|\text{Re}(z)| \leq 3/2$. The second and third bound ($|\text{Re}(z)| \leq 1/2$) map to $|z-1| \geq 1$ and $|z+1| \geq 1$. The fourth bound ($|z| \leq 1$) maps to $|z| \geq 1$.

So now we have a shape with five sides. If you draw it you will see it looks like three copies of $F$ side by side. Applying $f$ maps them all onto the central copy and ensures that $\text{Im}(z) \neq +1/2$. Applying $g$ one last time ensures that if $|z| = 1$ then $\text{Re}(z) \leq 0$.

So for an arbitrary starting point in the upper half plane, we have constructed a modular transformation that maps it into $F$. If we do this for two points, we can see if they map to the same point in $F$. If so, we can map them onto each other, otherwise it is impossible.
Let $F = \{z \in \mathcal{H}\ |\ -1/2 \le Re(z) \lt 1/2, |z| \gt 1$ or $|z| = 1$ and $Re(z) \le 0\}$. It is well-known that any two distincts points of $F$ are not equivalent under the action of $\Gamma$.
Let $S = \left( \begin{array}{ccc}
0 &amp; -1 \\
1 &amp; 0 \end{array} \right)$, 
$T = \left( \begin{array}{ccc}
1 &amp; 1 \\
0 &amp; 1 \end{array} \right)$.
Let $z \in \mathcal{H}$.
We will show that applying $S, T$ or $T^{-1}$ consecutively on $z$, we can map $z$ into $F$.
Hence we can find $\sigma \in \Gamma$ such that $\sigma z \in F$.
We consider the following algorithm.

Algorithm 1


$z = T^{-\lfloor \text{Re}(z)+1/2 \rfloor}(z)$, where $\lfloor a \rfloor$ denotes the greatest integer $n$ such that $n \le a$.  
If $|z| \gt 1$, then stop.
If $|z| \lt 0$, then $z = S(z)$ and go to 1.
If $|z| = 1$, then go to 3.
If $-1/2 \le Re(z) \le 0$, then stop.
If $0 \lt Re(z) \lt 1/2$, then $z = S(z)$ and stop.


If the algorithm terminates, then $z \in F$.
We will prove that it terminates in finite steps.

Lemma 1
$S(\{z \in \mathcal{H}\ |\ Im(z) \ge 1/3\}) = \{z \in \mathcal{H}\ |\ |z - 3i/2| \le 3/2\}$.

Proof:
Let $w = -1/z$.
Then $z = -1/w$.
Since $Im(z) = (z - \bar z)/2i$, $Im(z) = (-1/w + 1/\bar w)/2i$.
Hence $(-\bar w + w)/2i \ge w\bar w/3 = |w|^2/3$.
Let $w = x + yi$.
Then $y \ge (x^2 + y^2)/3$.
Hence $x^2 + y^2 - 3y \le 0$.
Hence $x^2 + (y - 3/2)^2 \le (3/2)^2$.
QED

Lemma 2
$S(\{z \in \mathcal{H}\ |\ Re(z) \lt 1/2\}) = \{z \in \mathcal{H}\ |\ |z + 1| \gt 1\}$.

Proof:
Let $w = -1/z$.
Then $z = -1/w$.
Since $Re(z) = (z + \bar z)/2$, $Re(z) \lt 1/2$ implies $-1/w - 1/\bar w \lt 1$.
Hence $-\bar w - w \lt |w|^2$.
Let $w = x + yi$.
Then $-2x \lt x^2 + y^2$.
Hence $(x + 1)^2 + y^2 \gt 1$.
QED

Lemma 3
$S(\{z \in \mathcal{H}\ |\ Re(z) \ge -1/2\}) = \{z \in \mathcal{H}\ |\ |z - 1| \ge 1\}$.

Proof:
Let $w = -1/z$.
Then $z = -1/w$.
Since $Re(z) = (z + \bar z)/2$, $Re(z) \ge -1/2$ implies $-1/w - 1/\bar w \ge -1$.
Hence $\bar w + w \le |w|^2$.
Let $w = x + yi$.
Then $2x \le x^2 + y^2$.
Hence $(x - 1)^2 + y^2 \ge 1$.
QED

Proposition 1
The algorithm terminates in finite steps.

Proof(based on the idea of apt1002):

Suppose $Im(z) \lt 1/3$ in the first place.
After executing step 1, $-1/2 \le Re(z) \lt 1/2$.
Hence $|z|^2 \lt 1/4 + 1/9 = 13/36$.
Then $Im(S(z)) = Im(z)/|z|^2 \gt (36/13)Im(z)$.
Since $\text{lim}_{n\rightarrow \infty} (36/13)^nIm(z) = \infty$,
after executing finite steps, the algorithm terminates or $Im(z) \ge 1/3$.
Hence we may suppose $Im(z) \ge 1/3$ in the first place.    

After executing step 1, if $|z| \ge 1$, the algorithm terminates.
Hence we may suppose $|z| \lt 1$.
Let $w = -1/z$.
Then $|w| \gt 1$.
By Lemma 1, Lemma 2 and Lemma 3, $|Re(w)| \le 3/2, |w + 1| \gt 1, |w - 1| \ge 1$.

Case 1: $-3/2 \le Re(w) \lt -1/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w + 1$.
Then $-1/2 \le Re(z) \lt 1/2$.
Since $|z| \gt 1$, the algorithm terminates.

Case 2: $-1/2 \le Re(w) \lt 1/2$

Since $|w| \gt 1$, the algorithm terminates. 

Case 3: $1/2 \le Re(w) \lt 3/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w - 1$.
Then $-1/2 \le Re(z) \lt 1/2$.
Since $|z| \ge 1$, the algorithm terminates.

Case 4: $Re(w) = 3/2$

Let $z = T^{-\lfloor \text{Re}(w)+1/2 \rfloor}(w) = w - 2$.
Then $Re(z) = -1/2$.
Since $Im(z) = Im(w) \ge \sqrt 3/2$, $|z| \ge 1$.
Hence the algorithm terminates.
QED