- 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

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 have a couple of questions. (given below.)

Kevin Acres wrote:>

First, I hate to bring up semantics, but ALL numbers of the form 2^n - 1

> 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.

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.

>

I was wondering, why do your iteration numbers up above go 0, 3, 4, 6?

> 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.

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. - 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 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.)

slightly

>

> Kevin Acres wrote:

> >

> > Hi,

> >

> > I thought that I would pass this on, seeing as how it may be

> > different to the normal run of the mill algorithm.

number

> >

> > There is a trivial tranformation that can be applied to any odd

> > 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.

2^n - 1

>

> First, I hate to bring up semantics, but ALL numbers of the form

> are Mersenne numbers. The ones where (2^n - 1) is prime is called a

Composites.

> Mersenne Prime. I guess the others would be called Mersenne

>

identifiable.

> >

> > 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

> >

(10111

> > 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

> > binary).

6?

> >

> > 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,

> 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/

>

>

> Yahoo! Groups Links

>

>

>

>

>

>

> - 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,

__________________________________

>

> 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 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 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,

> >

> > 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 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/

>

>

>Yahoo! Groups Links

>

>

>

>