Suppose $a\in\mathbb{G}$ is an arbitrary element in an abelian group $\mathbb{G}$ of order $|\mathbb{G}|$. The group $\mathbb{G}$ need not be a multiplicative modulo group and/or a cyclic group. Is there any algorithm to solve the equation $x^2=a\in\mathbb{G}$ in $O(\log{|\mathbb{G}|})$-time when $|\mathbb{G}|$ is even?
When $|\mathbb{G}|=2k-1$ is odd, it can be solved as $x=a^{\tfrac{|\mathbb{G}|+1}{2}}=a^k\in\mathbb{G}$. Using the repeated squaring algorithm it takes $O(\log{|\mathbb{G}|})$-time. However, it does not work with even $|\mathbb{G}|$ as it yields a fraction in the exponent of $a$.
Also, it is efficient to solve this equation in special cases of even order groups like $\mathbb{Z}^*_p$ where $p=3 \pmod{4}$ is a prime as $x=a^{\tfrac{p+1}{4}}\pmod{p}$.
But, is there any $O(\log{|\mathbb{G}|})$-time algorithm for even order group, in general?
$\def\eqd{\stackrel{\text{def}}{=}}$ If $\ |\Bbb{G}|=\prod_\limits{i=1}^np_i^{n_i}\ $, with $\ n_i\ge1\ $ for $\ i=1,2,\dots,n\ $,$\ p_1=2\ $, and $\ p_i\ $ are distinct primes for $\ i=2,3,\dots,n\ $, then the structure theorem for finitely generated abelian groups tells us that $$ \Bbb{G}\cong\bigotimes_{i=1}^n\bigotimes_{j=1}^{r_i}C_{p_i^{t_{ij}}} $$ where $\ C_k\ $ is cyclic of order $\ k\ $, and $\ \sum_\limits{j=1}^{r_i}t_{ij}=n_i\ $.
If $$ a=\prod_{i=1}^n\prod_{j=1}^{r_i}a_{ij}\ , $$ with $\ a_{ij}\in C_{p_i^{t_{ij}}}\ $, then $\ a\ $ will have a square root if and only if the order of $\ a_{1j}\ $ is strictly less than $\ 2^{t_{1j}}\ $ for each $\ j\in\big[1,r_1\big]\ $. The relative ease with which you can find the square root of $\ a\ $, however, will depend on whether you have easy access to $\ a_{1j}\ $ for each $\ j\in\big[1,r_1]\ $ and to an element lying in the same cyclic subgroup $\ C_{2^{t_{1j}}}\ $ that contains $\ a_{1j}\ $ and whose order is strictly greater than that of $\ a_{1j}\ $. This may well depend on exactly how the group $\ \Bbb{G}\ $ and the element $\ a\ $ are specified.
Let $\ b_1\eqd\prod_\limits{j=1}^{r_1} a_{1j}\ $ and $\ b_2\eqd\prod_\limits{i=2}^n\prod_\limits{j=1}^{r_i} a_{ij}\ $. Then $\ a=b_1b_2\ $, the order of $\ b_1\ $ divides $\ 2^{n_1}\ $, and the order of $\ b_2\ $ divides $\ \prod_\limits{i=2}^np_i^{n_i}\ $. You can use the extended Euclidean algorithm to find an integer $\ \beta\in\left[1, \prod_\limits{i=2}^np_i^{n_i}-1\right]\ $ such that $\ 2^{n_1}\beta\equiv1\pmod{\prod_\limits{i=2}^np_i^{n_i}}\ $. Let $\ \gamma\eqd\frac{1+\prod_\limits{i=2}^np_i^{n_i}}{2}\ $. Then \begin{align} a^{2^{n_1+1}\beta\gamma}&=b_1^{2^{n_1+1}\beta\gamma}b_2^{\big(2^{n_1}\beta\big)2\gamma}\\ &=1\cdot b_2^{2\gamma}\\ &=b_2\ . \end{align} Thus, $\ a^{2^{n_1}\beta\gamma}\ $ is a square root of $\ b_2\ $, and we'll be able to find a square root for $\ a\ $ if and only if we can find one for $\ b_1\ $.
If $\ g\ $ is a generator of $\ C_{2^s}\ $, then so is $\ g^{2i+1}\ $ for every $\ i=$$\,1,$$\,2,$$\,\dots,$$\,2^{s-1}-1\ $, and these are the only elements of $\ C_{2^s}\ $ with order $\ 2^s\ $, and the only elements that do not have a square root. If $\ c\in C_{2^s}\ $ has order $\ 2^u\ $, with $\ u<s\ $, then $\ c=g^{2^{s-u}d}\ $ for some odd $\ d<2^u\ $, and the integer $\ 2^{s-u}d\ $ can be found easily with the Pohlig-Hellman algorithm. Now $\ \big(g^{2^{s-u-1}d}\big)^2=c\ $, and so $\ g^{2^{s-u-1}d}\ $is a square root of $\ c\ $ which can be easily calculated.
Thus, in the case of the group $\ \Bbb{G}\ $ above, if you know $\ a_{1j}\ $ and an element $\ g_j\ $ of order strictly greater than $\ a_{1j}\ $ with $\ a_{1j}\in\langle g_j\rangle\ $, then you can use the above procedure to find a square root $\ \alpha_j\ $ of $\ a_{1j}\ $, and if you can do this for every $\ j=1,2,\dots,r_1\ $, then \begin{align} \left(\prod_{j=1}^{r_1}\alpha_j\right)^2&=\prod_{j=1}^{r_1}\alpha_j^2\\ &=\prod_{j=1}^{r_1}a_{1j}\\ &=b_1\ . \end{align} Therefore $$ \left(a^{2^{n_1}\beta\gamma}\prod_{j=1}^{r_1}\alpha_j\right)^2=b_2b_1=a $$ and hence $\ a^{2^{n_1}\beta\gamma}\prod_\limits{j=1}^{r_1}\alpha_j\ $ is a square root of $\ a $.
The problem with this is that the form in which you've been given $\ \Bbb{G}\ $ and $\ a\ $ might make it difficult to find the set of $\ a_{1j}\ $ and corresponding $\ g_j\ $ you'll need to carry out the above procedure. While you can always find $\ b_1=a\left(a^{2^{n_1+1}\beta\gamma}\right)^{-1}\ $ fairly easily, it's not clear that you'll always have a convenient way of splitting it up into its factors $\ a_{1j}\ $.
If you have a way to generate elements of $\ \Bbb{G}\ $ uniformly at random, then any such randomly generated $\ \rho\ $ will be of the form $$ \rho=\prod_{i=1}^n\prod_{j=1}^{r_i}\rho_{ij}, $$ with $\ \rho_{ij}\in C_{p_i^{t_{ij}}}\ $ for each $\ i,j\ $, and for each $\ j=1,2,\dots,r_1 $ $\ \rho_{1j}\ $ will be a generator of $\ C_{2^{t_{1j}}} $ with probability $\ \frac{1}{2}\ $, $$ \rho^{\prod_\limits{i=2}^np_i^{n_i}}=\prod_{i=1}^{r_1}\rho_{1j}^{\prod_\limits{i=2}^np_i^{n_i}}\ , $$ and $\ \rho_{1j}^{\prod_\limits{i=2}^np_i^{n_i}}\ $ will still be a generator of $\ C_{2^{t_{1j}}} $ if $\ \rho_{1j}\ $ is. An interesting question (interesting to me, at least) is whether this can be exploited to find the square root of $\ b_1\ $ in the case when you have no other convenient way to get hold of the set of $\ a_{1j}\ $ and corresponding $\ g_j\ $ needed in the procedure already described.