Public Key Cryptography

Date: 06/18/97 at 18:20:19
From: Anonymous
Subject: RE: NFS, QFS, etc. methods for determining the factors of 

This may seem to be a very general question, but I'm trying to find 
out more about number thoery, specifically in the area of prime 
numbers and public-key cryptography (RSA system). Could anyone give me 
a brief, general description of how these methods work (number field 
sieve, quadratic field sieve)?

Thanks for your time.

Date: 06/19/97 at 16:31:07
From: Doctor Daniel
Subject: RE: NFS, QFS, etc. methods for determining the factors of 

Hi there,

You asked about different ways of determining the factors of large 
numbers in the context of the RSA cryptosystem.  That's frankly a 
little outside the standard range of our problems (and we don't have 
terribly many math doctors who specialize in discrete applied-style 
math), so I think I'm going to have to declare you as having given us 
a problem which isn't K-12.  If you're actually not done with high 
school yet, feel free to give this problem back to us; we tend to be 
psyched to take hard questions from younger users!

However, I'll give you some pointers which should help you more than a
little, if you've got easy access to an academic library.

The first is the presentation of factoring algorithms, RSA, etc. in 
chapter 33 of _Introduction to Algorithms_ by Corman, Leiserson and 
Rivest.  This is the standard text for algorithms, and is conveniently 
co-authored by Ron Rivest, who's the R in RSA.

A much more difficult article is probably "Algorithms in number 
theory" in _The Handbook of Theoretical Computer Science, vol I: 
Algorithms and Complexity_, edited by J. van Leeuwen, MIT Press, 1990.  
This will probably have more than you could possibly care to have 
about 1990-era algorithms for factoring, modular arithmetic, etc.,  
but it'd be fairly complete.  

Of course, the essential questions when it comes to factoring are 
these: 

1) Is there an "efficient" in the sense that word is used in 
theoretical computer science, algorithm to factor numbers; in other 
words, given a number N, is there an algorithm to factor N which takes 
time polynomial in log N?

2) How easy is it, in a good algorithm, to enlist the help of other
computers; in other words, how easy is it to derive good parallel 
algorithms for this problem.

These problems mostly remain open; if the first is ever answered in 
the affirmative, it will have enormous effects on the whole of 
computer science, let alone have a truly bad influence on world 
banking technologies.

Good luck!

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 06/19/97 at 20:27:14
From: Anonymous
Subject: RE: (Response to) Re: NFS, QFS, etc. methods for determining 

Dear Dr. Math,
    
Thanks for your response.
     
Firstly, regarding your question (1), there are some sub-polynomial 
time factoring algorithms. I believe that NFS is asymtopic to 
e^(something, I'll have to look this up). However, I don't quite 
understand the "jacobi field equations" used to determine whether a 
number is "smooth", and hence a possiblity for being one of the prime 
factors. The NFS, with some modifications, including multi-partite
variations on the matrix can be used broken up into pieces for an
individual computer to solve and return to the main server.
    
Anyway, aside from the very difficult, and almost computationally
infeasable job of factoring the product of two prime numbers, what are 
the main ways of determining in the first place whether a number is 
prime or not? The resources that I have (Applied Cryptography, Modular 
Arithmetic and Multi-Variable Matrix Algebra, PKC Developers Guide, 
Mathematics in C++, Introduction to Algorithms, etc.) don't adaquetly 
explain _WHY_ their source code works. Do you have any idea where I 
can get more theoretical information on number theory?
    
Also, I am having difficulty in obtaining the books and resources
that were listed in your original reply. Most public libraries and 
bookstores don't have them. The college libraries I went to were 
somewhat deficient in this relatively new field of mathematics. Do you 
have any suggestions as to where I could find them?
   
Thanks for taking the time to answer this question.

Date: 06/20/97 at 14:07:14
From: Doctor Daniel
Subject: RE: (Response to) Re: NFS, QFS, etc.  methods for determining 

Hi again,

First off, I should warn you that you may be falling into a pretty 
serious set of problems.  Considering that primality and number theory 
are now central to possibly the only financially crucial (read: used 
constantly by banks) application of theoretical computer science 
methods (well, that's a gross overgeneralization, but...), the methods 
do get very complicated very quickly.

Conversely, it's really terrific math (though not my personal cup of 
tea); might as well start off with the good stuff!

I'll start off by giving you a description of what I meant by finding 
an "efficient" algorithm; undoubtedly, if you have access to Corman, 
Leiserson, Rivest's _Introduction to Algorithms_ (if not, you can get 
it through amazon.com; it's not cheap ($60), but a good book to have), 
it goes into more detail, but here goes:

We say that an algorithm runs in "polynomial time" if we can prove 
that, on an input encoded in length n, there exists three positive 
integers, c, k and n0, such that if n > n0, the algorithm terminates 
before c*n^k time has happened. We also assume that during the running 
of the algorithm, no arithmetic on numbers with lengths exponential in 
n occurs, and no need to have infinite (or even exponential in n) 
precision after the decimal point occurs when we use fractions.

Unless I'm very mistaken, it's still an open problem whether there's a
polynomial time algorithm for this problem:

FACTORING:

Input: A positive composite integer z, which can be expressed as a 
binary number with length log-base-2 (z).

Output: Two positive integers p and q such that pq = z.

It's also open whether this problem is NP-Complete, which is the
mathematical phrase that means a problem is "hard."  

It's also open how hard this problem is "in general"; in other words, 
are there special purpose algorithms that work for the vast majority 
of inputs?

As to finding if a number is prime, THAT's not known to be provable in
polynomial time, either. However, things are better here; we can come 
up with an algorithm which works in polynomial time which makes random 
choices, and which will never be wrong when it says a number is prime 
and which is wrong less than 1/2 of the time when it says a number is 
composite. Thus, we can run it 100 times, and know that if it says 
the number is composite, it only has a 2^-100 chance of being wrong.  
Or, alternatively, if a nasty number theory conjecture is true, then 
we have a polynomial time algorithm for the problem also.

Here's a bunch more references for you. To be honest, I think you 
might do really well to find yourself a math prof at a local college, 
if there is one near you, and enlist his or her help in getting you 
resources as well. If you really want to learn about this stuff 
(which is FABULOUSLY cool), it might help to have a good guide.

Here's a good book on theoretical CS which has nice chapters about 
number theory, cryptography, primality testing, polynomial algorithms, 
randomized computation, etc.:

Christos Papadimitriou, _Computational Complexity_, 1994 (Addison-
Wesley) ($50 through amazon.com)

Here's something that seems reasonable about primality on the web:

  http://www.utm.edu/research/primes/   

Books on number theory (these will be HEAVY):

G. H. Hardy and E.M. Wright _An Introduction to the Theory of Numbers, 
5th Edition_, 1979 (Oxford) ($45 through amazon.com)

I. Niven and H.S. Zuckerman _An Introduction to the Theory of Numbers, 
5th Edition_, 1991 (Wiley) ($78 through amazon.com)

For that matter, the Handbook of Theoretical CS I suggested to you is 
$53 via amazon.

(NO, I am not suggesting you drop $300 and buy all of these! 
Conversely, especially if you can find a supporter at a local college, 
_they_ can probably convince their library to get them!)

I know how frustrating it is having trouble getting decent books. If 
you live within an hour's drive of a university, they'd be reasonably 
likely to have many of these; if not, you may be able to convince them 
to get them via inter-library loan. The most important thing to do 
with college libraries is to cultivate a decent relationship with a 
faculty member so they'll take you seriously.

The University of Tennessee link above also has tons of links to 
recent articles. There are lots and lots of other relevant books, but 
starting with the good stuff and then working your way down to 
something easier seems simpler to me. If you want to understand this 
stuff, rather than just being able to vaguely slog your way through 
someone's code, it's worth learning from the top. (The problem with 
_that_ is that it may be a while before you look at primality testing 
again!)

I hope I've helped you out without bogging you down. I realize that 
I've not answered a single question of yours. However, your problems 
are hard enough that I think you'll get much more out of using 
resources that are better written than what I'd expect we'd be giving 
you. If you'd like more suggestions, feel free to write back; I'll 
let another Dr. Math answer you.

Good luck and keep up the interesting study!

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/