Addition Chains for Mersenne Numbers

[NeillC]

I am have been obsessed with the Mersenne numbers for quite a few years but for a different reason than most people here.
We define \(l(n)\) as the length of the smallest addition chain for \(n\).

I am desperately trying to find an addition chain for \(2^n-1\) thats short:

\(l(2^n-1) < n + l(n) - 1\)

I have covered all cases with \(l(n)\leq9\) so that has \(n\leq512\) to give you some idea of the sizes of the integers. The first case I can't handle is \(n=127\).

I expect I can learn a lot from what you guys do. My first source of performance problems is caused by me using boost for large integers on Windows. boost layers on top of compiler support for 128 bit integers that are unsupported in windows for both the MSVC c++ compiler and the Intel c++ compiler. So it ends up doing calculations in 32 bit chunks rather than 64 bit. I used fixed size integers in boost rather than the dynamic versions.
What do you guys use or suggest for these size integers? The most complex thing I do is division and I try to limit that as it kills my performance.

[VBCurtis]

gmplib.org : arbitrary precision.