Loading ...
Sorry, an error occurred while loading the content.

Primes of the form 4^n-3

Expand Messages
  • paulunderwood@mindless.com
    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
    • 0 Attachment
      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
    • jfoug@kdsi.net
      ... Especially the 4^720-3 number ;) Might you mean 4^7200-3 instead? Jim.
      Message 2 of 3 , May 3, 2001
      • 0 Attachment
        --- In primenumbers@y..., paulunderwood@m... wrote:
        > 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.
      • Paul Leyland
        ... 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
        • 0 Attachment
          > 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
          be interested in joining in. However, pressure of other work means that
          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.