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

Expand Messages
• 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
Shift left
Shift left
Iteration 3:
temp = 1011 1000
build = 1 0111
Iteration 4:
temp = 1 0111 0000
build = 1100 1111
Shift left
Iteration 6:
temp = 101 1100 0000
build = 10 0011 1111
Final build is 2047
In Binary = 111 1111 1111

Kevin.
• 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
> Shift left
> Shift left
> Iteration 3:
> temp = 1011 1000
> build = 1 0111
> Iteration 4:
> temp = 1 0111 0000
> build = 1100 1111
> Shift left
> Iteration 6:
> temp = 101 1100 0000
> build = 10 0011 1111
> Final build is 2047
> In Binary = 111 1111 1111
>
>
> 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
very interesting if it indeed does work out.

-David C.
• 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,

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/
>
>
>
>
>
>
>
>
>
• 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,
>
>
> I don't print the iteration number when I'm not
> 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
• 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,
> >
> >
> > I don't print the iteration number when I'm not
> > 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/
>
>