As a part of programming an Elliptic Curve Method with montgomery coordinates in Magma, I need to have an algorithm to convert a number from decimal notation to binary notation. Since there is no inbuilt function for this (as far as I know?), I made one myself. However, for the numbers I'm trying to decompose, the binary representation algorithm takes up 90% of the execution time (which is horrible).
Current algorithm is:
binarydigits := function(n)
m:=Floor(Log(2,n));
digits:=[];
while m ge 0 do
k:=n div 2^m;
digits:=Append(digits,k);
n:=n-k*2^m;
m:=m-1;
end while;
return digits;
end function;
Any suggestions to improve this? All I could think of was storing 2^m and calculating 2^(m-1) from that, etc...