MultiFactorHenselLifting using symmetric representatives description: This procedure employs the hensel step to lift a factorization with arbitrary many factors, that means to extend a factorization over the field with p elements to a factorization over the ring of congruence classes modulo p^n henselStep(f, T, g, h, s, t, m); multiFactorHenselLifting(b, fOrigin, modpFactorList, T, p, l);
<Text-field style="Heading 1" layout="Heading 1"></Text-field>henselSquareStep := proc( f :: And(polynom(integer), expanded) , T :: name , g :: And(polynom(integer), expanded) , h :: And(polynom(integer), expanded) , s :: And(polynom(integer), expanded) , t :: And(polynom(integer), expanded) , p :: prime , l :: posint ) :: list(And(polynom(integer), expanded)) ; local e :: And(polynom(integer), expanded) , v :: And(polynom(integer), expanded) , q :: And(polynom(integer), expanded) , r :: And(polynom(integer), expanded) , m :: posint , mSquare :: posint , eStar :: And(polynom(integer), expanded) , vStar :: And(polynom(integer), expanded) , gStar :: And(polynom(integer), expanded) , hStar :: And(polynom(integer), expanded) , sStar :: And(polynom(integer), expanded) , tStar :: And(polynom(integer), expanded) , qStar :: And(polynom(integer), expanded) , rStar :: And(polynom(integer), expanded) ; m := p^l; # Pre-condition ASSERTS ASSERT(type(f, polynom(integer, T)), cat("f is not a polynomial in Z[", T, "], check symbols!")); ASSERT(type(g, polynom(integer, T)), cat("g is not a polynomial in Z[", T, "], check symbols!")); ASSERT(type(h, polynom(integer, T)), cat("h is not a polynomial in Z[", T, "], check symbols!")); ASSERT(type(s, polynom(integer, T)), cat("s is not a polynomial in Z[", T, "], check symbols!")); ASSERT(type(t, polynom(integer, T)), cat("t is not a polynomial in Z[", T, "], check symbols!")); ASSERT(m > 1, "modulo m must be greater than 1!"); ASSERT(mods(Expand(f - g * h), m) = 0, "f != gh mod m"); ASSERT(mods(Expand(s * g + t * h - 1), m) = 0, "sg + th != 1 mod m, so g and h are not Bezout-coprime modulo m"); ASSERT(lcoeff(h) = 1, "polynomial h have to be monic!"); ASSERT(degree(f) = degree(g) + degree(h), "deg(f) != deg(g) + deg(h)"); ASSERT(degree(t) < degree(g), "deg(t) >= deg(g)"); ASSERT(degree(s) < degree(h), "deg(s) >= deg(h)"); ASSERT(mods(lcoeff(f), m) <> 0, "lc(f) is a zero divisor of modulo m"); # Step 1 mSquare := m^2; e := mods(Expand(f - g * h), mSquare); ASSERT(divide(e, m, T)); v := quo(e, m, T); # a) Division with remainder in Z/mZ -> q, r q := mods(Expand(Quo(v*s, h, T, r)), m); ASSERT(degree(r) < degree(h), "deg(r) < deg(h)"); print(r); # b) Calculate gStar, hStar in Z/m^2Z gStar := mods(Expand(g + t * e + q * g * m), mSquare); hStar := mods(h + m * r, mSquare); # Step 2 eStar := mods(Expand(s * gStar + t * hStar - 1), mSquare); ASSERT(divide(eStar, m, T)); vStar := quo(eStar, m, T); #toDo ASSERT Vstar = 0? # a) Division with remainder in Z/mZ -> qStar, rStar qStar := mods(Expand(Quo(vStar*s, hStar, T, rStar)), m); ASSERT(degree(rStar) < degree(hStar), "deg(rStar) < deg(hStar)"); print(rStar); # b) Calculate sStar, tStar in Z/m^2Z sStar := mods(s - m * rStar, mSquare); tStar := mods(Expand(t - t * eStar - m * qStar * gStar), mSquare); # Post-condition ASSERTS ASSERT(mods(Expand(f - gStar * hStar), mSquare) = 0, "f* != g*h* mod m^2"); ASSERT(mods(Expand(sStar * gStar + tStar * hStar - 1), mSquare) = 0, "s*g* + t*h* != 1 mod m^2, so g* and h* are not Bezout-coprime modulo m^2"); ASSERT(lcoeff(hStar) = 1, "polynomial hStar have to be monic !"); ASSERT(mods(g - gStar, m) = 0, "gStar != g mod m"); ASSERT(mods(h - hStar, m) = 0, "gStar != g mod m"); ASSERT(mods(s - sStar, m) = 0, "gStar != g mod m"); ASSERT(mods(t - tStar, m) = 0, "gStar != g mod m"); ASSERT(degree(g) = degree(gStar), "deg(g) != deg(gStar)"); ASSERT(degree(h) = degree(hStar), "deg(h) != deg(hStar)"); ASSERT(degree(tStar) < degree(gStar), "deg(tStar) >= deg(gStar)"); ASSERT(degree(sStar) < degree(hStar), "deg(sStar) >= deg(hStar)"); # Return as a list such as the procedure needs to call again simply return [gStar, hStar, sStar, tStar, p, 2*l] end proc: henselLinearStep := proc( f :: And(polynom(integer), expanded) , T :: name , g :: And(polynom(integer), expanded) , h :: And(polynom(integer), expanded) , s :: And(polynom(integer), expanded) , t :: And(polynom(integer), expanded) , p :: prime , l :: posint ) :: list(And(polynom(integer), expanded)) ; local e :: And(polynom(integer), expanded) , v :: And(polynom(integer), expanded) , q :: And(polynom(integer), expanded) , r2 :: And(polynom(integer), expanded) , pl :: posint , plp1 :: posint , eStar :: And(polynom(integer), expanded) , vStar :: And(polynom(integer), expanded) , gStar :: And(polynom(integer), expanded) , hStar :: And(polynom(integer), expanded) , sStar :: And(polynom(integer), expanded) , tStar :: And(polynom(integer), expanded) , qStar :: And(polynom(integer), expanded) , rStar2 :: And(polynom(integer), expanded) ; pl := p^l; plp1 := p^(l+1); # Pre-condition ASSERTS #ASSERT(type(f, polynom(integer, T)), # cat("f is not a polynomial in Z[", T, "], check symbols!")); #ASSERT(type(g, polynom(integer, T)), # cat("g is not a polynomial in Z[", T, "], check symbols!")); #ASSERT(type(h, polynom(integer, T)), # cat("h is not a polynomial in Z[", T, "], check symbols!")); #ASSERT(type(s, polynom(integer, T)), # cat("s is not a polynomial in Z[", T, "], check symbols!")); #ASSERT(type(t, polynom(integer, T)), # cat("t is not a polynomial in Z[", T, "], check symbols!")); #ASSERT(mods(Expand(f - g * h), pl) = 0, "f != gh mod p^l"); #ASSERT(mods(Expand(s * g + t * h - 1), pl) = 0, # "sg + th != 1 mod p^l, so g and h are not Bezout-coprime modulo p^l"); #ASSERT(lcoeff(h) = 1, "polynomial h have to be monic!"); #ASSERT(degree(f) = degree(g) + degree(h), "deg(f) != deg(g) + deg(h)"); #ASSERT(degree(t) < degree(g), "deg(t) >= deg(g)"); #ASSERT(degree(s) < degree(h), "deg(s) >= deg(h)"); #ASSERT(mods(lcoeff(f), p) <> 0, "lc(f) is a zero divisor of modulo p"); # Step 1 e := mods(Expand(f - g * h), plp1); #ASSERT(divide(e, pl, T)); v := quo(e, pl, T); # a) Division with remainder in Z/mZ -> q, r q := mods(Expand(Quo(v*s, h, T, r2)), p); #ASSERT(degree(r2) < degree(h), "deg(r2) < deg(h)"); #print(r2); # b) Calculate gStar, hStar in Z/m^2Z gStar := mods(Expand(g + t * e + q * g * pl), plp1); hStar := mods(h + pl * r2, plp1); # Step 2 eStar := mods(Expand(s * gStar + t * hStar - 1), plp1); #ASSERT(divide(eStar, pl, T)); vStar := quo(eStar, pl, T); #toDo ASSERT Vstar = 0? # a) Division with remainder in Z/mZ -> qStar, rStar qStar := mods(Expand(Quo(vStar*s, hStar, T, rStar2)), p); #ASSERT(degree(rStar2) < degree(hStar), "deg(rStar2) < deg(hStar)"); #print(rStar2); # b) Calculate sStar, tStar in Z/m^2Z sStar := mods(s - pl * rStar2, plp1); tStar := mods(Expand(t - t * eStar - pl * qStar * gStar), plp1); # Post-condition ASSERTS #ASSERT(mods(Expand(f - gStar * hStar), plp1) = 0, "f* != g*h* mod p^(l+1)"); #ASSERT(mods(Expand(sStar * gStar + tStar * hStar - 1), plp1) = 0, # "s*g* + t*h* != 1 mod p^(l+1), so g* and h* are not Bezout-coprime modulo p^(l+1)"); #ASSERT(lcoeff(hStar) = 1, "polynomial hStar have to be monic !"); #ASSERT(mods(g - gStar, pl) = 0, "gStar != g mod p^l"); #ASSERT(mods(h - hStar, pl) = 0, "gStar != g mod p^l"); #ASSERT(mods(s - sStar, pl) = 0, "gStar != g mod p^l"); #ASSERT(mods(t - tStar, pl) = 0, "gStar != g mod p^l"); #ASSERT(degree(g) = degree(gStar), "deg(g) != deg(gStar)"); #ASSERT(degree(h) = degree(hStar), "deg(h) != deg(hStar)"); #ASSERT(degree(tStar) < degree(gStar), "deg(tStar) >= deg(gStar)"); #ASSERT(degree(sStar) < degree(hStar), "deg(sStar) >= deg(hStar)"); # Return as a list such as the procedure needs to call again simply return [gStar, hStar, sStar, tStar, p, l+1] end proc: # This procedure employs the hensel step to lift a factorization with arbitrary many factors, # that means to extend a factorization over the field with p elements to a factorization # over the ring of congruence classes modulo p^n multiFactorHenselLifting := proc( b :: posint, fOrigin :: And(polynom(integer), expanded), modpFactorList :: list(And(polynom(integer), expanded)), T :: symbol, p :: prime, l :: posint) :: list(And(polynom(integer), expanded)); local i :: posint; # Index counter local j :: posint; # Index counter local r :: posint; # Cardinality of the given modpFactorList local f :: table; # Container of f , ... , f[r] local fStar :: table; # Container of the lifted factors fStar, ... , fStar[r] local k :: posint; # The r/2 floored to integer to split the factors f[i] in two parts with similar cardinality local d :: posint; # How offen to call the HenselStep local g :: table; # Container of the g[i], h[i], s[i], t[i] lifted with HenselStep local h :: table; # Container of the g[i], h[i], s[i], t[i] lifted with HenselStep local s :: table; local t :: table; local resultOfHenselStep :: list(And(polynom(integer), expanded)); local resultOfMultiFactor1 :: list(And(polynom(integer), expanded)); local resultOfMultiFactor2 :: list(And(polynom(integer), expanded)); local gNew :: And(polynom(integer), expanded); # Polynomials after called HenselStep d times local hNew :: And(polynom(integer), expanded); local ggT :: And(polynom(integer), expanded); # Pre-condition ASSERTS, set r ASSERT(type(fOrigin, And(polynom(integer, T), expanded)),cat("fOrigin must be an expanded polynomial in Z[",T,"]")); ASSERT(degree(fOrigin) >= 1, "deg(f) < 1"); ASSERT(gcd(lcoeff(fOrigin), p) = 1, " lc(f) is not a unit modulo p"); ASSERT(p > 1, "modulo p must be greater than 1"); r := nops(modpFactorList); ASSERT(r > 0, "modpFactorList is empty"); # Pre-condition ASSERTS, check factors of modpFactorList and set f[i] for i from 1 to r do f[i] := op(i, modpFactorList); ASSERT(type(f[i], And(polynom(integer, T), expanded)), cat("f[", i, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(degree(f[i]) >= 1, "One factor f[i] is constant!"); ASSERT(lcoeff(f[i]) = 1, "One factor f[i] is not monic!"); end do; ASSERT(fOrigin mod p = expand(lcoeff(fOrigin) * mul(f[i], i = 1..r)) mod p, "Input ASSERTION: f != lc(f) * f_1 * ... * f_r mod p"); # 1) Solve Case r = 1 (together with post-condition ASSERTS for this case) if r = 1 then fStar := mods(fOrigin / b, p^l); # ToDo Use Quo instead, assert Rem must be zero ASSERT(type(fStar, And(polynom(integer, T), expanded)), cat("f[", 1, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(lcoeff(fStar) = 1, "fStar is not monic"); ASSERT(f mod p = fStar mod p, "fStar != f mod p"); ASSERT(fOrigin mod p^l = lcoeff(fOrigin) * fStar mod p^l, "f != lc(f) * fStar_1 mod p^l"); return [fStar] end if; # Start solving Case r > 1 # 2a) Further pre-condition ASSERTS, to check, if all f[i] are pairwise Bezout-Coprime if kernelopts(assertlevel) > 0 then for i from 1 to r - 1 do for j from i + 1 to r do # FIXME if p is not prime? ASSERT(gcd(f[i] mod p, f[j] mod p) = 1, "f[i] and f[j] are not pairwise Bezout-coprime modulo p"); end do; end do; end if; # 2b) Set k and d k := floor(r/2); d := ceil(log(l)); # 3) Compute g and h g := mods(b * mul(f[i], i = 1..k), p); ASSERT(type(g, polynom(integer, T)), cat("g[", 0, "] must be a polynomial in Z[",T,"]")); h := mods(mul(f[i], i = k + 1..r), p); ASSERT(type(h, polynom(integer, T)), cat("h[", 0, "] must be a polynomial in Z[",T,"]")); # 4) Compute s and t ggT := mods(Gcdex(g, h, T, 's', 't'), p): # hint: works only, if p is prime! #ASSERT ggT = 1; ASSERT(type(s, And(polynom(integer, T), expanded)), cat("s[", 0, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(type(t, And(polynom(integer, T), expanded)), cat("t[", 0 , "] must be an expanded polynomial in Z[",T,"]")); ASSERT(expand(s * g + t * h) mod p = 1, "s * g + t * h != 1 mod p"); ASSERT(degree(t) < degree(g), "deg(t) >= deg(g)"); ASSERT(degree(s) < degree(h), "deg(s) >= deg(h)"); print(g, h, p^(2^0), 2^0); # 5, 6) Compute g[d] and h[d] by calling HenselStep for j from 1 to d do resultOfHenselStep := henselSquareStep(fOrigin, T, expand(g[j-1]), expand(h[j-1]), expand(s[j-1]), expand(t[j-1]), p^(2^(j-1))); g[j] := op(1, resultOfHenselStep); h[j] := op(2, resultOfHenselStep); s[j] := op(3, resultOfHenselStep); t[j] := op(4, resultOfHenselStep); ASSERT(type(g[j], And(polynom(integer, T), expanded)), cat("g[", j, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(type(h[j], And(polynom(integer, T), expanded)), cat("h[", j, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(type(s[j], And(polynom(integer, T), expanded)), cat("s[", j, "] must be an expanded polynomial in Z[",T,"]")); ASSERT(type(t[j], And(polynom(integer, T), expanded)), cat("t[", j, "] must be an expanded polynomial in Z[",T,"]")); print(g[j], h[j], p^(2^j), 2^j); end do; # 7) gNew := g[d]; hNew := h[d]; # 8) Recursive Call of MultiFactorHenselLifting resultOfMultiFactor1 := multiFactorHenselLifting(lcoeff(gNew), gNew, [seq(f[i], i = 1..k)], x, p, l); ASSERT(nops(resultOfMultiFactor1) = k, "ASSERT failure in ResultOfMultiFactor1!"); resultOfMultiFactor2 := multiFactorHenselLifting(1, hNew, [seq(f[i], i = k+1..r)], x, p, l); ASSERT(nops(resultOfMultiFactor2) = r - k, "ASSERT failure in ResultOfMultiFactor2!"); for i from 1 to r do if i <= k then fStar[i] := op(i, resultOfMultiFactor1); ASSERT(type(fStar[i], And(polynom(integer, T), expanded)), cat("fStar[", i, "] must be an expanded polynomial in Z[",T,"]")); else fStar[i] := op(i-k, resultOfMultiFactor2); ASSERT(type(fStar[i], And(polynom(integer, T), expanded)), cat("fSTar[", i, "] must be an expanded polynomial in Z[",T,"]")); end if; end do; # Post-condition ASSERTS if kernelopts(assertlevel) > 0 then for i from 1 to r do ASSERT(lcoeff(fStar[i]) = 1, "fStar[i] is not monic"); ASSERT(f[i] mod p = fStar[i] mod p, "fStar[i] != f[i] mod p"); end do; end if; ASSERT(gNew mod p^l = expand(lcoeff(gNew) * mul(fStar[i], i = 1..k)) mod p^l, "g != lc(g) * fStar_1 * ... * fStar_k mod p^l"); ASSERT(hNew mod p^l = expand(lcoeff(hNew) * mul(fStar[i], i = k+1..r)) mod p^l, "h != lc(h) * fStar_{k+1} * ... * fStar_r mod p^l"); ASSERT(fOrigin mod p^l = expand(lcoeff(fOrigin) * mul(fStar[i], i = 1..r)) mod p^l, "Output ASSERTION: f != lc(f) * fStar_1 * ... * fStar_r mod p^l"); return [seq(fStar[i], i = 1..r)]; end proc: # save procedure in lib printf("Mintcheck henselSquareStep: \134n"); maplemint(henselSquareStep); printf("Mintcheck henselLinearStep: \134n"); maplemint(henselLinearStep); savelibname := MY_LIB_FILE: savelib('multiFactorHenselLifting', 'henselSquareStep','henselLinearStep', MY_LIB_FILE); #LibraryTools:-ShowContents(MY_LIB_FILE); #LibraryTools:-Delete('bezoutpk',MY_LIB_FILE); #LibraryTools:-Delete('henselLinearStep',MY_LIB_FILE); Mintcheck henselSquareStep: These parameters have the same name as constants: 1, 3 These local variables were used before they were assigned a value: r::And(polynom(integer),expanded), rStar::And(polynom(integer),expanded) Mintcheck henselLinearStep: These parameters have the same name as constants: 1, 3 These local variables were used before they were assigned a value: r2::And(polynom(integer),expanded), rStar2::And(polynom(integer),expanded) LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2J1EoRXhhbXBsZUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUrZXhlY3V0YWJsZUdGMS8lLG1hdGh2YXJpYW50R1EsYm9sZC1pdGFsaWNGJy8lK2ZvbnR3ZWlnaHRHUSVib2xkRicvJSVzaXplR1EjMTJGJy8lJWJvbGRHUSZmYWxzZUYnRjIvJTBmb250X3N0eWxlX25hbWVHUSkyRH5JbnB1dEYnL0Y1USdub3JtYWxGJw==JSFH restart; kernelopts(assertlevel=0): trace(henselSquareStep); f := 4*x^3 + x - 1: g := x+1: h := x^2-x-1: s := -x-1: t := 1: p := 3: result := henselSquareStep(f, x, g, h, s, t, p, 1): g := result: h := result: s := result: t := result: #result2 := henselSquareStep(f, x, g, h, s, t, p, 2); #result := henselLinearStep(f, x, g, h, s, t, p, 2); #g := result: #h := result: #s := result: #t := result: #result := henselLinearStep(f, x, g, h, s, t, p, 3); STFoZW5zZWxTcXVhcmVTdGVwRzYi {--> enter henselSquareStep, args = 4*x^3+x-1, x, x+1, x^2-x-1, -x-1, 1, 3, 1 LCZJInhHNiIhIiJGJSIiIg== LCZJInhHNiIhIiJGJSIiIg== <-- exit henselSquareStep (now at top level) = [4*x-2, x^2-4*x-4, 2*x+2, 1, 3, 2]}