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

Cross Base Factorising

Expand Messages
  • Kevin Acres
    OK, here s a bombproof way to factorize a Mersenne, given that the algorithm is implementable in a computer. Please make me aware of any counter-example should
    Message 1 of 6 , Jul 1, 2004
    • 0 Attachment
      OK, here's a bombproof way to factorize a Mersenne, given that the
      algorithm is implementable in a computer. Please make me aware of any
      counter-example should you know of one.

      Remember that we are dealing solely with an exponent of a number to a given
      base. You don't need to keep the actual number itself in computer memory
      in an implementation.

      Given that the "reverse method" can find the smallest exponent in a given
      base for a given number.

      And given that p divides (n^(p-1))-1 where p is prime or a base n
      pseudoprime. Taken another way p+1 divides n^p - 1.

      Take a number known to be composite, in this case 2047 and check it against
      the smallest 3^n -1 number that it can divide.

      The reverse method shows us that 2047 divides 2^11-1 (itself) and 3^88 - 1.

      We now know for sure that 2047 isn't prime because 88 doesn't divide 2046,
      (2047-1).

      We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1 or 89.

      Now we find that 89 divides 2047 giving us 23, the other factor.
      Effectively factorizing 2^11-1 without ever having to work in base 2.

      Now take another number, this time known to be prime, 8191

      Applying the reverse algorithm in base 3 we find that 8191 divides 3^8190 -
      1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The reverse
      algorithm in base 2 shows that 8191 divides 2^13-1 and that 13 divides
      8190, therefore 8191 is base 2 prime as well.

      So am I wrong or does this method of factorizing work in all cases for
      Mersenne numbers?

      Kevin.
    • eharsh82
      Taken another way p+1 divides n^p - 1. This isn t true. Harsh ... any ... a given ... memory ... given ... against ... 3^88 - 1. ... divide 2046, ... or 89.
      Message 2 of 6 , Jul 1, 2004
      • 0 Attachment
        Taken another way p+1 divides n^p - 1.

        This isn't true.

        Harsh


        --- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
        wrote:
        > OK, here's a bombproof way to factorize a Mersenne, given that the
        > algorithm is implementable in a computer. Please make me aware of
        any
        > counter-example should you know of one.
        >
        > Remember that we are dealing solely with an exponent of a number to
        a given
        > base. You don't need to keep the actual number itself in computer
        memory
        > in an implementation.
        >
        > Given that the "reverse method" can find the smallest exponent in a
        given
        > base for a given number.
        >
        > And given that p divides (n^(p-1))-1 where p is prime or a base n
        > pseudoprime. Taken another way p+1 divides n^p - 1.
        >
        > Take a number known to be composite, in this case 2047 and check it
        against
        > the smallest 3^n -1 number that it can divide.
        >
        > The reverse method shows us that 2047 divides 2^11-1 (itself) and
        3^88 - 1.
        >
        > We now know for sure that 2047 isn't prime because 88 doesn't
        divide 2046,
        > (2047-1).
        >
        > We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1
        or 89.
        >
        > Now we find that 89 divides 2047 giving us 23, the other factor.
        > Effectively factorizing 2^11-1 without ever having to work in base
        2.
        >
        > Now take another number, this time known to be prime, 8191
        >
        > Applying the reverse algorithm in base 3 we find that 8191 divides
        3^8190 -
        > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The
        reverse
        > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13
        divides
        > 8190, therefore 8191 is base 2 prime as well.
        >
        > So am I wrong or does this method of factorizing work in all cases
        for
        > Mersenne numbers?
        >
        > Kevin.
      • Kevin Acres
        Hi, Perhaps, I didn t put it the right way. Where p+1 is prime it divides n^p - 1 i.e. 11 divides 2^10-1 and 23 divides 2^22-1 More importantly, for my
        Message 3 of 6 , Jul 1, 2004
        • 0 Attachment
          Hi,

          Perhaps, I didn't put it the right way.

          Where p+1 is prime it divides n^p - 1

          i.e. 11 divides 2^10-1 and 23 divides 2^22-1

          More importantly, for my example, 89 divides 3^88-1 .

          However, if you have a counter-example then please send it to me.

          Kevin.



          At 02:06 PM 2/07/2004, eharsh82 wrote:
          >Taken another way p+1 divides n^p - 1.
          >
          >This isn't true.
          >
          >Harsh
          >
          >
          >--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
          >wrote:
          > > OK, here's a bombproof way to factorize a Mersenne, given that the
          > > algorithm is implementable in a computer. Please make me aware of
          >any
          > > counter-example should you know of one.
          > >
          > > Remember that we are dealing solely with an exponent of a number to
          >a given
          > > base. You don't need to keep the actual number itself in computer
          >memory
          > > in an implementation.
          > >
          > > Given that the "reverse method" can find the smallest exponent in a
          >given
          > > base for a given number.
          > >
          > > And given that p divides (n^(p-1))-1 where p is prime or a base n
          > > pseudoprime. Taken another way p+1 divides n^p - 1.
          > >
          > > Take a number known to be composite, in this case 2047 and check it
          >against
          > > the smallest 3^n -1 number that it can divide.
          > >
          > > The reverse method shows us that 2047 divides 2^11-1 (itself) and
          >3^88 - 1.
          > >
          > > We now know for sure that 2047 isn't prime because 88 doesn't
          >divide 2046,
          > > (2047-1).
          > >
          > > We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1
          >or 89.
          > >
          > > Now we find that 89 divides 2047 giving us 23, the other factor.
          > > Effectively factorizing 2^11-1 without ever having to work in base
          >2.
          > >
          > > Now take another number, this time known to be prime, 8191
          > >
          > > Applying the reverse algorithm in base 3 we find that 8191 divides
          >3^8190 -
          > > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The
          >reverse
          > > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13
          >divides
          > > 8190, therefore 8191 is base 2 prime as well.
          > >
          > > So am I wrong or does this method of factorizing work in all cases
          >for
          > > Mersenne numbers?
          > >
          > > Kevin.
          >
          >
          >
          >
          >Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          >The Prime Pages : http://www.primepages.org/
          >
          >
          >Yahoo! Groups Links
          >
          >
          >
          >
        • eharsh82
          Perhaps it is K*p+1? Harsh ... the ... of ... number to ... computer ... in a ... n ... check it ... and ... 88+1 ... base ... divides ... The ... cases ...
          Message 4 of 6 , Jul 1, 2004
          • 0 Attachment
            Perhaps it is K*p+1?

            Harsh


            --- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
            wrote:
            > Hi,
            >
            > Perhaps, I didn't put it the right way.
            >
            > Where p+1 is prime it divides n^p - 1
            >
            > i.e. 11 divides 2^10-1 and 23 divides 2^22-1
            >
            > More importantly, for my example, 89 divides 3^88-1 .
            >
            > However, if you have a counter-example then please send it to me.
            >
            > Kevin.
            >
            >
            >
            > At 02:06 PM 2/07/2004, eharsh82 wrote:
            > >Taken another way p+1 divides n^p - 1.
            > >
            > >This isn't true.
            > >
            > >Harsh
            > >
            > >
            > >--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
            > >wrote:
            > > > OK, here's a bombproof way to factorize a Mersenne, given that
            the
            > > > algorithm is implementable in a computer. Please make me aware
            of
            > >any
            > > > counter-example should you know of one.
            > > >
            > > > Remember that we are dealing solely with an exponent of a
            number to
            > >a given
            > > > base. You don't need to keep the actual number itself in
            computer
            > >memory
            > > > in an implementation.
            > > >
            > > > Given that the "reverse method" can find the smallest exponent
            in a
            > >given
            > > > base for a given number.
            > > >
            > > > And given that p divides (n^(p-1))-1 where p is prime or a base
            n
            > > > pseudoprime. Taken another way p+1 divides n^p - 1.
            > > >
            > > > Take a number known to be composite, in this case 2047 and
            check it
            > >against
            > > > the smallest 3^n -1 number that it can divide.
            > > >
            > > > The reverse method shows us that 2047 divides 2^11-1 (itself)
            and
            > >3^88 - 1.
            > > >
            > > > We now know for sure that 2047 isn't prime because 88 doesn't
            > >divide 2046,
            > > > (2047-1).
            > > >
            > > > We also know that x+1 will divide 3^x -1. In this case x+1 is
            88+1
            > >or 89.
            > > >
            > > > Now we find that 89 divides 2047 giving us 23, the other factor.
            > > > Effectively factorizing 2^11-1 without ever having to work in
            base
            > >2.
            > > >
            > > > Now take another number, this time known to be prime, 8191
            > > >
            > > > Applying the reverse algorithm in base 3 we find that 8191
            divides
            > >3^8190 -
            > > > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3.
            The
            > >reverse
            > > > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13
            > >divides
            > > > 8190, therefore 8191 is base 2 prime as well.
            > > >
            > > > So am I wrong or does this method of factorizing work in all
            cases
            > >for
            > > > Mersenne numbers?
            > > >
            > > > Kevin.
            > >
            > >
            > >
            > >
            > >Unsubscribe by an email to: primenumbers-
            unsubscribe@yahoogroups.com
            > >The Prime Pages : http://www.primepages.org/
            > >
            > >
            > >Yahoo! Groups Links
            > >
            > >
            > >
            > >
          • eharsh82
            Yes it should work! Take a number known to be composite, in this case 2047 and check it against the smallest 3^n -1 number that it can divide. Finding n is
            Message 5 of 6 , Jul 1, 2004
            • 0 Attachment
              Yes it should work!

              "Take a number known to be composite, in this case 2047 and check it
              against the smallest 3^n -1 number that it can divide."

              Finding n is really difficult for large numbers. So your algorithm is
              not practical.


              Harsh





              --- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
              wrote:
              > OK, here's a bombproof way to factorize a Mersenne, given that the
              > algorithm is implementable in a computer. Please make me aware of
              any
              > counter-example should you know of one.
              >
              > Remember that we are dealing solely with an exponent of a number to
              a given
              > base. You don't need to keep the actual number itself in computer
              memory
              > in an implementation.
              >
              > Given that the "reverse method" can find the smallest exponent in a
              given
              > base for a given number.
              >
              > And given that p divides (n^(p-1))-1 where p is prime or a base n
              > pseudoprime. Taken another way p+1 divides n^p - 1.
              >
              > Take a number known to be composite, in this case 2047 and check it
              against
              > the smallest 3^n -1 number that it can divide.
              >
              > The reverse method shows us that 2047 divides 2^11-1 (itself) and
              3^88 - 1.
              >
              > We now know for sure that 2047 isn't prime because 88 doesn't
              divide 2046,
              > (2047-1).
              >
              > We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1
              or 89.
              >
              > Now we find that 89 divides 2047 giving us 23, the other factor.
              > Effectively factorizing 2^11-1 without ever having to work in base
              2.
              >
              > Now take another number, this time known to be prime, 8191
              >
              > Applying the reverse algorithm in base 3 we find that 8191 divides
              3^8190 -
              > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The
              reverse
              > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13
              divides
              > 8190, therefore 8191 is base 2 prime as well.
              >
              > So am I wrong or does this method of factorizing work in all cases
              for
              > Mersenne numbers?
              >
              > Kevin.
            • Kevin Acres
              Actually it is practical. Remember that you don t store the actual number, only the exponent. So in the example of 3^88-1 I know that everything below my
              Message 6 of 6 , Jul 1, 2004
              • 0 Attachment
                Actually it is practical.

                Remember that you don't store the actual number, only the exponent. So in
                the example of 3^88-1 I know that everything below my addition point is
                2222222..... As such it gets discarded. I only count how many 2's I get in
                the string.

                Kevin.




                At 04:26 PM 2/07/2004, eharsh82 wrote:
                >Yes it should work!
                >
                >"Take a number known to be composite, in this case 2047 and check it
                >against the smallest 3^n -1 number that it can divide."
                >
                >Finding n is really difficult for large numbers. So your algorithm is
                >not practical.
                >
                >
                >Harsh
                >
                >
                >
                >
                >
                >--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>
                >wrote:
                > > OK, here's a bombproof way to factorize a Mersenne, given that the
                > > algorithm is implementable in a computer. Please make me aware of
                >any
                > > counter-example should you know of one.
                > >
                > > Remember that we are dealing solely with an exponent of a number to
                >a given
                > > base. You don't need to keep the actual number itself in computer
                >memory
                > > in an implementation.
                > >
                > > Given that the "reverse method" can find the smallest exponent in a
                >given
                > > base for a given number.
                > >
                > > And given that p divides (n^(p-1))-1 where p is prime or a base n
                > > pseudoprime. Taken another way p+1 divides n^p - 1.
                > >
                > > Take a number known to be composite, in this case 2047 and check it
                >against
                > > the smallest 3^n -1 number that it can divide.
                > >
                > > The reverse method shows us that 2047 divides 2^11-1 (itself) and
                >3^88 - 1.
                > >
                > > We now know for sure that 2047 isn't prime because 88 doesn't
                >divide 2046,
                > > (2047-1).
                > >
                > > We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1
                >or 89.
                > >
                > > Now we find that 89 divides 2047 giving us 23, the other factor.
                > > Effectively factorizing 2^11-1 without ever having to work in base
                >2.
                > >
                > > Now take another number, this time known to be prime, 8191
                > >
                > > Applying the reverse algorithm in base 3 we find that 8191 divides
                >3^8190 -
                > > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The
                >reverse
                > > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13
                >divides
                > > 8190, therefore 8191 is base 2 prime as well.
                > >
                > > So am I wrong or does this method of factorizing work in all cases
                >for
                > > Mersenne numbers?
                > >
                > > Kevin.
                >
                >
                >
                >
                >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.