Valhalla Legends Archive

I need to implement RSA encryption/decryption/key generation for my algorithms class; I already have all the code written and correct, but I need a big number library (2⁸⁰?) to use to check the timing requirements.  Our school has a LEDA license, but I can only use this if I scp my project and ssh onto one of the lab machines, and this is a big pain.  Is anyone aware of a free (besides GMP - I spent about an hour trying to get it to work and gave up) arbitrary length number library?

Correct me if I'm wrong, which I could be, but can't you process it in 4-byte blocks?  For SHA-1, for sure, you can just store it in an int[5].

That would be about the same as writing my own bignum library, i think.  I would have to do special things every time I wanted to do something mathematical instead.

Quote from: K on March 22, 2004, 11:38 AM
That would be about the same as writing my own bignum library, i think.  I would have to do special things every time I wanted to do something mathematical instead.

Ok, so write your own then

For sha-1, all operations are designed to operate on it int-by-int.  I guess what you need to do doesn't, in that case, so forget I mentioned it

Quote from: iago on March 22, 2004, 11:45 AM

Quote from: K on March 22, 2004, 11:38 AM
That would be about the same as writing my own bignum library, i think.  I would have to do special things every time I wanted to do something mathematical instead.

Ok, so write your own then

For sha-1, all operations are designed to operate on it int-by-int.  I guess what you need to do doesn't, in that case, so forget I mentioned it

It's possible that there's a method that does it int by int, but I don't know of it; basically I need to generate ~200-digit primes as well as do modular exponetiation on large numbers.  

As a side note, if I were to write my own, I wonder what would be fastest?  Storing the number as an array of digits or actually manipulating dword by dword, etc?

I read somewhere that generating a prime that big is so difficult that quasi-primes are often used (almost-prime-numbers).  Not sure if it's true, though.

OpenSSL has a big number library as a subcomponent, but check the licenses on it to see if it's compatible with what you want to do.

Quote from: K on March 22, 2004, 01:49 PM
As a side note, if I were to write my own, I wonder what would be fastest?  Storing the number as an array of digits or actually manipulating dword by dword, etc?

If you store it as an array of digits, you'll be manipulating it in base 10. It would be faster to manipulate it in a larger base, like base 2**32 or 2**16. The principle will be the same, so assuming you don't run into limitations in your compiler, they should be about the same to code.

Quote from: iago on March 22, 2004, 02:18 PM
I read somewhere that generating a prime that big is so difficult that quasi-primes are often used (almost-prime-numbers).  Not sure if it's true, though.

the probability of generating a prime number randomly is ln(n) / n.  Basically I'm generating a large random number and then running several iterations of fermat's little theorem over it.

Basically, for any number A < P and any prime P working in modulo M:
A^P-1 mod M = 1

Each iteration has a 1/2 chance of proving P composite except for Carmichael Numbers which have a lower number of witnesses.

Quote from: Adron on March 22, 2004, 03:39 PM

Quote from: K on March 22, 2004, 01:49 PM
As a side note, if I were to write my own, I wonder what would be fastest?  Storing the number as an array of digits or actually manipulating dword by dword, etc?

If you store it as an array of digits, you'll be manipulating it in base 10. It would be faster to manipulate it in a larger base, like base 2**32 or 2**16. The principle will be the same, so assuming you don't run into limitations in your compiler, they should be about the same to code.

I've been thinking about this and it seems like it would be easy.  Just store a (doubly) linked list of DWORDS along with a count of how many nodes and a boolean to keep track of negatives.  Addition, Subtraction, and Bit Manipulation also seem like they would be easy to implement, but multiplication/division and exponentiating could be difficult.  I think I'll work on this now that I've tested and verified that my RSA code works for large numbers on a lab machine with LEDA.

You can use the regular multiplication and division algorithms that you'd use for multiplying two large decimal numbers on paper.

How do I teach my computer to use a ti-83?

Quote from: iago on March 25, 2004, 06:48 PM
How do I teach my computer to use a ti-83?

That would be a step down, considering paper extends near infinitely, all you have to do is get more, while a ti-83 can't be extended with much memory at all.

Quote from: Adron on March 25, 2004, 08:58 PM

Quote from: iago on March 25, 2004, 06:48 PM
How do I teach my computer to use a ti-83?

That would be a step down, considering paper extends near infinitely, all you have to do is get more, while a ti-83 can't be extended with much memory at all.

Granted, but TI-83 can go up to 10**10000 or something crazy like that, and that would take a whole lot of paper