Prime numbers and primality testing is a Restricted Group with 1117 members.
 Prime numbers and primality testing

 Restricted Group,
 1117 members
Re: [PrimeNumbers] RE: Largest Ordinary Prime?
Expand Messages
 On Mon, 30 Sep 2002, David Broadhurst wrote:
> Ordinary it ain't, since it was possible, with a huge
Also, major efficiency gains can be realized for simple arithmetic with a
> effort by Paul Underwood, Bouk de Water, Paul Leyland
> and myself, to factorize 30.08% of N+1=2^15*(2^646801)
> and hence to prove N prime using KonyaginPomerance.
number with such a sparse binary representation. Whether the code
actually exploited those efficiencies I don't know.   Carl Devore wrote:
> On Mon, 30 Sep 2002, David Broadhurst wrote:
PFGW was exploited for the inital search for a PRP because of it's
> > 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^646801)
> > and hence to prove N prime using KonyaginPomerance.
>
> 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.
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^323401 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 PariGP?
Paul   Marcel Martin wrote:
>
Yes the signs are important for these trinomials. The most genral
> In a previous post, I wrote:
> >>2^646952^151 19476 x43 2002 Unmentionable!
>
> >It could be archived as "3bit prime".
>
> That's anywhat. I didn't take in account the minus signs :))
>
case I have is x^n+x^k1 (x,n,k all positive integers x>1,n>2,n>k>0
and discounting Mersenne and "Fermattype" (2^n+1) numbers. Call the
trinomial f. I have not found a composite f:fx^fx. For instance
this for f=x^3x1 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^646952^151 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^a2^b1
with large a and small b.
Bouk de Water observed that
N+1=2^15*(2^646801)
is highly composite, since
64680=2*2*2*3*5*7*7*11
has 96 divisors.
Moreover he found the 1012digit prime
p1012=gcd(phi(4*8085,2),2^80852^4043+1)
which divides N+1.
By late July, David Broadhurst had used ecmgmp on
all of 11 remaining composite cofactors of
{Phi(d,2);d64680} (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) GHzdays 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^646801), namely
p43=1974132723329736593062151838364049346634561
p41=37131299037462589694325096898604106162577
with the second leaving a 154digit 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
had already been found by ecmgmp.
We now had 30.08% factorization of the
digits of N+1, sufficient for a
KonyaginPomerance proof.
The actual primality proving was easy:
about a quarter of an hour of pfgw,
for the Lucas tests,
Primality testing 2^15*(2^646801)1
[N+1, BrillhartLehmerSelfridge]
Calling BrillhartLehmerSelfridge
with factored part 30.08%
2^15*(2^646801)1 is Lucas PRP!
(1060.780000 seconds)
and then a few minutes of PariGP to complete
the proof using the pair of KonyaginPomerance
cubics of Theorem 4.2.9 of the book by
Crandall and Pomerance. The code for this
was written by David Broadhurst and had been
checked by Andy Steward in the course of
proving primality of (3048^31211)/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^646952^151
an "ordinary" prime. It is extraordinary
by the circumstance that it _just_ permitted
a KonyaginPomerance 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
David Broadhurst  Marcel:
> What I meant is that we cannot call
Err, it seems to me that it has all bits but
> 2^646952^151 a "3bit prime".
> Because of the minus signs, it
> has 63951 bits set to 1, not just 3.
one set to 1:
? b=binary(2^646952^151);
? print(sum(k=1,64695,b[k]))
64694
It is a "base2 near repunit",
just one bitchange
away from being a Mersenne.
David  Marcel:
> >The record for proving a _truly_ ordinary prime
Not really.
> >still stands at 5020 digits
> And this is somewhat surprising.
Everyone knows that Hans is doing something huge,
well above 6k digits.
So why spend cycles to become a poor second in 2003 :?
David >What I meant is that we cannot call
But it is:
>2^646952^151 a "3bit prime". Because of the minus signs, it
>has 64694 bits set to 1, not just 3.
2^15[2^646801]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 Marcel:
> I didn't take in account that kind of Primo use
That was unfortunate.
> when I set the limitations of the new version
> (to prevent the use of Primo by companies).
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  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 crossposting the inference?
> I wondered 'Why did he do that?'.
Because I like trying to solve
publicly posted puzzles.
David > Because I like trying to solve
There is good reason to suppose from
> publicly posted puzzles.
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^624957)/99
(14*10^634341)/99
(74*10^681547)/99
(32*10^695923)/99
(15*10^723351)/99
(72*10^759527)/99
(12*10^780921)/99
(18*10^831581)/99
is closest to 24 kilobits?
I bet on
(15*10^723351)/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^723351)/99
by the end of February,
provided the gods of the
dreaded backtracks don't intervene.
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 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 710 GHz hours on each
composite on average, though some I've just started and a few have
had thousands of hours).
I then generated a list of promising composite exponents c such that
2^c1 gave a decent chance of being useful in proving 2^a  2^b +/ 1
where c=ab. 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^c1 where it's a Mersenne prime
... or c=2p, 3p etc where 2^p1 is a Mersenne prime: diminishing
returns but worth a try for small multiples.
Ah well, I'll stick to the GRUs.
Good luck,
Andy  Andy:
> I reckon the best few exponents of around
Then recall that Paul U restricted his
> the same size are: 65520, 75600, 69300,
> 83160, 73920, 70560 then 64680.
search of 2^a2^b1 to b<=40.
So that gives 280 chances for those 7
values of c=ab, 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^646801)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 > > I reckon the best few exponents of around
b<44 actually. Also a<100000.
> > the same size are: 65520, 75600, 69300,
> > 83160, 73920, 70560 then 64680.
>
> Then recall that Paul U restricted his
> search of 2^a2^b1 to b<=40.
>
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^a2^b+1. ;)
Paul 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   Andy Steward <aads@...> wrote:
> Paul Underwood wrote:
110880 it should be indeed. Moreover because phi(36960,2) is a prp.
>
> > 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]
36960 * 2 = 73920
2^739201 is already BLS
36960 * 3 = 110880
2^1108801 is about 1300 digits short for KonyaginPomarance.
Bouk.
__________________________________________________
Do you Yahoo!?
Faith Hill  Exclusive Performances, Videos & More
http://faith.yahoo.com   Bouk de Water <bdewater@...> wrote:
> Moreover because phi(36960,2) is a prp.
^^^
> 36960 * 2 = 73920
Not yet... ;)
>
> 2^739201 is already BLS
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  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^739201)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^646801)1
David  Andy Steward wrote:
> Here's a list of exponents where each entry has a higher
[snip]
> expected factorisation yield than any larger:
>
> Exponent, factors, expectation
> 720720,240,5.39%
To be precise, 239 phifactors and 5.895144%:
http://groups.yahoo.com/group/primenumbers/files/Factors/m720720.zip
Best,
Andrey
[Nontext portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.