"There is a remarkably close parallel between the problems
of the physicist and those of the cryptographer. The system on which a
message is enciphered corresponds to the laws of the universe, the intercepted
messages to the evidence available, the keys for a day or a message to
important constants which have to be determined. The correspondence is
very close, but the subject matter of cryptography is very easily dealt
with by discrete machinery, physics not so easily."
Alan Turing
quoted in Cryptonomicon by Neal Stephenson, Avon Books 1999
Fermat factorization is a little more interesting than it might seem.
It is described in Exercise 4 of Chapter IV Section 2. The obvious
attack on an RSA code is to try to factor n = pq.
If either p or q is small, then we can factor n
easily by simply trying to divide it by the first few primes, say up
to 100,000 or 1,000,000. To preclude this attack, p and q
are chosen to be roughly the same size. But if they are choosen too
close to each other, then we can try factoring n by starting
in the middle, rather than at either end. So we look for factors near
the square root of n. That is the first idea behind
Fermat factorization.
The second idea reduces the number of trial divisions. If p
and q are close, then s = (p - q)/2 is
small, and n = t2 - s2
where t = (p + q)/2. Instead of trying to divide
n by all the odd numbers near the square root of n,
we can take numbers t that are a little bit bigger than
the square root of n and check each to see whether
t2 - n is a perfect square s2,
in which case n factors as (t + s)(t - s).
You can see the advantage in Exercise 4. You need only try three
values, 152843, 152844, and 152845, of t to get the factor 153649.
To get 153649 directly by trying each odd number, you would make 404
attempts.
Carmichael numbers:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041,
46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401,
172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561,
399001, 410041, 449065, 488881, 512461
The Prime Pages
See
The Prime Pages
for lots of things about prime numbers.
In particular, have a look at "How many primes are there?".
Fermat primes
See
Prime
factors of Fermat numbers