26 Jun

A Prime Patent (or two)

Date: Mon, 26 Jun 95 17:43:21 PDT From: Peter Langston <psl> To: Fun_People Subject: A Prime Patent (or two) Forwarded-by: bostic@CS.Berkeley.EDU (Keith Bostic) Forwarded-by: "Josh M. Osborne" <stripes@va.pubnix.com> Forwarded-by: sdw@lig.net (Stephen D. Williams) A Prime Patent Legal rights to a number upset programmers and lawyers Roger Schlafly has just succeeded in doing something no other mathematician has ever done: he has patented a number. The seemingly bizarre event is the latest twist in the saga of assigning software patents that has vexed the U.S. Patent and Trademark Office for more than 20 years. "I'm sure if you just went to someone and said, 'Can you patent a prime number?' they would say, 'No, that's ridiculous,'" says Schlafly, a computer consultant who lives in northern California. Schlafly, of course, hasn't patented just any number. His figure--which is nearly 150 digits long--has a property that makes it possible to take a certain shortcut when performing modular division. A little improvement in division is big news for people using the Diffie-Hellman public-key cryptography system, which uses repeated modular divisions as a tool for encrypting and decrypting secret codes. Cryptographic keys are typically numbers hundreds of digits long, so a small improvement can mean a big savings in time. But even as this patent is helping speed up a few mathematical calculations, patents in general are slowing down the progress of developing software. Such patents are on the rise: 4,500 were granted in 1994, and nearly 5,400 are projected to be granted in 1995, says Gregory Aharonian, who publishes the Internet Patent News Service. "It is hard to believe that all these 9,000 patents reflect novel and unobvious ideas," Aharonian notes. In 1972 the U.S. Supreme Court ruled that computer algorithms could not be patented. But in 1978 that decision was reinterpreted by a lower court, which concluded that the higher court really meant only to prohibit patenting mathematical algorithms. Unfortunately, the ruling never defined what a mathematical algorithm actually was. Ever since, the number of software patents issued has been steadily rising--as have the number of lawsuits. Indeed, Schlafly's patent seems to fit right in with current Patent Office policy. The patent, entitled "Partial Modular Reduction Method," describes an algorithm for finding prime numbers that have this particular property. Most patent applications would stop there. But Schlafly's goes further, claiming two prime numbers that have the property. One is 512 digits long; the second is 1,024. Nevertheless, the figures satisfy the primary requirements of patentability. They are novel, because there is no record they have been used before, and they are useful, because they can be employed for cryptography. "I was kind of interested in pushing the system to see how far you could go with allowable claims," explains Schlafly, a member of the League for Programming Freedom, an organization that opposes software patents. Although Schlafly can now sue anybody for using his numbers, he is not worried about people infringing on his rights. "When you get to numbers that are so big that nobody has used them before, well, there are lots of them up there," he says. The same cannot be said of cryptography algorithms themselves. Schlafly is at present embroiled in a lawsuit with Public Key Partners (PKP), a California partnership that maintains the rights to the most important patents in the domain of public-key cryptography. The group claims that one of its patents covers the entire field. A second PKP patent, meanwhile, is at the heart of a program that Schlafly wrote, called Secret Agent, which is used to encrypt electronic mail. --Simson Garfinkel

Note that there is considerable controversy over the details of this use of patents. See http://groups.yahoo.com/group/mathforfun/message/10694. © 1995 Peter Langston