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) > 0\}$ be the upper half complex plane.
Let $\sigma = \left( \begin{array}{ccc}
p & q \\
r & 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 > 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.
 A: 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)<1/2$ and $|z|>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)<1/3$. Let $w=f(z)$. Then $-1/2\leq\text{Re}(w)<1/2$, and the imaginary part is unchanged, so $|w| < \sqrt{13/36}$. Let $z'=g(w)$. Then $\text{Im}(z')>(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.
A: 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 & -1 \\
1 & 0 \end{array} \right)$, 
$T = \left( \begin{array}{ccc}
1 & 1 \\
0 & 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
A: Let us apply the method of apt1002 to the OP's problem.
We use the definitions and notation of this question.
Let $D$ be a negative non-square integer such that $D \equiv 0$ (mod $4$) or $D \equiv 1$ (mod $4$). We denote the set of positive definite primitive binary quadratic forms of discriminant $D$ by $\mathfrak{F}^+_0(D)$.
For notational convenience, we denote an element $ax^2 + bxy + cy^2$ of $\mathfrak{F}^+_0(D)$ by $(a, b, c)$.
We define a map $\phi\colon \mathfrak{F}^+_0(D) \rightarrow \mathcal{H}(D)$ by $\phi((a,b,c)) = (-b + \sqrt D)/2a$.
By the question, $\phi$ is a bijection and $\phi(f^\sigma) = \sigma^{-1}\phi(f)$ for $f \in \mathfrak{F}^+_0(D),\ \sigma \in \Gamma$.
We denote $f^{\sigma^{-1}}$ by $\sigma f$.
Thus $\Gamma$ acts on $\mathfrak{F}^+_0(D)$ from left.
Then $\phi$ is an isomorphism between the $\Gamma$-sets.
Therefore it suffices to solve the corresponding problem in $\mathfrak{F}^+_0(D)$.
We denote $\phi((a,b,c))$ by $\phi(a,b,c)$ by abuse of notation.
Let $S = \left( \begin{array}{ccc}
0 & -1 \\
1 & 0 \end{array} \right)$, 
$T = \left( \begin{array}{ccc}
1 & 1 \\
0 & 1 \end{array} \right)$.
It is easy to see that
$S\phi(a,b,c) = \phi(c, -b, a)$,
$T^{-n}\phi(a,b,c) = \phi(a, 2an + b, an^2 + bn + c)$ for $n \in \mathbb{Z}$.
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\}$.
Proposition 3
Let $(a,b,c) \in \mathfrak{F}^+_0(D)$.
The necessary and sufficient conditions for $\phi(a,b,c) \in F$ are as follows.


*

*$|b| \le a \le c$.

*If $|b| = a$ or $a = c$, then $b \ge 0$.
Proof:
Since $Re(\phi(a,b,c)) = -b/2a, -1/2 \le -b/2a \lt 1/2$.
Hence $-a \le -b \lt a$.
Hence $|b| \le a$.
If $|b| = a$, $a = b$.
Since $|\phi(a,b,c)|^2 = (b^2 - D)/4a^2 = 4ac/4a^2 = c/a \ge 1, a \le c$.
If $|\phi(a,b,c)| = 1$, i.e. $a = c$, then $-1/2 \le -b/2a \le 0$.
Hence $-a \le -b \le 0$.
Hence $a \ge b \ge 0$.
QED
We denote the set of $(a, b, c)$ which satisfies the conditions of Proposition 3 by $\mathcal{F}(D)$.
$\mathcal{F}(D)$ is a finite set as shown in my answer to this question.
Let $(a,b,c) \in \mathfrak{F}^+_0(D)$.
We consider the following algorithm.
Algorithm 2


*

*If $-a \le -b \lt a$, go to 2.
If not, set $(a,b,c) = (a, 2an + b, an^2 + bn + c)$, where $n = \lfloor -b/2a +1/2 \rfloor$.

*If $a \lt c$, then stop.
If $a = c$, go to 3.
If $a \gt c$, set $(a,b,c) = (c, -b, a)$ and go to 1.

*If $b \ge 0$, stop.
Otherwise set $(a,b,c) = (c, -b, a)$ and stop.
Proposition 4
The algorithm terminates in finite steps.
Moreover when it terminates, $(a, b, c) \in \mathcal{F}(D)$.
Proof:
This follows immediately from Proposition 1.
However, we will prove it directly.
If $|b| \gt a$ or $-b = a$, by executing step 1, $b$ satisfies $-a \le -b \lt a$, hence $|b| \le a$.Hence $|b|$ decreases at least by $1$.
If $-b = a$, by executing step 1, $b = a$.
Hence |b| does not change.
In step 2, the algorithm terminates or $|b|$ does not change and $a$ decreases and it goes to step 1.
Hence the algorithm must terminate in finite steps.
QED
Proposition 5
(1) Any two distinct forms of $\mathcal{F}(D)$ are not equivalent under the action of $\Gamma$.
(2) Let $\Gamma_f = \{\sigma \in \Gamma\ |\ \sigma f = f\}$ for $f \in \mathcal{F}(D)$.
Let $S = \left( \begin{array}{ccc}
0 & -1 \\
1 & 0 \end{array} \right)$, 
$T = \left( \begin{array}{ccc}
1 & 1 \\
0 & 1 \end{array} \right)$.
If $D \ne -4, -3$, then $\Gamma_f = \{\pm1\}$ for every $f \in \mathcal{F}(D)$.
Let $g = x^2 + y^2$.
Let $h = x^2 + xy + y^2$.
$\mathcal{F}(-4) = \{g\}$.
$\mathcal{F}(-3) = \{h\}$.
$\Gamma_g = \{\pm 1, \pm S\}$.
$\Gamma_h = \{\pm 1, \pm ST, \pm (ST)^2\}$.
Proof:
This follows immediately from Proposition 2 except $\mathcal{F}(-4) = \{g\}$, $\mathcal{F}(-3) = \{h\}$.But this is easy to see by the method of my answer to this question.
A: Algorithm 1 can be simplified as follows.
Let $[F]$ be the closure of $F$, i.e.
$[F] = \{z \in \mathcal{H}\ |\ |Re(z)| \le 1/2, |z| \ge 1 \}$.
Then $[F] - F = \{z \in \mathcal{H}\ |\ Re(z) = 1/2$ or  $|z| = 1$ and $0 \lt Re(z) \lt 1/2 \}$.
Let $z \in [F] - F$.
If $Re(z) = 1/2$, then $T^{-1}(z) \in F$.
If $|z| = 1$ and $0 \lt Re(z) \lt 1/2$, then $S(z) \in F$.
Hence the following algorithm which transforms any element $z \in \mathcal{H}$ into $[F]$ will do.
Algorithm 1a


*

*If $|Re(z)| \le 1/2$, then go to 2.
Otherwise set $z = T^{-\lfloor \text{Re}(z)+1/2 \rfloor}(z)$.

*If $|z| \ge 1$, then stop.
Otherwise set $z = S(z)$ and go to 1.
Similarly Algorithm 2 can be simplified as follows.
We denote the set $\{(a,b,c) \in \mathfrak{F}^+_0(D)\ |\ |b| \le a \le c\}$ by $[\mathcal{F}(D)]$.
Let $(a,b,c) \in \mathfrak{F}^+_0(D)$.
Suppose $|b| = a$ and $b \lt  0$. i.e. $-b = a$.
Then $T^{-1}(a,b,c) = (a, 2a + b, a + b + c) = (a, a, c) \in \mathcal{F}(D)$.
Suppose $a = c$ and $b \lt 0$.
Then $S(a, b, c) = (a, -b, a) \in \mathcal{F}(D)$.
Hence the following algorithm which transforms any element $(a,b,c) \in \mathfrak{F}^+_0(D)$ into $[\mathcal{F}(D)]$ will do.
Algorithm 2a


*

*If $|b| \le a$ go to 2.
Otherwise set $(a,b,c) = T^{-n}(a, b, c)$, where $n = \lfloor -b/2a +1/2 \rfloor$.

*If $a \le c$, then stop.
Otherwise set $(a,b,c) = S(a, b, c)$ and go to 1.
