Fun_People Archive
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

© 1995 Peter Langston