RSA / BigInt

[SymbolicFrank]

So, there are a few examples that do this. They use third-party dll's (hard to port), BCD (why would you do that?), floating-point with configurable accuracy (???) or other strange solutions.

Yes, using BCD makes sense when your only goal is to print the number in decimal. For all other requirements, I would simply prefer a flat, binary representation. As that doesn't exist for Free Pascal (that I know of) and I need it for my next project, I think I'll start with implementing this.

Although it won't be BigInt, as much as "variable size integer math", probably with a fixed point extension.

[BeniBela]

BCD (why would you do that?),

When you have floating points it is useful.

You calculate 123.456 * 0.1 in BCD faster than the input is converted to binary and you know there are no rounding errors.

[Thaddy]

http://wiki.freepascal.org/BcdUnit

BCD is a format that has no rounding errors for its given precision. It is very important in standards compliant software in banking and accounting.

[guest60499]

http://wiki.freepascal.org/BcdUnit

BCD is a format that has no rounding errors for its given precision. It is very important in standards compliant software in banking and accounting.

I think he's referring to the possibility of encoding numbers in a way similar to BCD that does not waste some fractional part of the total bytes in use. As in, you only use 9 of 16 positions in a nibble.

As for the OP: libgmp is one of the best libraries out there though it does not have cryptographic modifications for constant time or randomized time computations which you may want (at least that I am aware of). Being C it is extremely easy to port. Seeing as making use of that library means you inherit all of the testing and bugfixes put into it, I would strongly suggest making an include file defining the functions inside of it and then wrapping the mathematics in objects for convenience.

If you need functions with a cryptographic tilt then there are libraries for optimized modulus arithmetic, etc.

[SymbolicFrank]

As I said in the OP, BCD is interesting only if you start with a decimal number and want to print the result again in decimal. It's not only inefficient use of space, but it is also very slow. (4-bit calculations vs. 64-bit ones). And perhaps for smallish numbers (MediumIntegers). If you want it big and exact, you should either use fixed-point numbers, or rational numbers (ie.: 3/7, store the formula).

Libgmp is (L)GPL and not all that portable (you need a precompiled .dll / .so), and you might suffer precision loss if you don't set the right precision before your calculation (ie. they don't auto-grow). Not a fan.

Anyway, MathMan linked me to this BigInteger unit. That looks about perfect. I modified it to work in Free Pascal. It compiles, but it needs some rigorous testing. I might port the BigDecimals and BigRationals as well, if it goes smoothly.