Exploring (RSA (001)

[Paul S. Penrod]

On Thu, 29 Aug 1996 Scottauge at aol.com wrote:

> Exploring Rivest, Shamir, Adelman algorithm, but hoping someone out there is
> interested in very large number manipulations.
> 
> RSA suggests choosing two prime 100 digit numbers p and q for beginning of
> key generation.
> 
> These numbers are obviously beyond the long type of a C program.

Don't just assume that the long type is too small. For most compilers 
this is true, but the long data type (at least as I have seen the 
definition from ANSI 1991) is twice the base word (INT) length, where the 
word size is generally defined to be the size of the register length of the 
CPU in question to which the compiler has been developed for. Intel blurs 
this distinction by still supporting 8,16,32 and now 64 bit registers in 
the same CPU, and there are various flavors of the same C compiler that 
accomodate both 16 and 32 bit word sizes (read INT).

Just for the sake of arugment, an unsigned long in a 64 bit compiler 
represents integers from 0 to 2^128-1. This is fairly large. However, 
Fred Gruenburg (a RAND fellow) and some of his cohorts back in 1957 came 
up with a method of bit ticking that allowed them to calculated 
astronomically large prime numbers very quickly. It had something to do 
with a known mathematical progression of primes in the set of integer 
numbers as X -> 00. If I can find the information, I will post how he 
did it.

One other method involves using character strings to manipulate large 
numbers "long hand". This method is fairly slow compared to bit ticking, 
but it works and was used in some of the old style 8 bit systems I worked 
on many moons ago. You set up at least 3 long strings and use them as 
registers for all mathematical operations, plus allow for an overflow flag. 
This simulates some of the old style decimal machine in their operations.

> 
> Other than using Mathematica or Maple, I would like to use C or perferrably
> C++.
> 
> Just some basics such as multiplication, addition, subtraction, division,
> mod, etc over the Z set.
> 
> 

...Paul