How to implement long separation for huge numbers (bignums)

Question

I am trying to implement a long split for bignums. I cannot use a library such as GMP, unfortunately, due to limitations of the embedded programming. In addition, I want the intellectual exercise to learn how to implement it. So far, I have had addition and multiplication using arrays of length in bytes (so each byte is similar to the value of base-256).

I'm just trying to start implementing a unit / module, and I want to know where to start? I found a lot of optimized (aka unreadable) code on the network that does not help me, and I found a lot of high-tech mathematical documents from which I can not bridge the gap between theory and implementation.

If someone could recommend a popular algorithm and point me to a simple one to understand the explanation that tends to implant, that would be fantastic.

-edit: I need algorithms that work when the dividend is ~ 4000 bits and the divisor is ~ 2000 bits.

-edit: Will this algorithm work with a 256 base? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit: Do I really have to use an algorithm (Newton's division)? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Answer 1

If you want to learn, start with the pencil and paper method you used in elementary school. Believe it or not, this is essentially the same O (n ^ 2) algorithm that most bignum libraries use for numbers that are in the range you are looking for. The difficult first step is called “factor assessment,” and this is likely to be the most difficult to understand. Once you understand this, the rest should be easy.

A good recommendation is Knuth's "Seven-Dimensional Algorithms." He has a lot of discussion about different ways of estimating coefficients both in the text and in the exercises. This book has chapters on bignome implementations.

Answer 2

Do you use void Four1 (long double [], int, int) in your code, and then fold, and then do the inverse transform well, I got multiplication by work, but when I tried to make the division the same way as it spat out one result and then exit, so I can’t help, but if you have a volume called "Numeric Recipes in C ++", go closer to the end and you will find what you are looking for, it actually starts with Page 916 - 926.

Answer 3

This question is older than 2 years, but for these numbers you can see the source code of OpenSSL. It runs RSA with these number numbers, so it has many math routines optimized for numbers from 1000 to 4000 bits.