\t {Analytic Method} Assume $\chi$ primitive now. If $$ K_{n,\chi}:=(-1)^{n-1}\, 2 n!\left(\frac{N}{2 i}\right)^n $$ then $$ B_{n,\chi}=\frac{K_{n,\chi}}{\pi^n\,\tau(\chi)}\; L(n,\overline{\chi}) $$ There is a simple formula for a $d$ such that $d \cdot B_{n,\chi}$ is an algebraic integer (analogue of Clausen and von Staudt). For $n$ large we can compute $L(n,\overline{\chi})$ {\em very quickly} to high precision; hence we can compute $B_{n,\chi}$ (at least if $\Q(\chi)$ isn't too big, e.g., $\Q(\chi)=\Q$ wouldn't be a problem). (Note, for small $n$ that $L(n,\overline{\chi})$ converges slowly; but then just use the power series algorithm.) Compute the conjugates of $d\cdot B_{n,\chi}$ approximately; compute minimal polynomial over $\Z$; factor that over $\Q(\chi)$, then recognize the right root from the numerical approximation to $d\cdot B_{n,\chi}$.