Side note: As my girlfriend says, my wording might be quite good, but my spelling is attrocious. You've been warned - and note that my typing is inaccurate too! So far I've been approached from about 10 different directions for more information, and it only makes sense to try to get some sort of "press release" together. This is it, I'm afraid.

There is nothing particularly innovative about the principles behind what I've done, and to claim otherwise would be wrong. I simply tied known things together. Pretty much anyone could have done it; I just happened to try it first.

As far as I'm concerned, the history lies with the 2600 case and the Jon Johanson case, information on which can be found on the The Electronic Frontier Foundation's page on DeCSS cases. All roads lead to Rome, and all HREFs lead to Dave Touretzky's DeCSS web page for far more background information.

My original plan was to make sure that the "bits", the raw data, of the
DeCSS code was archived somewhere where it should be beyond the reach of
the law. Somewhere where the number would be allowed to be printed because
it had some property that made it publishable, independent of whether it
was "illegal" or not. I needed to find a presentation of the data such
that it had an *intrinsicly archivable* quality.

I have been a large prime prover (parse that either way!) for quite a while now (I refer you to, for example, the "Near Repdigit" record on Professor Caldwell's Prime Pages), and I tried to think how I could come up with a number archivable on those pages. The Prime Pages is the world's definitive resource for large prime number archiving and information; Professor Caldwell, who manages it, has put an awfully large amount of effort into deveoloping those pages, and into administering the archival of large primes, and has put a lot of thought into the criteria for their archivability.

The only thing I could think of was to try to find one of the
*largest* ever numbers tested with an algorithm called ECPP.
It's an algorithm usable on numbers with no particular form (N±1
is not easily factorable to any great extent), and is based on Elliptic
Curves (which is quite a nice link to cryptography, and the fact the CSS
was supposed to be a "cryptographic" algorithm).

It is important to note that the 1401-digit prime as listed on Dave
Touretzky's page *isn't* large enough to be archivable. In fact
*mathematically* there's little particularly interesting about the
prime. However it has become "interesting" enough to be one of the curios
on the Prime Curios site,
which is part of the Prime Pages site, and is for the more "fun" aspects
of prime numbers.

So my real *archivable* discovery is that of a 1905-digit prime,
which shares the same initial bytes as the gzip file which forms the
start of the 1401-digit prime) but has lots more 0s appended to it,
and then an extra byte (99, I seem to remember) to make it prime.
This is the *10th largest number ever proven using ECPP*. It will
therefore remain archived purely because it is the top 20. The reason it
is archived is *not* that it is supposedly illegal, but its size,
nothing more. This can be verified by doing a search of the whole database
of large primes with the text search key "ECPP". (The server seems to be
down at the the time of writing (the
slashdot effect?), but if you
follow the "Prime Lists" and the "Search whole database" links
you'll get there in the end!). The above search will show you the value
and sizes of all the ECPP-proven primes.

I had some trouble with the proving software - it's a hard job proving
these things sometimes - and so "hedged my bets" and actually have
*2* huge primes (the other is 1920 digits or more, and isn't yet
submitted to the above database).

OK, with that out of the way, the questions that still remain are "how did I find it?" and "why did I bother doing this at all?".

The first question above is an easy one. I used a couple of wonderful pieces of software written by other people!

Firstly, I thought of the expression that I wished the prime to satisfy.

For the 1401-digit prime this was

~~bignum representing the .gz file~~ * 256 + Xwhere X is an odd number between 1 and 255. i.e I wanted to append just one byte to the .gz file. However, this search failed, so I changed the target to be 2 extra bytes:

~~bignum representing the .gz file~~ * 65536 + X, for X in 1 to 65535

For the

~~bignum representing the .gz file~~ *256^(156+Y) + Xfor Y in 0 to 300, and from X in 1 to 255

OK, with those in mind I created a configuration file for an
*excellent* program called OpenPFGW (or just PFGW) which permits
one to search for *Probable Primes*, or PrPs of any form. (It
also lets you *prove* primes which have special properties, but my
primes didn't have these properties). Information about OpenPFGW can be
got from (maybe via a redirect)
Chris Nash's Primeform Web page or
via the links on the Prime Pages. (The program used to be
called PrimeForm but changed its name when it went open source.)

What PFGW does is first trial factor the numbers (it tries up to a few million or maybe a billion, just to quickly reject obvious non-primes). After that it performs a Probable Primality test, which only takes a few seconds. As the search space I was using was much wider than it needed to be, I found many probable primes. My chances were roughly 1:1600 for finding a small one (1400/1401 digits) and 1:2100 for the larger prime. (It is proportional to ln(x) where x is the number in question, i.e. it is proportional to the number of digits/bits in the number.)

Now to a mathematician *probable* primes just aren't good
enough. They are certainly not archivable on the Prime Pages until a
deterministic proof is obtained. So the third part was a deterministic
proof, using ECPP. The running time of ECPP deterministic proofs is
O(N^6), where N is the number of bits in the probable prime, and so
the proofs for very large primes (over 2000 digits) are very long.
Remember that the probabilistic test took only 1 second, well the
ECPP test would take *many days*! The software I used was
Titanix, written by Marcel Martin, which is about as fast as you
can get for ECPP proving. More information is available at
Marcel Martin's web site.

If you have any further questions about the mathematics, please get back to me. The username "fatphil" and the domain name "yahoo.co.uk" normally work to this end.

In simple terms I believe that source code, which is pure information
to my way of thinking, *cannot intrinsically* be illegal. So the
banning of the
Copyleft T-shirts, for example, I
find to be *absolutely bizarre*. I therefore just wanted to have
the data replicated in another form, but specifically a form which
*could not sensibly be considered illegal*. The larger number(s)
is/are record (top20) ECPP primes. You can't sensibly remove them from the
archive, because the numbers are *still prime* and *still proved
using ECPP* whether the MPAA likes what they stand for or not.

I am *very* grateful to Professor Caldwell for permitting me to put
his site at risk by my action. If things do turn sour then of course my
stubborn attitude must be ignored, and the numbers should be replaced with
some place-holder indicating there used to be a prime number there. There
is enough publicity surrounding these numbers for it to be impossible to
remove every trace of them from the world. Even if they do, they'll still
be primes; that's an intrinsic property of the numbers which cannot be
removed.

Phil Carmody,

Kivenlahti, nr. Helsinki 2001/03/19

- Sites Bearing the Original Information
- Sites Bearing the Story
- Greets
- The
*utmost*respect to Dave Touretzky for his no-nonsense stance on many important freedom-related issues - Chris Caldwell
- Jon Johanson - who was the innocent victim of some
*serious*brokenness in the world - Chris Nash (primeform/openpfgw) and Marcel Martin (Titanix) (and the other pfgw contributers of course)
- The Primenumbers and primeform mailing lists
- Those who noticed this without my prompting - Tim, James, Fabio, Champie, Leonid and the others
- Anna, my girlfriend who puts up with loads of rubbish and my stupid prime number obsession (my proofreader has just turned pink!)

- The
- Gibber

This page © 2001 Phil Carmody