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

Re: [PrimeNumbers] Re: Cross Base Factorising

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