Implementation of Decompose

Question

I'm curious as to how Decompose works so I decided to use Trace with the option TraceInternal -> True.

For NextPrime, this works well:

AppendTo[$ContextPath, "NumberTheory`NextPrimeDump`"];
Trace[NextPrime[45],TraceInternal->True]

{NextPrime[45],
{Block[{res},res=integerNextPrime[45];RuleCondition[res,IntegerQ[res]]],
{res=integerNextPrime[45];RuleCondition[res,IntegerQ[res]],
{{integerNextPrime[45],{Block[{res},res=45+1+Mod[45,2];
While[!PrimeQ[res],res+=2];RuleCondition[res,IntegerQ[res]]],
{res=45+1+Mod[45,2];While[!PrimeQ[res],res+=2];RuleCondition[res,IntegerQ[res]],
{{{Mod[45,2],1},45+1+1,47},res=47,47},{While[!PrimeQ[res],res+=2],
{{{res,47},PrimeQ[47],True},!True,False},Null},
{{{res,47},IntegerQ[47],True},RuleCondition[res,True],res,47},47},47},47},res=47,47},
{{{res,47},IntegerQ[47],True},RuleCondition[res,True],res,47},47},47},47}

Above, we can see some code and get an idea of how NextPrime works. But when I do this with Decompose I get something weird:

With[{p = Expand[(x^2+x+1)^2+2(x^2+x+1)+1]},
  Trace[Decompose[p, x], TraceInternal -> True]
]

{Decompose[4+4 x+5 x^2+2 x^3+x^4,x],{BitAnd[29,8],BitAnd[8,29],8},
{BitAnd[29,4],BitAnd[4,29],4},{BitAnd[29,2],BitAnd[2,29],0},
{BitAnd[29,1],BitAnd[1,29],1},{BitAnd[14,4],BitAnd[4,14],4},
{BitAnd[14,2],BitAnd[2,14],2},{BitAnd[14,1],BitAnd[1,14],0},
{BitAnd[31,8],BitAnd[8,31],8},{BitAnd[31,4],BitAnd[4,31],4},
{BitAnd[31,2],BitAnd[2,31],2},{BitAnd[31,1],BitAnd[1,31],1},
....,
{4+4 x+x^2,x+x^2}}

Is there any way to tell where these bitwise ANDs are coming from? Isn't TraceInternal supposed to show all workings during an execution?

Answer 1

Per Daniel Lichtblau's comment, the method used by Decompose is based on the following reference:

• Fast polynomial decomposition algorithms by V. S. Alagar and Mai Thanh (Google Books link)

The BitAnd calls come from some polynomial factorization code used by Decompose.