The problem came from a research paper that I'm reading. Please inform me if you need any clarification.
So I was implementing the algorithm 1 from literature 1. It aims to reduce a quaternion ideal into another powersmooth norm representative that, as $\mathbb Z$-module, is isomorphic to the original one. Below, everything sits inside the quaternion algebra $B$, where $i^2=-1, j^2=-p, ij = k = -ji$.
First, there is a minor issue in this algorithm. In step 7, $S_1, S_2$ is too large to exist. Since it is required that $S_1S_2>p^4$ and also required to be $(7/2)\log p$ powersmooth, $S_1, S_2$ must not exists, at least asymptotically speaking. However, I believe that it is merely a typo so below I will modify to require only $S_2>p^2\log p$ and $S_1> p \log p$.
Anyway, I successfully compute $\alpha, \beta_1$ and they all satisfy the requirements: $\gcd(\mathsf{Nrd}(\alpha),N^2) = N$ and $\mathsf{Nrd}(\beta_1) = N S_1$. However, at step 13, beta2 seems to not even exists most of the time. I shall stress that I did not deliberately construct counter-example. Instead, after just "randomly" pick suitable alpha, beta1, I always failed to find its corresponding beta2.
See [2] for the exact setting of a counter example. I confirmed this by seeing $\beta_1$ as a linear transformation by left multiplication on $\mathcal{O}_0$ as a $\mathbb{Z}/N$ module, where N is a large prime; then solve for the 4 by 4 matrix equation. Note that $\beta_1$ is not invertible, meaning that the matrix of beta1 should be singular and by linear algebra one could simply do the Gaussian ellimination to check whether a $\beta_2$ solution exists.
Is there anything wrong with my computation or counter-example? What else should I do to find the $\beta_2$?
Thank you.
[1] https://eprint.iacr.org/2016/1154.pdf
[2] http://codepad.org/IVStsQbK
The photo of algorithm 1 are from [1].
