Sorry, an error occurred while loading the content.

## Re: Cross Base Factorising

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