## Re: Largest Ordinary Prime?

Expand Messages
• ... PFGW was exploited for the inital search for a PRP because of it s gain in speed in this respect -- for 2^n+-k (k
Message 1 of 22 , Oct 1, 2002
--- Carl Devore wrote:
> On Mon, 30 Sep 2002, David Broadhurst wrote:
> > Ordinary it ain't, since it was possible, with a huge
> > effort by Paul Underwood, Bouk de Water, Paul Leyland
> > and myself, to factorize 30.08% of N+1=2^15*(2^64680-1)
> > and hence to prove N prime using Konyagin-Pomerance.
>
> Also, major efficiency gains can be realized for simple arithmetic
> with a
> number with such a sparse binary representation. Whether the code
> actually exploited those efficiencies I don't know.

PFGW was exploited for the inital search for a PRP because of it's
gain in speed in this respect -- for 2^n+-k (k< about 43 bits.) I
used Prime95.exe to try and find factors of 2^32340-1 and 32340+1 and
this uses DFT I think. Paul Leyland also ran some ECM curves with
this program. I think David and Bouk used ECM.exe -- I don't know if
this uses the effiency. Does Pari-GP?

Paul
• ... Yes the signs are important for these trinomials. The most genral case I have is x^n+-x^k-1 (x,n,k all positive integers x 1,n 2,n k 0 and discounting
Message 2 of 22 , Oct 1, 2002
--- Marcel Martin wrote:
>
> In a previous post, I wrote:
> >>2^64695-2^15-1 19476 x43 2002 Unmentionable!
>
> >It could be archived as "3-bit prime".
>
> That's anywhat. I didn't take in account the minus signs :-))
>

Yes the signs are important for these trinomials. The most genral
case I have is x^n+-x^k-1 (x,n,k all positive integers x>1,n>2,n>k>0
and discounting Mersenne and "Fermat-type" (2^n+1) numbers. Call the
this for f=x^3-x-1 passes 5 rounds of Miller Rabin at least for all
x<19700000001 (1007728207 PrPs).

I forgot to say in my previous post that Primo was used for proving
the primailty of some of the factors of N+1. I used bc for my
arithmetic ;)

Paul
• N=2^64695-2^15-1 is prime. Paul Underwood discovered that N is probably prime, as part of a large trawl of candidates of his favourite form f(a,b)=2^a-2^b-1
Message 3 of 22 , Oct 1, 2002
N=2^64695-2^15-1 is prime.

Paul Underwood discovered that N is
probably prime, as part of a large trawl
of candidates of his favourite form
f(a,b)=2^a-2^b-1
with large a and small b.

Bouk de Water observed that
N+1=2^15*(2^64680-1)
is highly composite, since
64680=2*2*2*3*5*7*7*11
has 96 divisors.

Moreover he found the 1012-digit prime
p1012=gcd(phi(4*8085,2),2^8085-2^4043+1)
which divides N+1.

all of 11 remaining composite cofactors of
{Phi(d,2);d|64680} (and their Aurifeuillian parts,
when d=4 mod 8) which had less than 600 digits,
making 1800 attempts on each of these 11 at B1=10^6,
i.e. p35 level. This took O(100) GHz-days of effort.

Working on largest cofactor,
Paul Leyland found that
p26=13304801278785221502712801
divides Phi(64680,2) with more than 4000 digits.

At this stage we lacked 221 digits of factorization,
and Paul Leyland contemplated using NFS on the
smallest composite, with 162 digits, if another
50 digits could be found with ECM.

In the event, NFS was not needed.
Paul Underwood used prime95 to find 2 large
factors of N+1=2^15*(2^64680-1), namely

p43=1974132723329736593062151838364049346634561
p41=37131299037462589694325096898604106162577

with the second leaving a 154-digit prime
in the now completed factorization of the
Aurifeuillian factor

gcd(phi(4*1617,2),2^1617+2^809+1)=
6469*1346555145625865869*p38*p41*p154

where

p38=10816328089875303012806778969765211273

We now had 30.08% factorization of the
digits of N+1, sufficient for a
Konyagin-Pomerance proof.

The actual primality proving was easy:
about a quarter of an hour of pfgw,
for the Lucas tests,

Primality testing 2^15*(2^64680-1)-1
[N+1, Brillhart-Lehmer-Selfridge]
Calling Brillhart-Lehmer-Selfridge
with factored part 30.08%
2^15*(2^64680-1)-1 is Lucas PRP!
(1060.780000 seconds)

and then a few minutes of Pari-GP to complete
the proof using the pair of Konyagin-Pomerance
cubics of Theorem 4.2.9 of the book by
Crandall and Pomerance. The code for this
checked by Andy Steward in the course of
proving primality of (3048^3121-1)/3047.

We also used 90 minutes of Primo to prove primality
of the prime factors of N+1, the largest known
being p1012, above.

By no stretch of the imagination is

N=2^64695-2^15-1

an "ordinary" prime. It is extraordinary
by the circumstance that it _just_ permitted
a Konyagin-Pomerance proof by factorization of N+1,
using cyclotomic and Aurifeuillian theory and
the best factoring engines available.

At 19476 decimal digits, it holds the record
for a very special type of proof:
"easy after much difficult factoring".

The previous record of this type was held
by Fibonacci(81839) with 17103 digits.

The record for proving a _truly_ ordinary prime
still stands at 5020 digits:

http://www.znz.freesurf.fr/pages/primotop20.html

• ... Err, it seems to me that it has all bits but one set to 1: ? b=binary(2^64695-2^15-1); ? print(sum(k=1,64695,b[k])) 64694 It is a base-2 near repunit ,
Message 4 of 22 , Oct 1, 2002
Marcel:

> What I meant is that we cannot call
> 2^64695-2^15-1 a "3-bit prime".
> Because of the minus signs, it
> has 63951 bits set to 1, not just 3.

Err, it seems to me that it has all bits but
one set to 1:

? b=binary(2^64695-2^15-1);
? print(sum(k=1,64695,b[k]))
64694

It is a "base-2 near repunit",
just one bit-change
away from being a Mersenne.

David
• ... Not really. Everyone knows that Hans is doing something huge, well above 6k digits. So why spend cycles to become a poor second in 2003 :-? David
Message 5 of 22 , Oct 1, 2002
Marcel:
> >The record for proving a _truly_ ordinary prime
> >still stands at 5020 digits
> And this is somewhat surprising.
Not really.
Everyone knows that Hans is doing something huge,
well above 6k digits.
So why spend cycles to become a poor second in 2003 :-?
David
• ... But it is: 2^15[2^64680-1]-1 and perhaps this may yield a name. Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths BrainBench
Message 6 of 22 , Oct 1, 2002
>What I meant is that we cannot call
>2^64695-2^15-1 a "3-bit prime". Because of the minus signs, it
>has 64694 bits set to 1, not just 3.

But it is:

2^15[2^64680-1]-1

and perhaps this may yield a name.

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com

T
• ... That was unfortunate. I had a registered Titanix (thanks!) which did all the batch except the p1012 and then used latest Primo 2.0.0 beta3 for this, the
Message 7 of 22 , Oct 1, 2002
Marcel:
> I didn't take in account that kind of Primo use
> when I set the limitations of the new version
> (to prevent the use of Primo by companies).
That was unfortunate.
I had a registered Titanix (thanks!)
which did all the batch except the p1012
and then used latest Primo 2.0.0 beta3
for this, the biggest.
David
• ... On July 2 he told that he had done 2173 bits of something big: http://groups.yahoo.com/group/primeform/message/2621 On Sept 21 he told that he had recently
Message 8 of 22 , Oct 1, 2002
Marcel:

> Maybe Hans told of it elsewhere,

On July 2 he told that he had done 2173 bits
of something big:

http://groups.yahoo.com/group/primeform/message/2621

On Sept 21 he told that he had recently gotten
below 20 kilobits:

http://groups.yahoo.com/group/primeform/message/2720

Putting these together, it is probable
that he started above 7k decimal digits.

But it seems that Marcel did not like
the idea of me cross-posting the inference?

> I wondered 'Why did he do that?'.

Because I like trying to solve
publicly posted puzzles.

David
• ... There is good reason to suppose from http://groups.yahoo.com/group/primeform/message/2719 that Hans s target was posted by him as a PrP at
Message 9 of 22 , Oct 1, 2002
> Because I like trying to solve
> publicly posted puzzles.

There is good reason to suppose from

http://groups.yahoo.com/group/primeform/message/2719

that Hans's target was posted by him as a PrP at

http://www.worldofnumbers.com/undulat.htm

So then one may take the hinted data:

1) processor about 1.5 GHz AMD
2) 2173 bits done before July 2
3) below 20 kilobits by Sept 21

Next one differentiates my notional

hours=(bits/3000)^4.5/(speed/GHz)

to guess a notional rate of

1000*(3000/22000)^3.5 ~ 1 bit/hour

at 1.5 GHz with around 22 kilobits left.

There were slightly more than
1800 hours between messages.

So notional starting number of bits is about

2173 + 1800 + 20000 ~ 24000

Then one asks which of the PrPs

(75*10^6249-57)/99
(14*10^6343-41)/99
(74*10^6815-47)/99
(32*10^6959-23)/99
(15*10^7233-51)/99
(72*10^7595-27)/99
(12*10^7809-21)/99
(18*10^8315-81)/99

is closest to 24 kilobits?

I bet on

(15*10^7233-51)/99

with 24025 bits,
which Hans discovered
to be PrP on 4 Jun 2001.

He will be ever so pleased if
I have failed to solve the puzzle:-)

At 1.5 GHz we might expect to know in

(20000/3000)^4.5/1.5/24/30 ~ 5 months time.

My best bet:
the 24 kilobit smoothly undulating prime
(15*10^7233-51)/99
by the end of February,
provided the gods of the

David (in puzzle solving mode)
• Firstly, congratulations to Paul, Paul, David and Bouk. Secondly, DAMN. I had this great idea while I was on holiday about ten days ago. It appears to be much
Message 10 of 22 , Oct 3, 2002
Firstly, congratulations to Paul, Paul, David and Bouk.

Secondly, DAMN. I had this great idea while I was on holiday
about ten days ago. It appears to be much the the same idea that
you guys had a long while earlier ;-)

I used my experience in trying to prove Gigantic GRUs to model
how many digits of prime factors I would expect to extract from
a cyclotomic factor of a given size given the amount of ECM work
I have done on such factors to date (about 7-10 GHz hours on each
composite on average, though some I've just started and a few have

I then generated a list of promising composite exponents c such that
2^c-1 gave a decent chance of being useful in proving 2^a - 2^b +/- 1
where c=a-b. 64680 came out at 19.85%, so your 30% indicates how much
more work you did on it (and a bit of luck). I reckon the best few
exponents of around the same size are: 65520, 75600, 69300, 83160,
73920, 70560 then 64680.

Another thought I had was to use 2^c-1 where it's a Mersenne prime
... or c=2p, 3p etc where 2^p-1 is a Mersenne prime: diminishing
returns but worth a try for small multiples.

Ah well, I'll stick to the GRUs.

Good luck,
Andy
• ... Then recall that Paul U restricted his search of 2^a-2^b-1 to b
Message 11 of 22 , Oct 4, 2002
Andy:

> I reckon the best few exponents of around
> the same size are: 65520, 75600, 69300,
> 83160, 73920, 70560 then 64680.

Then recall that Paul U restricted his
search of 2^a-2^b-1 to b<=40.

So that gives 280 chances for those 7
values of c=a-b, whereas
ln(N) ~ ln(2^70000) = 50,000,
giving you odds of order 100:1 against.

It's neat that one of your 280 showed up,
with b=15, and even neater that Bouk's eagle
eyes spotted it in Henri's pages.

PS: How's the latest GRU cooking?

Remember that Phil has just offered
double the usual extra bits,
if/when you need them :-)

Also Paul L was holding NFS cycles
in reserve for 2^15*(2^64680-1)-1
which we didn't need. So maybe
you could do something really
impressive with another 150 digits
from him, in some strategic place :-?

Best wishes

David
• ... b
Message 12 of 22 , Oct 4, 2002
> > I reckon the best few exponents of around
> > the same size are: 65520, 75600, 69300,
> > 83160, 73920, 70560 then 64680.
>
> Then recall that Paul U restricted his
> search of 2^a-2^b-1 to b<=40.
>

b<44 actually. Also a<100000.

Bouk suggests having a look at 118080.

I will find minimal PrPs for all the suggestions at the end of the
month; also for 2^a-2^b+1. ;-)

Paul
• ... Did you mean 110880? I get an expected factorisation of 18.4% for that one, but only 9.7% for 118080. By my model, 110880 is the most promising exponent in
Message 13 of 22 , Oct 5, 2002
Paul Underwood wrote:

> Bouk suggests having a look at 118080.

Did you mean 110880? I get an expected factorisation of
18.4% for that one, but only 9.7% for 118080. By my model,
110880 is the most promising exponent in (85680,750000]

Here's a list of exponents where each entry has a higher
expected factorisation yield than any larger:

Exponent, factors, expectation
1680,40,100.00%
1740,24,96.33%
1890,32,95.48%
2100,36,94.98%
2520,48,91.05%
2640,40,88.53%
2940,36,88.41%
3360,48,86.53%
3780,48,82.88%
3960,48,80.44%
4200,48,79.05%
4620,48,78.67%
5040,60,78.06%
5460,48,71.49%
5880,48,69.92%
6120,48,69.12%
7560,64,68.14%
7920,60,63.67%
9240,64,62.61%
10080,72,61.54%
10920,64,56.45%
12600,72,53.33%
13860,72,52.73%
15120,80,51.39%
16380,72,46.94%
18480,80,46.48%
20160,84,43.47%
21840,80,41.16%
27720,96,39.70%
30240,96,36.29%
32760,96,35.11%
36960,96,31.72%
37800,96,30.69%
40320,96,28.96%
41580,96,28.95%
42840,96,28.73%
55440,120,28.00%
65520,120,24.39%
75600,120,21.10%
83160,128,21.05%
85680,120,19.43%
110880,144,18.40%
131040,144,15.89%
138600,144,15.06%
166320,160,14.15%
171360,144,12.41%
196560,160,12.14%
221760,168,11.37%
240240,160,10.17%
277200,180,9.96%
332640,192,8.95%
360360,192,8.35%
393120,192,7.64%
415800,192,7.26%
443520,192,6.75%
471240,192,6.43%
480480,192,6.31%
498960,200,6.29%
554400,216,6.21%
556920,192,5.47%
720720,240,5.39%
739200,192,4.09%
742560,192,4.08%
748440,192,3.93%
749700,162,3.33%

HTH,
Andy
• ... 110880 it should be indeed. Moreover because phi(36960,2) is a prp. 36960 * 2 = 73920 2^73920-1 is already BLS 36960 * 3 = 110880 2^110880-1 is about 1300
Message 14 of 22 , Oct 5, 2002
> Paul Underwood wrote:
>
> > Bouk suggests having a look at 118080.
>
> Did you mean 110880? I get an expected factorisation of
> 18.4% for that one, but only 9.7% for 118080. By my model,
> 110880 is the most promising exponent in (85680,750000]

110880 it should be indeed. Moreover because phi(36960,2) is a prp.

36960 * 2 = 73920

36960 * 3 = 110880

2^110880-1 is about 1300 digits short for Konyagin-Pomarance.

Bouk.

__________________________________________________
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com
• ... Not yet... ;-) Phil ===== First rule of Factor Club - you do not talk about Factor Club. Second rule of Factor Club - you DO NOT talk about Factor Club.
Message 15 of 22 , Oct 5, 2002
--- Bouk de Water <bdewater@...> wrote:
> Moreover because phi(36960,2) is a prp.
^^^
> 36960 * 2 = 73920
>

Not yet... ;-)

Phil

=====
First rule of Factor Club - you do not talk about Factor Club.
Second rule of Factor Club - you DO NOT talk about Factor Club.
Third rule of Factor Club - when the cofactor is prime, or you've trial-
divided up to the square root of the number, the factoring is over.

__________________________________________________
Do you Yahoo!?
Faith Hill - Exclusive Performances, Videos & More
http://faith.yahoo.com
• ... True, oh sage. But 2312 digits would be a mere bagatelle for primo. More significantly what a would make 2^a*(2^73920-1)-1 PrP? On average you have to
Message 16 of 22 , Oct 5, 2002
Phil:

> Not yet... ;-)

True, oh sage.

But 2312 digits would be
a mere bagatelle for primo.

More significantly what "a" would make
2^a*(2^73920-1)-1
PrP?

On average you have to wait a long time
and by then 2^a gives you most of BLS anyway,
thus eroding you factorization work.

It was Paul U's a=15 that was really notable in

2^15*(2^64680-1)-1

David
• ... [snip] ... To be precise, 239 phi-factors and 5.895144%: http://groups.yahoo.com/group/primenumbers/files/Factors/m720720.zip Best, Andrey [Non-text
Message 17 of 22 , Oct 13, 2002
Andy Steward wrote:

> Here's a list of exponents where each entry has a higher
> expected factorisation yield than any larger:
>
> Exponent, factors, expectation
[snip]
> 720720,240,5.39%

To be precise, 239 phi-factors and 5.895144%: