2
$\begingroup$

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...

1 Answers 1

1

You could use the implemented function Intseq.

It takes two arguments, first the integer you want to expand, second the base, and returns the expansion in a list. So for example, the base 2 representation of $10$ is $1010$ and

Intseq(10,2)

returns

[ 0, 1, 0, 1 ]

The coefficient of the highest power of $2$ is the rightmost one. You can use

Reverse(Intseq(10,2))

to reverse the order and get $[ 1, 0, 1, 0]$.

  • 1
    I've just started testing this, and for a p with 43452 digits, the old algorith took about 90 seconds, yours took less than one, it's probably safe to say this is a LOT better. Thanks!2012-11-17