in less than one second for $n$ up to one hundred (cryptographic applications of [`IP1S`]{}usually require smaller values of $n$, typically $\leq 30$, for efficiency reasons).

### Matrix Square Root Computation {#matrix-square-root-computation .unnumbered}

It is well known that computing square roots of matrices can be done efficiently using numerical methods (for instance, see [@grant]). On the other hand, it seems difficult to control the bit complexity of numerical methods. In [@DBLP:conf/issac/ChistovIK97 Section 3], the authors consider the problem of computing, in an exact way, the square root of matrices over algebraic number fields. As presented, it is not completely clear that the method proposed is polynomial-time as some coefficients of the result matrix lie in extensions of nonpolynomial size, see [@Cai1994]. However, by applying a small trick to the proof of [@DBLP:conf/issac/ChistovIK97], one can compute a solution in polynomial-time for various field of characteristic $\neq 2$. In any case, for the sake of completeness, we propose two polynomial-time algorithms for this task. First, a general method fixing the issue encountered in [@DBLP:conf/issac/ChistovIK97 Section 3] is presented in Section \[ss:computation\]. To do so, we adapt the technique of [@Cai1994] and compute the square root as the product of two matrices in 