1Function: idealredmodpower 2Section: number_fields 3C-Name: idealredmodpower 4Prototype: GGUD0,U, 5Help: idealredmodpower(nf,x,n,{B=primelimit}): return b such that x * b^n = v 6 is small. 7Doc: let \var{nf} be a number field, $x$ an ideal in \var{nf} and $n > 0$ be a 8 positive integer. Return a number field element $b$ such that $x b^n = v$ 9 is small. If $x$ is integral, then $v$ is also integral. 10 11 More precisely, \kbd{idealnumden} reduces the problem to $x$ integral. Then, 12 factoring out the prime ideals dividing a rational prime $p \leq B$, 13 we rewrite $x = I J^n$ where the ideals $I$ and $J$ are both integral and 14 $I$ is $B$-smooth. Then we return a small element $b$ in $J^{-1}$. 15 16 The bound $B$ avoids a costly complete factorization of $x$; as soon as the 17 $n$-core of $x$ is $B$-smooth (i.e., as soon as $I$ is $n$-power free), 18 then $J$ is as large as possible and so is the expected reduction. 19 \bprog 20 ? T = x^6+108; nf = nfinit(T); a = Mod(x,T); 21 ? setrand(1); u = (2*a^2+a+3)*random(2^1000*x^6)^6; 22 ? sizebyte(u) 23 %3 = 4864 24 ? b = idealredmodpower(nf,u,2); 25 ? v2 = nfeltmul(nf,u, nfeltpow(nf,b,2)) 26 %5 = [34, 47, 15, 35, 9, 3]~ 27 ? b = idealredmodpower(nf,u,6); 28 ? v6 = nfeltmul(nf,u, nfeltpow(nf,b,6)) 29 %7 = [3, 0, 2, 6, -7, 1]~ 30 @eprog\noindent The last element \kbd{v6}, obtained by reducing 31 modulo $6$-th powers instead of squares, looks smaller than \kbd{v2} 32 but its norm is actually a little larger: 33 \bprog 34 ? idealnorm(nf,v2) 35 %8 = 81309 36 ? idealnorm(nf,v6) 37 %9 = 731781 38 @eprog 39