don@allegra.UUCP (01/23/84)
I found this article in my latest issue of the Manchester Guardian:
CODES RISK IN MATHS ADVANCE
Secret codes on which national and international security rest appear
to have been broken wide open by an advance in mathematical analysis
that, so far, has been ignored by the government.
The mathematical system, which involves multi-dimensional vectors is
claimed by its author, the cyberneticist Arnold Arnold, to have solved a
famous mathematical problem known as Fermat's Last Theorem.
Although this appears to be remote from matters of security, the
system has the power to find with ease prime numbers of any magnitude
and to factor, very rapidly, large numbers that are themselves products
of prime numbers (prime numbers are those which can be divided by only
themselves and one).
Although governments maintain a very high security wall around their
coding techniques, it is widely known that many high level codes
including those which control the "interlocks" governing procedural
progression up Nato's nuclear ladder in the event of war, make use of
prime numbers.
Nuclear triggers themselves are in many cases, prime number sequences,
and the highest level diplomatic codes make use of numerical structures
which ultimately rest on prime numbers.
The reason for making use of prime numbers is that the pattern of the
series--although recently described in a huge polynomial equation--has
hitherto seemed inpenetrable. This in turn has meant that attempts to
break codes have demanded huge computers and extremely long computing
times.
Only a couple of years ago, when academic interest in factoring and in
cryptography began it embarrass the US Government, experts were claiming
that a 60 digit number that was itself the product of prime numbers
could form a secure basis for cryptography because it would take
hundreds of years of computing time to resolve it.
Conventional techniques of number crunching, in which almost every step
of arithmetic has to be tried have advanced to the point at which a
number of that size can probably be factored in a day.
It is believed that the difficulty of factoring grows exponentially with
the number of digits and that, for example, a number of 100 digits
would still require many years of analysis before it could be
factored.
According to Mr. Arnold, who points out that the cracking of Fermat is
merely a sideshoot of the development of much more powerful techniques,
the number of digits is now irrelevant to the level of security.
Using his technique, it should be possible to go directly to any level
of prime numbers, including numbers which are many thousands of times
larger than any examined hitherto, and to analyse in seconds the key
components of prime number codes.
Since the techniques he uses are known to have been under investigation
by Russian mathematicians for several years but have been virtually
ignored in the West the position of the Government and its cypher staff
at its communications centre at Cheltenham and elsewhere, could be
embarrassing.ignatz@ihuxx.UUCP (01/24/84)
It might be even worse: From the Jan. 14th, 1984 issue of Science News: Science News of the week Faster Factoring for Cracking Computer Security For years, mathematicians have known that the number (11^64)+1 is really the product of at least two smaller numbers multiplied together, but this 67-digit number until recently withstood their repeated attempts at finding its factors. Last month, mathematicians at Sandia National Laboratories in Albuquerque, N.M., made it the longest "hard" number ever to be factored by a general-purpose factoring routine. That record is likely to fall within the next few weeks when the Sandia group, using their specially designed method for factoring on a Cray computer, expects to crack a 71-digit number. Only eight years ago, the best anyone could do, using a day of computer time, was to factor a difficult 40-digit number. While factoring was once the pursuit of a few eccentric mathematicians, it has now become an important activity for people concerned about computer security (SN: 7/3/82, p.12). Several important cryptographic methods (SN: 9/26/81, p. 205) depend on the inherent difficulty in factoring compared with finding out whether a number is prime (divisible only by itself or one)(SN: 3/6/82,p. 158). The recent rapid advances in factoring larger and larger numbers are making some computers vulnerable that just a year ago were thought to be adequately protected by cryptographic systems. Sandia's Gustavus J. Simmons says, "Factoring is one of a whole class of problems that are so difficult that they're at the edge of computational feasibility. You quickly get to numbers that you can't factor." However, during the last year os so, mathematicians have begun to take advantage of the way particular computers handle information internally by matching a mathematical scheme or algorithm for solving a problem to the way the machine operates most efficiently. At Sandia, James A. Davis and Diane B. Holdridge started with a method for factoring called the "quadratic sieve,", originally invented by Carl Pomerance of the University of Georgia in Athens. This method breaks the problem of factoring a big number into an enormous number of smaller problems, each of which provides some information about the original factorization. The answers go into large arrays in the computer's memory. The "sieving" operation requires selecting and manipulating entries at locations that are all the same distance apart. The Cray is designed to do just that. It can hop directly from one regularly spaced array position to another instead of counting off every location along the way. Matching the Pomerance algorithm to the Cray's "architecture" cut the time to factor a 55-digit number from more than 50 hours to less than four hours. Then, Davis improved the factoring algorithm by finding a way to make the sieving operation more efficient. After this change, a 58-digit number that had required 8.8 hours took only 1.8 hours to factor. The Sandia researchers reached a new limit when they tried a 67-digit number. The million words of high-speed memory within the Cray simply wasn't big enough to hold all the necessary numbers. Holdridge had to steal "bits" from the computer's operating system to fit the computation within the computer. Now, the Sandia group is switching to a larger model of the Cray computer that will allow them to factor even bigger numbers. To put their factoring method through the toughest possible tests, the Sandia group has been working on numbers of special interest to mathematicians, including those numbers on a "10 most-wanted" list of candidates for factoring. Six numbers from that list have already been done at Sandia. Their current target is (10^71)-1. Although that number is divisible by 9, division leaves a string of 71 ones. This "hard part" is known to be factorable, but no one has yet found its factors. Other groups are also attacking the problem of factoring large numbers. For instance, Samuel Wagstaff at Purdue University in Lafayette, Ind., and Jeffrey Smith and Carl Pomerance at the University of Georgia are building a computer specially designed just to factor numbers. When the machine is ready, they expect to be able to factor a 78-digit number in a day. The consensus at a recent meeting of mathematicians interested in factoring was that it may be possible to factor any 100-digit number by the 1990s. Simmons says, "Computational feasibility is something that changes all the time." Given Sandia's dependence on cryptographic systems, some of which apply the difficulty of factoring large numbers, for protecting information such as weapons systems data, Simmons says,"It's critically important for us to know just how difficult factoring is." -I. Peterson
chongo@nsc.UUCP (Landon Noll) (02/01/84)
Mr. Arnold claims to be able to factor or prove the primality of any number regardless of the size of the number.... if Mr. Arnold can do such a thing, why not have him select a Mersenne prime on the order of 2^400000-1. such a number could be verified in a few days with the help of a Cyber 205 and FFT's. put his money on the number i say... chongo <Mr. Arnold the bogus?> /\../\