Hi All,

I am optimizing in space a C++ Big Integer class.

Like most big integer classes, I must keep track within the class of
the effective number of base-10 digits of an object of the class,
which can be determined from the number of (8*2^x)-bit segments that
comprise the big integer (GMP calls them limbs).

Using a full unsigned int on a 32-bit machine to keep track of such
segments yields a maxium of 4,294,967,295 segments, which would be a
massive base-10 number.

I would like to consolidate multiple fields of my class so that only 1
32-bit bit-field is use to represent several fields, including the
segment count.  At present, I have 28-bits avalable, which is plenty
for a count, but I want to reserve some bits for just-in-case.

What is a reasonable number of base-10 digits in a big integer class
for operations beyond crypto?

Hi All,

I am optimizing in space a C++ Big Integer class.

Like most big integer classes, I must keep track within the class of
the effective number of base-10 digits of an object of the class,
which can be determined from the number of (8*2^x)-bit segments that
comprise the big integer (GMP calls them limbs).

Using a full unsigned int on a 32-bit machine to keep track of such
segments yields a maxium of 4,294,967,295 segments, which would be a
massive base-10 number.

I would like to consolidate multiple fields of my class so that only 1
32-bit bit-field is use to represent several fields, including the
segment count. At present, I have 28-bits avalable, which is plenty
for a count, but I want to reserve some bits for just-in-case.

What is a reasonable number of base-10 digits in a big integer class
for operations beyond crypto?

-Le Chaud Lapin-

On Apr 30, 6:12 pm, Le Chaud Lapin <jaibudu...@gmail.com> wrote:





Hi All,

I am optimizing in space a C++BigIntegerclass.

Like mostbigintegerclasses, I must keep track within the class of
the effective number of base-10 digits of an object of the class,
which can be determined from the number of (8*2^x)-bit segments that
comprise thebiginteger(GMP calls them limbs).

Using a full unsigned int on a 32-bit machine to keep track of such
segments yields a maxium of 4,294,967,295 segments, which would be a
massive base-10 number.

I would like to consolidate multiple fields of my class so that only 1
32-bit bit-field is use to represent several fields, including the
segment count.  At present, I have 28-bits avalable, which is plenty
for a count, but I want to reserve some bits for just-in-case.

What is a reasonable number of base-10 digits in abigintegerclass
for operations beyond crypto?

The biggest RSA key size I've ever heard discussed was about 15k bits,
which was what NIST suggests is equivalent to a 256 bit symmetric
key.  Of course I've never seen anyone actually try to use one bigger
that 8192 bits (and even that is rather silly).  To implement modular
exponentiation, you'll need intermediates of twice that length, so for
the bigger limit you'd need around 10k decimal digits.  So 16 bits, if
a nice round number helps, sounds like a reasonable choice.

OTOH, what's the point here?  Even for short RSA keys you're talking
about needing 1024 bits of storage for the number and saving what?  16
bits, or a small multiple thereof?  Two or three percent?  Is that
really worth it?

Perhaps if you were expecting a large number of small(ish) numbers, a
compressed format (with automatic conversions to and from the normal
larger format) might be worthwhile.  Not to mention that you'd
eliminate all that bit field manipulation in the main part of your
processing.- Hide quoted text -