Efficient exact cyclotomic norm solving with a supplied integer factorization

Reject if either real embedding of $\xi$ is negative, and return zero if $\xi =0$. Signs of $a+b\sqrt{2}$ are determined by coefficient signs and comparison of $a^2$ with $2b^2$, so these are exact polynomial bit operations. A zero real embedding implies $\xi =0$ by injectivity. Otherwise both embeddings are positive. Clear a rational square denominator by choosing the least $r\ge 0$ with $\eta =4^r\xi \in R$. Since the input uses explicit denominators, $r=O(L)$ and $\eta$ has $O(L)$-bit coefficients. Its positive rational norm is $N_R(\eta )=2^{4r-\mathrm{\ell }}n$, so its factorization is obtained from the supplied one by adjoining the known factor $2$. All its prime factors and their multiplicities have total size polynomial in $L$.

Here are polynomial bit gcd and associate procedures for [F1], with coefficient growth controlled. Use $N_R(a+b\sqrt{2})=\mathrm{\mid }{a}^2-2b^2\mathrm{\mid }$ and $N_O(z)=\mathrm{\mid }z{\mathrm{\mid }}^2\mathrm{\mid }{z}^{\bullet }{\mathrm{\mid }}^2$. The real coefficient-rounding error has norm at most $1\mathrm{/}2$. Write the cyclotomic rounding error as $C+D\omega$, where $C=x+iy$, $D=z+it$ and $\mathrm{\mid }x\mathrm{\mid },\mathrm{\mid }y\mathrm{\mid },\mathrm{\mid }z\mathrm{\mid },\mathrm{\mid }t\mathrm{\mid }\le 1\mathrm{/}2$. Put $S=\mathrm{\mid }C{\mathrm{\mid }}^2+\mathrm{\mid }D{\mathrm{\mid }}^2$. If $S\le 9\mathrm{/}10$, then $N_O(C+D\omega )=\mathrm{\mid }{C}^2-i{D}^2{\mathrm{\mid }}^2\le S^2\le 81\mathrm{/}100$. If $S>9\mathrm{/}10$, each of the four squared real coordinates exceeds $3\mathrm{/}20$, since the other three sum to at most $3\mathrm{/}4$. Thus $\mathrm{\mid }\mathrm{Re}{C}^2\mathrm{\mid },\mathrm{\mid }\mathrm{Re}{D}^2\mathrm{\mid }<1\mathrm{/}10$ and $\mathrm{\mid }\mathrm{Im}{C}^2\mathrm{\mid },\mathrm{\mid }\mathrm{Im}{D}^2\mathrm{\mid }\le 1\mathrm{/}2$. Expanding the square gives $\mathrm{\mid }{C}^2-i{D}^2{\mathrm{\mid }}^2\le \mathrm{\mid }C{\mathrm{\mid }}^4+\mathrm{\mid }D{\mathrm{\mid }}^4+2(\mathrm{\mid }\mathrm{Re}{C}^2\mathrm{\mid }\mathrm{\mid }\mathrm{Im}{D}^2\mathrm{\mid }+\mathrm{\mid }\mathrm{Im}{C}^2\mathrm{\mid }\mathrm{\mid }\mathrm{Re}{D}^2\mathrm{\mid })\le 1\mathrm{/}2+1\mathrm{/}5=7\mathrm{/}10$. Hence every cyclotomic remainder contracts the norm by at most $\rho =81\mathrm{/}100$. As $(81\mathrm{/}100{)}^4<1\mathrm{/}2$, every four nonzero divisions halve the norm. This explicit estimate needs no compactness premise.

Before and after each division, balance any nonzero remainder $z$ by multiplying it by a power of $\lambda$, which changes neither its norm nor the generated principal ideal. In $R$ arrange $\sqrt{N_R(z)}\le \mathrm{\mid }z\mathrm{\mid }<\lambda \sqrt{N_R(z)}$; in $O$ arrange $N_O(z{)}^{1\mathrm{/}4}\le \mathrm{\mid }z\mathrm{\mid }<\lambda N_O(z{)}^{1\mathrm{/}4}$. The other embedding then has comparable magnitude, since their absolute product is respectively $N_R(z)$ or $\sqrt{N_O(z)}$. The fixed inverse linear conversion from embeddings to power-basis coordinates bounds every balanced coefficient by a constant times $N_R(z{)}^{1\mathrm{/}2}$ or $N_O(z{)}^{1\mathrm{/}4}$. All comparisons can be performed without numerical approximations by squaring and comparing elements of $\mathbb{Q}(\sqrt{2})$. For inputs with $B$-bit coordinates, the initial norm has $O(B)$ bits, and its nonzero conjugates are bounded above by $2^{O(B)}$ and below by $2^{-O(B)}$ using their integer product. Hence initial balancing uses $O(B)$ unit multiplications. Thereafter all balanced coordinates and each exact quotient have $O(B)$ bits; division in the fixed-degree number field uses a fixed number of rational operations. Rounding produces $O(B)$-bit remainders, whose balancing again uses $O(B)$ multiplications. Step 2.1 bounds the number of divisions by $O(B)$. This proves polynomial bit cost for gcds; exact quotient and associate tests have polynomial cost as well. Units used in balancing do not affect any gcd ideal.

Recover all $R$-prime classes above each odd rational prime $p$ in step 1.1 as follows. If $p\equiv 3,5(\mathrm{m}\mathrm{o}\mathrm{d}8)$, the polynomial $X^2-2$ has no root by [F3], so $R\mathrm{/}(p)={\mathbb{F}}_p[X]\mathrm{/}(X^2-2)$ is a field by [F4], and $p$ is already prime in $R$. If $p\equiv 1,7(\mathrm{m}\mathrm{o}\mathrm{d}8)$, compute $b^2=2(\mathrm{m}\mathrm{o}\mathrm{d}p)$ using [F3]. Evaluation at the two distinct roots $b,-b$ identifies $R\mathrm{/}(p)$ with ${\mathbb{F}}_p\times {\mathbb{F}}_p$: interpolation of a linear polynomial gives the inverse, since $2b$ is invertible. The gcds ${\pi }_{+}={\gcd }_R(p,\sqrt{2}-b)$ and ${\pi }_{-}={\gcd }_R(p,\sqrt{2}+b)$ generate the preimages of the two component kernels. Their quotients are fields, so these gcds are nonassociate primes, and the component description shows $({\pi }_{+}{\pi }_{-})=(p)$. These procedures give every $R$-prime over $p$ and use the modular-root algorithm and polynomial gcds of step 3.1.

For an odd $p$ and an $R$-prime $\pi$ just obtained, put $E=R\mathrm{/}(\pi )$. Because $2$ is invertible modulo $\pi$ and $\omega =(\sqrt{2}\mathrm{/}2)(1+i)$, there is an explicit isomorphism $O\mathrm{/}(\pi )=E[i]=E[T]\mathrm{/}(T^2+1)$: the displayed formula expresses $\omega$ in the right-hand ring, and $i={\omega }^2$ expresses its inverse map. If $p\equiv 7(\mathrm{m}\mathrm{o}\mathrm{d}8)$, then $E={\mathbb{F}}_p$ and $T^2+1$ is irreducible by [F3]. Thus $O\mathrm{/}(\pi )$ is a field, and $\pi$ is prime also in $O$; its class is fixed by conjugation because $\pi$ is real. If $p\equiv 1,5(\mathrm{m}\mathrm{o}\mathrm{d}8)$, compute $b^2=-1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and put $h=b+i$. If $p\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}8)$, compute $b^2=-2(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and put $h=b+i\sqrt{2}$; the root exists since both characters of $-1$ and $2$ are $-1$ by [F3]. In these cases $T^2+1$ splits into distinct roots in $E$: they are $\pm b$ in the first case and $\pm b\mathrm{/}\sqrt{2}$ in the second. Hence $O\mathrm{/}(\pi )$ is a product of two fields, by the same explicit interpolation as in step 4.1. The ideals generated by $(\pi ,h)$ and $(\pi ,h^{†})$ select the two distinct component kernels. Consequently $t={\gcd }_O(\pi ,h)$ and $t^{†}$ are nonassociate primes, with $\pi \sim t^{†}t$. This proves prime recovery and its completeness, rather than merely asserting a splitting table.

Include $\delta$ as the sole prime class over $2$ by [F2]. Step 4.1 and step 5.1 now give a finite list of all $O$-prime classes over the rational prime divisors of $N_R(\eta )$. Every prime of $O$ dividing $\eta$ appears: it divides the integer $\eta {\eta }^{\bullet }$, and the prime-divisor property of [F1] makes it divide one of those rational primes. Repeated exact division of $\eta$ by the displayed generators, with associate tests to remove duplicate classes, therefore gives its full prime-class exponent list. The remaining quotient has norm one and is a unit, since otherwise unique factorization would supply a missing prime divisor. Compute conjugation orbits by conjugating the generators and testing associates. Reject exactly when a fixed class has odd exponent; otherwise form $s$ by the allocation in [F2]. This decision and allocation are complete, including the ramified class and arbitrary multiplicities, by [F2].

Put $e=\eta \mathrm{/}(s^{†}s)$. By [F2], this is a real unit of $R$, positive at both embeddings; [F1] gives $e={\lambda }^{2j}$ for an integer $j$. Recover its exponent by multiplying $e$ by ${\lambda }^{-1}$ while it is at least $\lambda$, or by $\lambda$ while it is below $1$, recording the signed number of multiplications. The resulting unit in $[1,\lambda )$ is $1$ by [F1], so this finds $2j$ exactly, including negative exponents. Set $v={\lambda }^j$ and return $t=vs\mathrm{/}{2}^r$. Then $t^{†}t=v^2{s}^{†}s\mathrm{/}{4}^r=\xi$. This also states the actual unit-recovery algorithm; no search over arbitrary coefficients is used.

All rational primes in step 1.1 have $O(L)$ bits, and their multiplicities sum to $O(L)$ since their product is an $O(L)$-bit integer. Each gcd in step 4.1 and step 5.1 is normalized as in step 3.1, so its output has $O(L)$-bit coefficients. The number of prime generators is at most four per rational prime. A prime in $O$ has integer norm at least two; consequently step 6.1 uses $O(L)$ successful divisions. Products and quotients of at most $O(L)$ such factors have at most $O(L^2)$ coefficient bits: a product in fixed degree adds operand bit lengths plus a constant, and a field inverse is given by the product of the other conjugates divided by the integer norm. Thus $s$, $e$ and the intermediate divisions have polynomial bit length. An element ${\lambda }^j$ with $B$-bit coefficients has $\mathrm{\mid }j\mathrm{\mid }=O(B)$, because its two real absolute embeddings are ${\lambda }^j$ and ${\lambda }^{-j}$ and both are bounded by $2^{O(B)}$. Step 7.1 therefore takes polynomially many bit operations and produces a polynomial-size answer. Modular-root calls are the only randomized operations; their number is $O(L)$ and each has expected polynomial cost by [F3]. This proves the full expected polynomial bit bound, without using the exhaustive factor search in [F1].

For the bounded case, put $\alpha =(\sqrt{2}{)}^k\xi =A+B\sqrt{2}\in R$. Both absolute embeddings of $\alpha$ are at most $2^{k\mathrm{/}2}$, so $\mathrm{\mid }A\mathrm{\mid }\le 2^{k\mathrm{/}2}$ and $\mathrm{\mid }B\mathrm{\mid }\le 2^{k\mathrm{/}2}\mathrm{/}\sqrt{2}$. If $k$ is even, $\xi =(A+B\sqrt{2})\mathrm{/}{2}^{k\mathrm{/}2}$; if $k$ is odd, $\xi =(2B+A\sqrt{2})\mathrm{/}{2}^{(k+1)\mathrm{/}2}$. These expressions and their reductions have $O(k+1)$ coefficient bits. Moreover $\mathrm{\mid }{N}_R(\alpha )\mathrm{\mid }=2^k\xi {\xi }^{\bullet }\le 2^k$ is an integer, so the reduced nonzero numerator $n$ is at most $2^k$ (and hence at most $4^k$); its supplied prime factorization has polynomial length in $k+1$. Thus $L$ is polynomial in $k+1$, and step 8.1 yields the asserted bounded-input complexity. For the candidate case, write $u=z\mathrm{/}(\sqrt{2}{)}^h$ with $z\in O$. Then $(\sqrt{2}{)}^{2h}\xi =2^h-z^{†}z$ is a real element of $O$, hence lies in $R$ by [F1]; the least residual exponent is at most $2h$. Applying the preceding bounds with that exponent proves $n\le 4^h$ and expected polynomial cost in $h+1$. Zero was already handled in step 1.1. For unrestricted inputs, real units can have norm one but arbitrarily large coefficients; retaining $L$ in the general statement is therefore necessary.

We calibrate the last bound for $H=h+1\ge 1$. The bounded residual lies in $2^{-h}R$, so write $\xi =(a+b\sqrt{2})\mathrm{/}{2}^h$ with $\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid }\le 2^h$, by adding and subtracting its two embeddings. Using the least clearing exponent of step 1.1 gives $r\le \lceil h\mathrm{/}2\rceil$ and $\eta$-coefficient bit lengths at most $h+2$. The input coefficient denominators divide $2^h$. For prime $n=p$, $p\le 2^{2h}$; hence its bit length is at most $2h+1$. The cases $n=0,1$ omit these prime calls. At most two real primes and four cyclotomic primes over $p$, together with $\delta$, need be represented. Reusing the modular roots, at most eight modular-root calls and sixteen ring gcds cover step 4.1 and step 5.1, including harmless duplicate computations. All gcd inputs have coefficient bit lengths at most $8H$: the modular roots are reduced below $p$, and a balanced real factor has coefficients at most $2\sqrt{N_R(p)}=2p$, so converting it to the cyclotomic basis still fits this bound. The real and cyclotomic norm bounds for an integer element with $b$-bit coordinates are respectively $2^{2b+2}$ and $2^{4b+8}$, because each complex embedding has magnitude at most $4\cdot 2^b$. Step 2.1 therefore requires fewer than $32(b+2)$ divisions per gcd.

Here is explicit storage and loop bookkeeping for these gcds. Multiplication in the power basis of $O$ has at most four signed product terms per output coefficient, so multiplying elements with coefficient bit lengths $b_1,b_2$ gives lengths at most $b_1+b_2+3$; the real basis obeys the same bound. The other field conjugates only permute or negate coordinates. Forming $x\mathrm{/}y$ by multiplying $x$ by the other three conjugates of $y$ and dividing by $N_O(y)$ gives numerator and denominator lengths at most $b_x+3b_y+12$ and $4b_y+12$. Balanced gcd operands have lengths at most $b+6$, by the embedding bounds in step 3.1 and the preceding norm estimate. Thus the unbalanced integer remainder has lengths below $8(b+8)$. Its nonzero embeddings lie between $2^{-8(b+8)-2}$ and $2^{8(b+8)+2}$, by the integer norm and the upper bound for the other embedding. Since $\lambda >2$, balancing needs fewer than $32(b+8)$ unit multiplications, including comparisons; during balancing each embedding stays between its initial and final values, so all coefficient lengths stay below $16(b+8)$. The quotient formulas keep temporary rational coordinates below $512(b+8)$ bits. Allowing eight fixed-degree field actions per balancing iteration and $256$ for division, norm and rounding, $32(b+2)$ divisions, and initial balancing, fewer than $2^{21}(b+8{)}^2$ field actions suffice per gcd. Here an action means a fixed-degree field multiplication, quotient, norm, sign comparison or coordinate rounding, with their integer-operation costs expanded below.

For the remaining work, the number of prime factors of $\eta$ counted with multiplicity is at most ${\log }_2{N}_O(\eta )\le 4h+8\le 16H$. Balanced prime-generator coefficients have at most $32H$ bits, including $\delta$. Multiplying at most $16H$ generators gives coefficient lengths below $2^{10}{H}^2$; successive exact divisions increase length by at most $3(32H)+12$ each by step 11.1, hence stay below $2^{12}{H}^2$. The quotient $e=\eta \mathrm{/}(s^{†}s)$ has length below $2^{14}{H}^2$. If $e={\lambda }^m$, its two embedding bounds and $\lambda >2$ give $\mathrm{\mid }m\mathrm{\mid }<2^{15}{H}^2$, so both exponent recovery and construction of ${\lambda }^{m\mathrm{/}2}$ use fewer than $2^{16}{H}^2$ unit multiplications in total. A unit multiplication increases length by at most three; monotonicity of the embedding sizes during exponent reduction, or the direct power formula during reconstruction, bounds every stored coordinate, including the returned numerator and denominator, by $B=2^{20}{H}^2$ bits. Sixteen gcds with $b\le 8H$, at most $16H$ successful divisions and at most one failed division per generator, at most $25$ associate comparisons, and these unit loops, are together fewer than $2^{40}{H}^4$ field actions; this also includes reading, denominator clearing, allocation, and checking $t^{†}t=\xi$ exactly before returning. A field action can be implemented using fewer than $4096$ signed integer operations and rational reductions on values of at most $4096(B+1)$ bits: expand the at most four coordinates, the at most three conjugate factors for inversion, and reduce each rational coordinate by the ordinary integer gcd. Binary schoolbook addition, multiplication and long division of $d$-bit integers take fewer than $2^{10}(d+1{)}^2$ bit steps, by their nested digit loops. An integer gcd has at most $2d+2$ divisions, since every two Euclidean divisions at least halve its positive divisor. For $d\le 4096(B+1)$, $4096$ such integer-gcd costs are below $2^{63}(B+1{)}^3$. Maintaining the at most four binary array-index counters costs at most $64(B+1)$ further bit operations per digit action, since their lengths are at most $13+\lceil {\log }_2(B+1)\rceil \le 16(B+1)$. Including this overhead and the rational reductions, one field action therefore costs less than $2^{70}(B+1{)}^4$ bit steps. These bounds deliberately allow more integer operations and bits than any of the displayed fixed-degree formulas require.

Finally, for a modular-root call with prime bit length $d$, the sampling implementation of [F3] uses an expected at most eight raw bit strings before finding a nonsquare: sampling accepts with probability at least $1\mathrm{/}4$, and half its accepted residues are nonsquares. Binary powering uses at most $2d$ modular multiplications, and the at most $d$ order-reduction iterations use at most $4d$ modular multiplications each. The schoolbook bounds in step 12.1 consequently put the expected cost of one call below $2^{20}(d+1{)}^5$ bit steps, including sampling and initialization. Since $d\le 2H$, eight calls cost less than $2^{31}{H}^5$ in expectation. The deterministic part is less than $2^{40}{H}^4{2}^{70}(2^{20}{H}^2+1{)}^4\le 2^{194}{H}^{12}$. Adding the random part gives a bound below $2^{195}{H}^{12}\le 2^{200}{H}^{20}=P(h)$. For $n=0,1$ the omitted prime calls only reduce the bound. This proves the explicit majorant for the actual chosen arithmetic loops, with no timing assumption about composite inputs.