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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.