Associated Topics || Dr. Math Home || Search Dr. Math

### 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

```

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

Hi there,

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

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,

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

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
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
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
(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.:

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
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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search