Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)
while m ge 0 do
k:=n div 2^m;
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...

share|cite|improve this question
up vote 1 down vote accepted

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



[ 0, 1, 0, 1 ]

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


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

share|cite|improve this answer
Please let me know if you try this and it's actually faster. – Gregor Bruns Nov 17 '12 at 1:30
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! – user49719 Nov 17 '12 at 11:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.