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