A (new) old, (faster) slower mersenne-(primality) PRP test

[boldi]

Originally Posted by science_man_88

I have copied your code, and get that is not prime.

? NewMersenneFast(p) = {

local(m, m1, m2, b);

m = 1<<p - 1;
m1 = m - 1;
m2 = m1 / 2;

b = lift(Mod(3, m)^m2);

if (b == M1, print(p, " prime"), print(p, " no prime"));
}
? NewMersenneFast(132049)
  ***   at top-level: NewMersenneFast(1320
  ***                 ^--------------------
  ***   in function NewMersenneFast: ...1;m2=m1/2;b=lift(Mod(3,m)^m2);if(b==M1,print(
  ***                                                            ^--------------------
  *** _^_: user interrupt after 1min, 45,507 ms.

  ***   Break loop: type <Return> to continue; 'break' to go back to GP
break>
? NewMersenneFast(1061)
1061 no prime
? NewMersenneFast(7)
7 no prime

Though I've said things that you might like, I get why in the end you need to prove it works to only find primes, namely Pseudoprimes

Thank You for Your constructive post. You have to change only

b == M1 to b == m1


So the correct code is:

/*--------------------------------------------------------------
New Mersenne test as fast as possible in Pari/GP
--------------------------------------------------------------*/
NewMersenneFast(p) = {

local(m, m1, m2, b);

m = 1<<p - 1;
m1 = m - 1;
m2 = m1 / 2;

b = lift(Mod(3, m)^m2);

if (b == m1, print(p, " prime"), print(p, " no prime"));
}
/*------------------------------------------------------------*/

Greetings
boldi

[boldi]

Originally Posted by Batalov

Well, there, you've demonstrated that you also cannot read.

They have proved their theorem. I repeat: their theorem.
"Your" "conjecture" is the converse of little Fermat and is known for centuries to be proven - that is, proven false. Did you get this? I repeat: proven false.

To Your surprise, I know Fermats little theorem.

As I can see, You make the same mistake as M. and S. -- You misunderstood the conjecture as Fermat test. This is not the case.

Greetings
boldi

[boldi]

@Mayer
@Silverman
@Batalov

thank You for Your replies, but please calm down. It is not necessary to attack me. Let us be constructive. All I have done is, to give a conjecture, I have also shown a new algorithm, and all I ask is, if anybody knows, if the conjecture ist proven or unproven. But all I have got are personal attacks.

I attacked no one here. But if someone tolds me, "this [conjecture] is in fact a long-since-disproven - allegations", I have every right to ask for a paper where I can read about it.

But it seems more and more, that You misunderstood the conjecture as Fermat test -- this is not the case. Fermat's little theorem states, that if p is a prime number, then for any integer a, the number a^p − a is an integer multiple of p.

What I say is more specific: Take the number 3 and a Mersenne number M. If 3 and M satisfies the relation 3^(M-1) ≡ 1 mod M, then M must be a prime number. In Fermats little theorem You will not find such an statement. Sure, the conjecture is next to Fermat test, but it is not the same. Compared with the Fermat test, there are also no pseudo prime numbers who can pass this test. (This is my claim, and all I do here is ask for a well-known proof.) The conjecture is also only menat for number 3 as base, not for other numbers like in Fermat test. So please stop pointing me to Fermats little theorem.

All I ask is: Is the conjecture 3^(M-1) ≡ 1 mod M (only if M is prime) proven or is it disproven, or where can I read about it?

Again I make the proposal to be constructive. I think we are all interested in number theory, and the prime research and his math are fascinating topics. If the conjecture is unproven, we could work together to find a proof and create a new prime test.

The positive thing is: The recursive algorithm I have shown is only an example to point out, that the conjecture leads to an algorithm, wich is at least as simple as Lucas Lehman. I have never told, this is the best way to calculate the congruence relation.

Compared with Lucas-Lehmer, we can caluclate the relation not only in one recursive way. We have to calculate a modular exponentiation and this can be done in several ways. May be we find some one, who needs less time as LL. (This is because I am here). It would be great if we could discuse the best modular exponentiation algorithm available for this task.

Also it is possible to write down the conjecture in other terms. Examples are:

3^(M-1) ≡ 1 mod M (only if M is prime) or

3^M ≡ 3 mod M or

3^((M-1)/2) ≡ -1 mod M or

3^((M+1)/2) ≡ -3 mod M

From my point of view, all these expressions could be valid prime tests. And may be we find some other, who fullfill better the needs of modular exponentiation algorithm. I think, the math behind LL does not allow so many possibilities.


Greetings
boldi

[kracker]

Wrong or right... parts of this forum is the place to go to get attacked if you are wrong in even a degree, sadly.

[boldi]

Originally Posted by paulunderwood

I don't think you can compare optimized Pari-GP internals for expmod with other unoptimized code.

Sure. But what I would like to demonstrate is: By LL there is no further optimization possible. You can square and substract, thats all. But if conjecture holds, we can do modular exponentation, and there are several ways to do so. For example, the recursive algorithm I have shown, is similar to the binary modular exponentation.

But it could be we find a better exponentation for this task or we find a better congruence to get faster results. From my point of view, the shown congruence is only a starting point.

Therefore you cannot extrapolate to Prime95/mprime timings. Even if your test was a proof, it might save less than one second on a test which takes P95 60 days

I think it is a little bit more. And do not forget it is not only one test, there are 100 and 1000 tests all over the world. If it is only one second pro test, ok, just let us save this second. Its a matter of progress.

Greetings
boldi

[chalsall]

Originally Posted by kracker

Wrong or right... parts of this forum is the place to go to get attacked if you are wrong in even a degree, sadly.

In my opinion, not sadly.

If one is wrong one must accept being questioned for being wrong -- and be willing to stand up if one believes one are correct.

It's called the "Scientific Method". It's healthy, although many find it uncomfortable (did I smell that correctly?).

[kracker]

Originally Posted by chalsall

In my opinion, not sadly.

If one is wrong one must accept being questioned for being wrong -- and be willing to stand up if one believes one are correct.

It's called the "Scientific Method". It's healthy, although many find it uncomfortable (did I smell that correctly?).

That is true and healthy, but that is not the condition here. Have you heard of "overload"?

[chalsall]

Originally Posted by kracker

Have you heard of "overload"?

Yes.

[Batalov]

So you can write:

Originally Posted by boldi

Where are Your facts? I can only see unproved claims.
...
You should read more seriosley.

and then take the same questions:

boldi, Where are Your facts? I can only see unproved claims.
...
You should read more seriously.

from others as an attack? Are you capable of at least trying to be objective?

[science_man_88]

Originally Posted by boldi

Sure. But what I would like to demonstrate is: By LL there is no further optimization possible. You can square and substract, thats all. But if conjecture holds, we can do modular exponentation, and there are several ways to do so. For example, the recursive algorithm I have shown, is similar to the binary modular exponentation.

But it could be we find a better exponentation for this task or we find a better congruence to get faster results. From my point of view, the shown congruence is only a starting point.

I think it is a little bit more. And do not forget it is not only one test, there are 100 and 1000 tests all over the world. If it is only one second pro test, ok, just let us save this second. Its a matter of progress.

Greetings
boldi

There are LL possibilities from the one you listed instead of s^2-2 you could say, well all s are 2*x for some value x since for M to divide 2*x it must divide one of them it divides into x as well so you can cut each in half, and that gives you the new equation 2*x^2-1 . Can you come up with others? can you come up with properties of Mersenne primes, and some for powers of 3, that can help you prove the congruence can only happen for Mersenne primes and not Mersenne numbers in general ?

[chalsall]

Originally Posted by science_man_88

There are LL possibilities from the one you listed instead of s^2-2 you could say, well all s are 2*x for some value x since for M to divide 2*x it must divide one of them it divides into x as well so you can cut each in half, and that gives you the new equation 2*x^2-1.

Are you distantly related to Rick Mercer?