# Implementation of Decompose

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, "NumberTheoryNextPrimeDump"];
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?

-
The reference for the method used by Decompose is: "Fast polynomial decomposition algorithms" by V. S. Alagar and Mai Thanh. I believe it appeared in the proceedings of the EuroCal '85 conference. I've no idea what those BitAnds are from. –  Daniel Lichtblau Feb 1 '13 at 20:43
I checked. The BitAnd calls come from some polynomial factorization code used by Decompose. –  Daniel Lichtblau Feb 1 '13 at 21:11
Thanks for that. The source was very easy to follow. –  RiemannZeta Feb 4 '13 at 4:29
Per Daniel Lichtblau's comment, the method used by Decompose is based on the following reference:
The BitAnd calls come from some polynomial factorization code used by Decompose.