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

How to (trivially) tell what Mersenne a given number divides

Expand Messages
  • Kevin Acres
    Hi, I thought that I would pass this on, seeing as how it may be slightly different to the normal run of the mill algorithm. There is a trivial tranformation
    Message 1 of 5 , Jun 30, 2004
      Hi,

      I thought that I would pass this on, seeing as how it may be slightly
      different to the normal run of the mill algorithm.

      There is a trivial tranformation that can be applied to any odd number
      x to make it generate an number that is of the form 2^n - 1, of which
      Mersenne numbers are a subset. This new number can then be divided in
      to 2^x - 2 to give some idea of primality.

      If 2^x - 1 = 1 (mod (transform(x)) then x is either prime or base 2
      pseudoprime.

      How to tell the difference between the prime and pseudo prime is to
      look at how many times the transformed number divides 2^x - 2. The
      signature for pseudoprimes makes them almost instantly identifiable.

      Obviously the transformation can also be used for trial factoring.
      The advantage is that you don't have to complete any division, you
      just let the number find it's natural periodicity.

      Stepwise the alogorithm is shown below for an example using 23 (10111
      binary).

      candidate = 1 0111 (23)
      3 set bits in low order of 23
      Iteration 0:
      temp = 1 0111
      build = 0
      Add temp to build
      Shift left
      Shift left
      Iteration 3:
      temp = 1011 1000
      build = 1 0111
      Add temp to build
      Iteration 4:
      temp = 1 0111 0000
      build = 1100 1111
      Add temp to build
      Shift left
      Iteration 6:
      temp = 101 1100 0000
      build = 10 0011 1111
      Add temp to build
      Final build is 2047
      In Binary = 111 1111 1111

      Comments welcome as always.


      Kevin.
    • David Cleaver
      I have a couple of questions. (given below.) ... First, I hate to bring up semantics, but ALL numbers of the form 2^n - 1 are Mersenne numbers. The ones
      Message 2 of 5 , Jun 30, 2004
        I have a couple of questions. (given below.)

        Kevin Acres wrote:
        >
        > Hi,
        >
        > I thought that I would pass this on, seeing as how it may be slightly
        > different to the normal run of the mill algorithm.
        >
        > There is a trivial tranformation that can be applied to any odd number
        > x to make it generate an number that is of the form 2^n - 1, of which
        > Mersenne numbers are a subset. This new number can then be divided in
        > to 2^x - 2 to give some idea of primality.

        First, I hate to bring up semantics, but ALL numbers of the form 2^n - 1
        are Mersenne numbers. The ones where (2^n - 1) is prime is called a
        Mersenne Prime. I guess the others would be called Mersenne Composites.

        >
        > If 2^x - 1 = 1 (mod (transform(x)) then x is either prime or base 2
        > pseudoprime.
        >
        > How to tell the difference between the prime and pseudo prime is to
        > look at how many times the transformed number divides 2^x - 2. The
        > signature for pseudoprimes makes them almost instantly identifiable.
        >
        > Obviously the transformation can also be used for trial factoring.
        > The advantage is that you don't have to complete any division, you
        > just let the number find it's natural periodicity.
        >
        > Stepwise the alogorithm is shown below for an example using 23 (10111
        > binary).
        >
        > candidate = 1 0111 (23)
        > 3 set bits in low order of 23
        > Iteration 0:
        > temp = 1 0111
        > build = 0
        > Add temp to build
        > Shift left
        > Shift left
        > Iteration 3:
        > temp = 1011 1000
        > build = 1 0111
        > Add temp to build
        > Iteration 4:
        > temp = 1 0111 0000
        > build = 1100 1111
        > Add temp to build
        > Shift left
        > Iteration 6:
        > temp = 101 1100 0000
        > build = 10 0011 1111
        > Add temp to build
        > Final build is 2047
        > In Binary = 111 1111 1111
        >
        > Comments welcome as always.
        >
        > Kevin.

        I was wondering, why do your iteration numbers up above go 0, 3, 4, 6?
        Also, how do you know when to shift left once, or shift left twice, or not
        shift left at all? (Actually looking again, it just looks like you left out
        a shift left between iteration 3 and 4, is this the case? Also, should
        "iteration 6" be "iteration 5"?) Just curious about your algorithm. Looks
        very interesting if it indeed does work out.

        -David C.
      • Kevin Acres
        Hi David, First, in answer to your questions: I don t print the iteration number when I m not doing the addition, this is why the number jumps the way that it
        Message 3 of 5 , Jun 30, 2004
          Hi David,

          First, in answer to your questions:

          I don't print the iteration number when I'm not doing the addition,
          this is why the number jumps the way that it does.

          The shifting of a number continues until its LSB is over a zero in the
          current result. Once this occurs then the addition takes place again.

          The method is just a form of muliplication, you just don't know what
          you are multiplying by when you start the process. It's a process of
          finding the natural periodicity of the number concerned.

          It also proves, in a visual way, why any given prime divides at most
          one mersenne. And, by extension, why any given pseudo prime divides
          at most one mersenne.

          The interesting thing is that there is an implied rule as to which
          numbers divide which mersennes. This rule has to do with the
          distribution of 1's and 0's in the binary representation of the
          number.

          I noticed that in my earlier post I had something that wasn't clear.

          I actually count the bits in a generated number before the division.

          Taking the example of 23.

          23 generates a string of 11 binary 1's or 2^11 - 1.

          This means that 23 divides 2^11 - 1.

          Now the primality test (??) requires dividing the power-1 (22) by
          number of bits in the generated mersenne. So we have 22/11 which is a
          whole number. Now it is this division that instantly shows you the
          difference between primes and pseudoprimes. Try it on a range of
          numbers and you will see what I mean.


          Kevin.


          > I have a couple of questions. (given below.)
          >
          > Kevin Acres wrote:
          > >
          > > Hi,
          > >
          > > I thought that I would pass this on, seeing as how it may be
          slightly
          > > different to the normal run of the mill algorithm.
          > >
          > > There is a trivial tranformation that can be applied to any odd
          number
          > > x to make it generate an number that is of the form 2^n - 1, of
          which
          > > Mersenne numbers are a subset. This new number can then be
          divided in
          > > to 2^x - 2 to give some idea of primality.
          >
          > First, I hate to bring up semantics, but ALL numbers of the form
          2^n - 1
          > are Mersenne numbers. The ones where (2^n - 1) is prime is called a
          > Mersenne Prime. I guess the others would be called Mersenne
          Composites.
          >
          > >
          > > If 2^x - 1 = 1 (mod (transform(x)) then x is either prime or base 2
          > > pseudoprime.
          > >
          > > How to tell the difference between the prime and pseudo prime is to
          > > look at how many times the transformed number divides 2^x - 2. The
          > > signature for pseudoprimes makes them almost instantly
          identifiable.
          > >
          > > Obviously the transformation can also be used for trial factoring.
          > > The advantage is that you don't have to complete any division, you
          > > just let the number find it's natural periodicity.
          > >
          > > Stepwise the alogorithm is shown below for an example using 23
          (10111
          > > binary).
          > >
          > > candidate = 1 0111 (23)
          > > 3 set bits in low order of 23
          > > Iteration 0:
          > > temp = 1 0111
          > > build = 0
          > > Add temp to build
          > > Shift left
          > > Shift left
          > > Iteration 3:
          > > temp = 1011 1000
          > > build = 1 0111
          > > Add temp to build
          > > Iteration 4:
          > > temp = 1 0111 0000
          > > build = 1100 1111
          > > Add temp to build
          > > Shift left
          > > Iteration 6:
          > > temp = 101 1100 0000
          > > build = 10 0011 1111
          > > Add temp to build
          > > Final build is 2047
          > > In Binary = 111 1111 1111
          > >
          > > Comments welcome as always.
          > >
          > > Kevin.
          >
          > I was wondering, why do your iteration numbers up above go 0, 3, 4,
          6?
          > Also, how do you know when to shift left once, or shift left twice,
          or not
          > shift left at all? (Actually looking again, it just looks like you
          left out
          > a shift left between iteration 3 and 4, is this the case? Also,
          should
          > "iteration 6" be "iteration 5"?) Just curious about your
          algorithm. Looks
          > very interesting if it indeed does work out.
          >
          > -David C.
          >
          >
          > ------------------------ Yahoo! Groups Sponsor --------------------~-
          ->
          > Yahoo! Domains - Claim yours for only $14.70
          > http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/8HYolB/TM
          > --------------------------------------------------------------------
          ~->
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
          >
          >
        • sambit nayak
          Hi Kevin, I was testing your algorithm for the primality test. I have some doubts. The number I tested was N =
          Message 4 of 5 , Jul 1, 2004
            Hi Kevin,

            I was testing your algorithm for the primality test. I
            have some doubts.

            The number I tested was
            N =
            556158012756522140970101270050308458769458529626977.

            (Actually this is a composite number I was using so
            that I could factor it if possible.)

            This number generated (2^1332 - 1).
            So, by your primality test, if 1332 divides (N-1),
            then N is prime. In this case, 1332 actually divides
            (N-1), but the number N is not prime. (In fact,
            N = 449818591141 *
            1236405128000120870775846228354119184397.)

            Further, I could not factorise N using your method.
            Here, 1332 is even, so what to do now?

            I might have erred somewhere.. Kindly check this.

            Besides, do you have a proof of why all this is
            happening? I mean, why should any number lead to a
            Mersenne number, and how is the number of steps
            required to reach there related to the input number?
            Why should the input factor the Mersenne generated?
            Kindly bear with my curiosity (that might be
            irritating).

            Thanks,
            Sambit



            --- Kevin Acres <research@...> wrote:
            > Hi David,
            >
            > First, in answer to your questions:
            >
            > I don't print the iteration number when I'm not
            > doing the addition,
            > this is why the number jumps the way that it does.
            >
            > The shifting of a number continues until its LSB is
            > over a zero in the
            > current result. Once this occurs then the addition
            > takes place again.
            >
            > The method is just a form of muliplication, you just
            > don't know what
            > you are multiplying by when you start the process.
            > It's a process of
            > finding the natural periodicity of the number
            > concerned.
            >
            > It also proves, in a visual way, why any given prime
            > divides at most
            > one mersenne. And, by extension, why any given
            > pseudo prime divides
            > at most one mersenne.
            >
            > The interesting thing is that there is an implied
            > rule as to which
            > numbers divide which mersennes. This rule has to do
            > with the
            > distribution of 1's and 0's in the binary
            > representation of the
            > number.
            >
            > I noticed that in my earlier post I had something
            > that wasn't clear.
            >
            > I actually count the bits in a generated number
            > before the division.
            >
            > Taking the example of 23.
            >
            > 23 generates a string of 11 binary 1's or 2^11 - 1.
            >
            > This means that 23 divides 2^11 - 1.
            >
            > Now the primality test (??) requires dividing the
            > power-1 (22) by
            > number of bits in the generated mersenne. So we have
            > 22/11 which is a
            > whole number. Now it is this division that
            > instantly shows you the
            > difference between primes and pseudoprimes. Try it
            > on a range of
            > numbers and you will see what I mean.
            >
            >
            > Kevin.
            >
            >





            __________________________________
            Do you Yahoo!?
            New and Improved Yahoo! Mail - 100MB free storage!
            http://promotions.yahoo.com/new_mail
          • Kevin Acres
            Hi, Actually you need to study the numbers around that area so that you can see that the division is anomalous to what you would expect to find. It s visually
            Message 5 of 5 , Jul 1, 2004
              Hi,

              Actually you need to study the numbers around that area so that you can see
              that the division is anomalous to what you would expect to find. It's
              visually obvious but I don't think that I can derive a rule for it yet.

              Regards,

              Kevin.


              At 11:35 PM 1/07/2004, sambit nayak wrote:
              >Hi Kevin,
              >
              >I was testing your algorithm for the primality test. I
              >have some doubts.
              >
              >The number I tested was
              >N =
              >556158012756522140970101270050308458769458529626977.
              >
              >(Actually this is a composite number I was using so
              >that I could factor it if possible.)
              >
              >This number generated (2^1332 - 1).
              >So, by your primality test, if 1332 divides (N-1),
              >then N is prime. In this case, 1332 actually divides
              >(N-1), but the number N is not prime. (In fact,
              >N = 449818591141 *
              >1236405128000120870775846228354119184397.)
              >
              >Further, I could not factorise N using your method.
              >Here, 1332 is even, so what to do now?
              >
              >I might have erred somewhere.. Kindly check this.
              >
              >Besides, do you have a proof of why all this is
              >happening? I mean, why should any number lead to a
              >Mersenne number, and how is the number of steps
              >required to reach there related to the input number?
              >Why should the input factor the Mersenne generated?
              >Kindly bear with my curiosity (that might be
              >irritating).
              >
              >Thanks,
              >Sambit
              >
              >
              >
              >--- Kevin Acres <research@...> wrote:
              > > Hi David,
              > >
              > > First, in answer to your questions:
              > >
              > > I don't print the iteration number when I'm not
              > > doing the addition,
              > > this is why the number jumps the way that it does.
              > >
              > > The shifting of a number continues until its LSB is
              > > over a zero in the
              > > current result. Once this occurs then the addition
              > > takes place again.
              > >
              > > The method is just a form of muliplication, you just
              > > don't know what
              > > you are multiplying by when you start the process.
              > > It's a process of
              > > finding the natural periodicity of the number
              > > concerned.
              > >
              > > It also proves, in a visual way, why any given prime
              > > divides at most
              > > one mersenne. And, by extension, why any given
              > > pseudo prime divides
              > > at most one mersenne.
              > >
              > > The interesting thing is that there is an implied
              > > rule as to which
              > > numbers divide which mersennes. This rule has to do
              > > with the
              > > distribution of 1's and 0's in the binary
              > > representation of the
              > > number.
              > >
              > > I noticed that in my earlier post I had something
              > > that wasn't clear.
              > >
              > > I actually count the bits in a generated number
              > > before the division.
              > >
              > > Taking the example of 23.
              > >
              > > 23 generates a string of 11 binary 1's or 2^11 - 1.
              > >
              > > This means that 23 divides 2^11 - 1.
              > >
              > > Now the primality test (??) requires dividing the
              > > power-1 (22) by
              > > number of bits in the generated mersenne. So we have
              > > 22/11 which is a
              > > whole number. Now it is this division that
              > > instantly shows you the
              > > difference between primes and pseudoprimes. Try it
              > > on a range of
              > > numbers and you will see what I mean.
              > >
              > >
              > > Kevin.
              > >
              > >
              >
              >
              >
              >
              >
              >__________________________________
              >Do you Yahoo!?
              >New and Improved Yahoo! Mail - 100MB free storage!
              >http://promotions.yahoo.com/new_mail
              >
              >
              >
              >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              >The Prime Pages : http://www.primepages.org/
              >
              >
              >Yahoo! Groups Links
              >
              >
              >
              >
            Your message has been successfully submitted and would be delivered to recipients shortly.