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

Re: Cross Base Factorising

Expand Messages
  • 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 1 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 2 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.