Preface: Using GMS 2.3
I started doing an implementation of RSA for encrypting my networking system, and I almost finished it, except that I had to create a BigInteger struct first. I did so, and it supports super huge numbers (haven't tested above 128 bits). Right now, it supports addition, subtraction, multiplication, exponentiation (with normal integers. it's not hard to expand this, except that I'm not entirely sure how to handle past the first "digit", as you'll read later in this comment), bitwise shifting, comparison, and a crude and extremely (could take YEARS to calculate) modulo function. The last thing I was doing was implementing sign, as it was previously restricted to unsigned values. I then have to learn how to divide a BigInteger by another BigInteger. I tried reading the Java implementation of BigInteger, but it's enormous and complex. I also found a video and started following their algorithm, but it requires negative numbers, which I hadn't started supporting yet as of writing the divide function.
The way my BigIntegers work is actually very simple. I have a chunk size, defined currently as 8 bits (could easily swap to 16 bits at the change of a macro, but not sure if larger calculations resulting from this would be accurate given that GM numbers are all doubles). They have an array of numbers, each number having the defined chunk size in bits (so in my case, every chunk AKA element in the array stores a number from 0-255). As for what I say in the next paragraph, whether a BigInt is positive or negative is a simple variable called
signed that is -1 or +1. It just changes what the operation functions do (for example, if this bigint is signed -1 and we are subtracting a signed -1 big int, that's just an addition and you keep being signed -1). Chunks are stored in big-endian. The way addition works is just like how you would have learned in school, except each "digit" is actually a chunk. So, you can think of my BigIntegers as being base-256 numbers, where each chunk is a "digit" (except, big-endian so reverse the digits. Big-endian is just because it's easier to manage).
The only reason I need BigInteger is because RSA keys are meant to be 128 bits, and my mod_power (modulus exponentiation) function can't support BigIntegers yet. I converted it to work with BigInts, but I need a proper modulo function first. My idea was a series of repeated divisions instead of repeated subtractions (which is how my modulo function works right now), which would be many
many times faster. The issue is that my division algorithm requires the use of negative BigInts, so I'm stuck trying to get that working first. So far, it works with subtraction (as explained above. I haven't fully finished subtraction, as when A - B and B > A (ignoring sign), it's better to do B - A and swap the sign, so you never actually deal with negative numbers) and multiplication (super simple. if the two signs are the same, make it positive. if they are different, make it negative), but not yet addition (should be easy. if we are signed -1 and we are adding a signed -1, addition and keep the sign. if we are signed +1 and we are adding a signed -1, subtraction). Subtraction is another case of what you learned in school, just borrowing from the next chunk if the subtracting chunk is larger than ours.
Btw, my RSA code
can generate prime numbers, but to generate prime numbers large enough to be cryptographically secure, it's really slow, because it has to run a Fermat primality test and then repeated Rabin-Miller primality tests, to generate a number that is
probably prime. And it would need to work with BigIntegers, to make the primes arbitrarily large, which just makes them even slower. Instead of making the user wait for that, I just have a global array of every large prime number from 800k to 1m. That's not very secure though, as I should use the whole 32-bit space, or even the whole 64-bit space.
@FrostyCat
Do you have anything to say regarding what I've written above? I've seen you on the forums for years from time to time, back to when I was first learning GM (first time I ever used it was GM8.1 back in 2007-2008 ish). I was wondering if you knew anything about arbitrary-precision algorithms, or how to do division with them.