## Primes of the form 4^n-3

Expand Messages
• Hi Paul Leyland askedme the other day about 4^n-3. As far as I know the biggest ordinary prime (whatever that is) is 4^7057-3 proven by Preda Milhailescu. I
Message 1 of 3 , May 3, 2001
Hi

Paul Leyland askedme the other day about 4^n-3. As far as I know the
biggest "ordinary prime" (whatever that is) is 4^7057-3 proven by
Preda Milhailescu.

I am intersted in these because I have never found a composite of
the form F:2^N-2^k-1 for which F|2^F-2. In the above case k=1 and
n=2N.

Modular reducton of a 2N bit number is particularly easy since
2^N=2+1 and hence requires just two shifts and additions. Moreover to
test F we could check 2^(2^N)=8 modulo F i.e take N (FFT) squarings
of 2, use the simple modular reduction, and finally check to see if
this equals 8.

I checked an old email file to the old utm list server for back on
the 3rd May 1999.I wrote:

>4^n-3 is proven prime. n:
2
3
5
7
10
11
12
47
58
61
75
87
133
168
226
347
425
868
1977
2815
3378
4385
5286
7057

4^n-3 not proven prime. n:
720
8230
8340
13175
17226

I also tested 4^n+3:
1
2
3
6
8
9
14
15
42
114
195
392
555
852
1004
1185
2001
2030
2031
2276
8610
8967
10362
11366
15927
16514

In both case I tested to n=17400. You might want to check these are
PRP. Do I qualify for Henri's PRP list with any of these?

Tony Forbes concurred with me that these were the only such numbers
upto some maximum I forget.

Chris Nash attemted factorisation of some of these numbers for BHS
test. I guese he got lucky with 7057 and Preda was able to finish the
job with his "cycloprove" program.

I hope this helps. Don't forget to check the PRPs.

Paul
• ... Especially the 4^720-3 number ;) Might you mean 4^7200-3 instead? Jim.
Message 2 of 3 , May 3, 2001
> Hi
>
>Paul Leyland askedme the other day about 4^n-3. As far as I know the
> ...
>4^n-3 not proven prime. n:
>720
> ...
>In both case I tested to n=17400. You might want to check these are
>PRP.

Especially the 4^720-3 number ;) Might you mean 4^7200-3 instead?

Jim.
• ... Indeed, as I am toying with the idea of searching for further examples and putting up a web page to coordinate the search, should anyone else be interested
Message 3 of 3 , May 4, 2001
> Paul Leyland askedme the other day about 4^n-3. As far as I know the
> biggest "ordinary prime" (whatever that is) is 4^7057-3 proven by
> Preda Milhailescu.

Indeed, as I am toying with the idea of searching for further examples
and putting up a web page to coordinate the search, should anyone else
it won't happen in the immediate future 8-(

> I am intersted in these because I have never found a composite of
> the form F:2^N-2^k-1 for which F|2^F-2. In the above case k=1 and
> n=2N.
>
> Modular reducton of a 2N bit number is particularly easy since
> 2^N=2+1 and hence requires just two shifts and additions. Moreover to
> test F we could check 2^(2^N)=8 modulo F i.e take N (FFT) squarings
> of 2, use the simple modular reduction, and finally check to see if
> this equals 8.
>
> I checked an old email file to the old utm list server for back on
> the 3rd May 1999.I wrote:
>
> >4^n-3 is proven prime. n:

[Lists deleted.]

Thanks Paul! This will help populate the web page, and also gives a few
nice test cases to pick up really stupid bugs.

Paul
Your message has been successfully submitted and would be delivered to recipients shortly.