- While programing a comment lint for the new database system

an old question has come up. In the past we have let

"ECPP" be an archivable class. With some trepidation I

marked several "Cyclotomy". David often uses

"Konyagin/Pomerance". I strongly feel the first

desrves to remain an archivable class; but I am not sure

what to do with the other two.

But here is the big problem: definition.

What makes a prime N an "ECPP" (or "Cyclotomy" or

"Konyagin/Pomerance") prime? What if enough prime

factors of N+/-1 are discovered later for more

classical methods--does it lose the "ECPP"...?

What if it is possible, but not obvious how, to use a

simpler method and the prime is submitted as ECPP

soon after to be done another way?

The answer to this question is very important to

those that spend months on one type of proof and

a simpler one is found.

It is also important to me, because if we remove

the ECPP once an easier method is found then

eventually all primes marked ECPP will lose that

status (maybe 30 years later...), so it makes my

task harder--somehow periodically all such primes

would need to be rechecked.

So I am leaning towards leaving the method first

used marked, even if there is a better way. But

doesn't the clever Primo have some classical methods

built in? This means using Primo would not be

enough to make it ECPP, there would be some type

of certificate check.

Now I am leaning towards just making the comments

not archivable--this would solve the problem that

each record Primo number has a certificate full of other

ECPP primes... and would encourage folks to focus on

interesting numbers, not proof methods...

Where should I lean next?

Chris - --- "Good Question <caldwell@...>" <caldwell@...> wrote:
> While programing a comment lint for the new database system

As we recently witnessed.

> an old question has come up. In the past we have let

> "ECPP" be an archivable class. With some trepidation I

> marked several "Cyclotomy". David often uses

> "Konyagin/Pomerance". I strongly feel the first

> desrves to remain an archivable class; but I am not sure

> what to do with the other two.

>

> But here is the big problem: definition.

>

> What makes a prime N an "ECPP" (or "Cyclotomy" or

> "Konyagin/Pomerance") prime? What if enough prime

> factors of N+/-1 are discovered later for more

> classical methods--does it lose the "ECPP"...?

> What if it is possible, but not obvious how, to use a

> simpler method and the prime is submitted as ECPP

> soon after to be done another way?

> The answer to this question is very important to

Is it a property of the number or the proof?

> those that spend months on one type of proof and

> a simpler one is found.

If a property of the number, then ECPP and APRCL classes contain the same

numbers.

If a property of the proof, then you invoke your elliptical comment below

and your comment above.

Therefore either view leads to problems. I think the latter ones (it is a

property of the proof that took place) leads to less of an issue.

> It is also important to me, because if we remove

If it's a property of the proof, then then it's immutable.

> the ECPP once an easier method is found then

> eventually all primes marked ECPP will lose that

> status (maybe 30 years later...), so it makes my

> task harder--somehow periodically all such primes

> would need to be rechecked.

> So I am leaning towards leaving the method first

Leaning there too.

> used marked, even if there is a better way. But

> doesn't the clever Primo have some classical methods

> built in? This means using Primo would not be

> enough to make it ECPP, there would be some type

> of certificate check.

> Now I am leaning towards just making the comments

Before I express my leanage, let's argue by analogies, and see where it leads.

> not archivable--this would solve the problem that

> each record Primo number has a certificate full of other

> ECPP primes... and would encourage folks to focus on

> interesting numbers, not proof methods...

If we agree (which we don't all necessarily by any means) that the tag is a

property of the proof not the number, then is there a difference between the

relevance of the "software used" and the "algorithm used" fields?

I'm finding it hard to separate the two, which implies to me that having

top-20 tables for the largest ECPP primes would imply that there ought to

be analogous top-20 primes proved by OpenPFGW tables, for example.

Which implies that I too have obliged myself to lean in the same direction

as you again.

> Where should I lean next?

Remaining flexible is probably the key!

Phil

=====

The answer to life's mystery is simple and direct:

Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________

Do you Yahoo!?

Yahoo! Mail Plus - Powerful. Affordable. Sign up now.

http://mailplus.yahoo.com > But here is the big problem: definition.

You may wish to consider what the factoring community does in analgous cases.

>

> What makes a prime N an "ECPP" (or "Cyclotomy" or

> "Konyagin/Pomerance") prime? What if enough prime

> factors of N+/-1 are discovered later for more

> classical methods--does it lose the "ECPP"...?

> What if it is possible, but not obvious how, to use a

> simpler method and the prime is submitted as ECPP

> soon after to be done another way?

It's occasionally the case that a factorization is found by two methods essentially simultaneously. Most commonly, an ECM run spits out a small factor when a NFS or QS computation is still sieving, though other circumstances are occasionally found. For instance, Paul Zimmermann found a factor by P+1 of 118*^10^118+1 just after I'd started a SNFS run.

A similar circumstance occurs when a factor which is found by one method is found to be discoverable by another. I don't mean trivial cases such as using Pollard rho rather than trial division to find 8-digit factors but, rather, ECM discovering a factor which could have been found more quickly by P-1 or P+1. An extreme case and, admittedly, a contrived case was found in Simon Singh's Cipher challenge where a factorization of a 512-bit integer actually performed by GNFS could have been done in about 1% of the computation by P-1.

The factoring community invariably records the first reported method in these cases.

Paul> ECPP, Cyclotomy, Konyagin/Pomerance

1) ECPP is at present an archivable class, with a top-20.

I believe that it should stay like this, with Chris trying to

chase up the folk in Marcel's top-20 who are not yet in his.

Once proven by ECPP, no subsequent easier validation can demote

such a prime, since the top-20 is for primes first proven by ECPP.

2) Cyclotomy is at present an archivable class, with a top-20.

I believe that should be relegated to a mere comment.

No-one will be affected since all of the present top-20 are archivable

according to their mathematical definitions, irrespective of their

proof method.

3) Konyagin/Pomerance is at present neither an archivable class

nor an accepted comment.

I believe it should stay like this.

If folk want to indicate that KP was the proof method they can do

so as I do, using the <url,...,notes> addendum.

David Broadhurst> 1) ECPP is at present an archivable class, with a top-20.

Maybe Marcel could try to encourage his top-20 to contact Chris?

> I believe that it should stay like this, with Chris trying to

> chase up the folk in Marcel's top-20 who are not yet in his.

Congrats to Jeff Heleen:

http://www.ellipsa.net/pages/primotop20.html

(10^4769 - 1) / 3 - 2*10^2384

4769 decimal digits

Certified by Jeff Heleen (2002)

* Running time: 1464h

* Processor: AMD Athlon 1.3 GHz

David