mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-09-05, 19:41   #12
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·461 Posts
Default

Quote:
Originally Posted by axn View Post
The s variable is a Mod() object. All operations with it will automatically work modulo N.
I should read again the documentation of PARI/gp... ;) However, I'm now involved with porting Ruby and Python3, and then Go, on AIX, so I'm fed up reading language documentation. So, I know very basic things about PARI/gp. Some time, when I have time, I'll read more ! ;) Anyway, thanks to help me understand. For now, I do not care about performance of PARI/gp programs.
T.Rex is offline   Reply With Quote
Old 2015-09-05, 21:58   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F6C16 Posts
Default

Is there any need to run verification now "mathlove" has proved this composite test?

Does it produce fewer pseudoprimes than base-a Fermat PRP tests?

Last fiddled with by paulunderwood on 2015-09-05 at 22:15
paulunderwood is online now   Reply With Quote
Old 2015-09-06, 18:59   #14
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·461 Posts
Default

About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .
T.Rex is offline   Reply With Quote
Old 2015-09-06, 19:32   #15
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by T.Rex View Post
About proving the sufficiency, I think that an issue (as I already said) is that s can be equal to sn before i==n-1 .
Finding s(n-1)==sn only after n-1 iterations and not before is important I think.
I think that it is important to add a check s!=sn after the computation of s from i=1,n-2 .
if it loops multiple times it should in theory loop at multiples of a divisor of n-2 if it's going to have the final result match, but of course that would mean n = all multiples of that divisor +2, should give prime N.
science_man_88 is offline   Reply With Quote
Old 2015-09-07, 17:32   #16
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·461 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Does it produce fewer pseudoprimes than base-a Fermat PRP tests?
If we use the test as-is: ( if(s==sn && ! isprime(N) ), it produces pseudoprimes, like: 1*2^3+1 or 98*2^79+17 .

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : produces 34 pseudoprimes.

But, if we check that no S(i) is equal to S(sn-1) with i=1...n-2 , there are less.

... z=0; forstep(i=n,3,-1, s=sqr(s)-2; if(s==sn, z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn && ! isprime(N), print("k: ",k," c: ",c," n: ",n)))

? for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13.
k: 1 c: 1 n: 3
k: 15 c: 1 n: 3
k: 33 c: 25 n: 79
k: 35 c: 17 n: 83
k: 37 c: 17 n: 92
k: 45 c: 1 n: 3
k: 49 c: 17 n: 80
k: 66 c: 25 n: 78
k: 70 c: 17 n: 82
k: 74 c: 17 n: 91
k: 95 c: 17 n: 77
k: 97 c: 17 n: 48
k: 98 c: 17 n: 79

With c=1, 17, or 25 only, within the limits used for k, c and n.
However, there are others, like: 16*2^121+33 .

Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .

For c<0, it seems to appear only with: c= 5, 29 , like: 8*2^158-29 or 11*2^232-5 .

Last fiddled with by T.Rex on 2015-09-07 at 18:07 Reason: Add note about special values of c and -c that create pseudoprimes.
T.Rex is offline   Reply With Quote
Old 2015-09-07, 18:42   #17
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16328 Posts
Default

for(k=1,100,for(c=0,50,CEk2c(k,2*c+1,100))) : there are only 13 pseudoprimes out of 5588 numbers verifying the test; including 5575 primes: 0.23% of pseudoprimes. Out of a total of 125,000 numbers N tested.

For c<0, there are 1.22% of pseudoprimes (72 out of 5866 numbers verifying the test, including 5794 primes). Out of a total of 125,000 numbers N tested.
T.Rex is offline   Reply With Quote
Old 2015-09-07, 21:53   #18
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×461 Posts
Default

Quote:
Originally Posted by T.Rex View Post
Up to now, for c>0, they all seem to appear when c = 1 mod 8 : 1, 17, 25, 33, 41, 73 .
There are also pseudo primes for c=89, but not with 81, 87, 105, with the following bounds:
for(k=1,300,CEk2c(k,89,300)) :
133*2^262+89
221*2^291+89
266*2^261+89
T.Rex is offline   Reply With Quote
Old 2015-09-07, 23:26   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

226358 Posts
Talking

A few trivial things about Chebyshev polynomials replace all that "mathlove" wrote in pages of scribbles in a simple way.
One has to admire how he repeated copy-pasted pages of similar arguments in each of the primus' questions (of which there are scores and the all look the same, only maybe with different values of c, or base). Do these guys ever get tired of typing?! I think not. Everyone gets their kicks of it. mathlove gets a load of stackexchange's "credits" (like PrimeGrid's, but slightly more useful perhaps) for answering the same question 20 times. Hats off to his/her stamina.

Ponder these:
1. https://en.wikipedia.org/wiki/Lissajous_curve : x=A\sin(at+\delta),\quad y=B\sin(bt)
2. Lissajous figures where a=1, b=N (with N a natural number) and \delta=\frac{N-1}{N}\frac{\pi}{2}\ are Chebyshev polynomials
3. Chebyshev polynomial T_n(cos \theta) = cos(n \theta) (one of the definitions)
4. Using renormalized C_n(v) = 2 T_n(v/2), \ C_{km}(x) = C_k(C_m(x)); in particular C_{k b^n}(x) = C_b(C_b(C_b(...C_b(C_k(x))...))) {n times}.

So, the whole iterated calculation is a calculation of T_{k*2^n}(a) and comparing it to T_c(a) with some a value like a = cos \delta . Because of periodicity of cos, the result is obvious. In a way, this is a "Fermat" test z^N = z ("mod" N) in complex plane and with irrational complex z = e^{i \theta} with imaginary half of calculations swept under the carpet, projected on real axis only. (A Frobenius PRP test?)

primus has been boring people with these trivialities for years now. Search this forum. And always it was "A new conjectured primality test bla-bla-bla" .
Only in 2015, he finally settled down for them as PRP tests, which they are; but as such, they are trivial!

All you need to realize is the property 4, which makes the purpose of iterations painfully obvious: you are calculating the C_{N-c}(a), because N-c = k*b^n, then compare that the cos(N {{N-c} \over  N} {\pi \over 2}) = cos(N {-c \over N} {\pi \over 2}). Of course it is!
Batalov is offline   Reply With Quote
Old 2015-09-08, 20:17   #20
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·461 Posts
Default

Quote:
Originally Posted by Batalov View Post
A few trivial things about... .... "A new conjectured primality test bla-bla-bla" .
O.... they are trivial!
.... Of course it is!

Hummm Sometimes, I'm saying myself that I should go back to photography and forget Maths, where I was not so good even before I forgot so many things !

Anyway, thanks for the explanations !

So, you transformed something mysterious into something nearly obvious... I'm sad ! But that's the (Math) rule/law.

Anyway, what is surprising me is that, with some modification of his algorithm, I no more can find pseudoprimes (which does NOT mean that there are no more, for sure).

In a previous post, I said that, with c>0, pseudoprimes seem to be only N=k*2^n+c where c = 1 mod 8.
If you eliminate Ns such that S(i)==S(n-1) with i<n-1, and then if you eliminate Ns such that N= 0 mod(2*c-1) , I no more find pseudoprimes. Last check means that remaining numbers Ns only have 2*c-1 as simple factor. The examples I have factored do confirm: they have a unic small factor (never prime) and a very big prime factor.

Examples (where N passes the test before my last filter and are pseudoprimes):
N=171*2^379+145 = 0 mod 17^2 , and 17^2=2*145-1 .
factor(171*2^379+145) : 17^2 * 728562182048384077130159586626790436923511614970760313605012778127813410783523249843408253631630684967337087623537

N=307*2^319+105 = 0 mod 11*19 and 11*19 = 2*105-1
factor(307*2^319+105) : 11*19 * 1568775167530429175347539865536010763595766240104048804721870271773735540226451313055142011218969

N=471*2^393+73 = 0 mod 5*29 and 5*29 = 2*73-1
factor(471*2^393+73): 5*29 * 65530155850158078972410448815378156940155788169319195826683219662211477907862726436991538868262118459391723814610133049

N=17*2^399+137 = 0 mod 3*7*13 and 3*7*13 = 2*137-1
factor(17*2^399+137): 3*7*13 * 80399721478896421289653161033060809274001828714463003146742141137712471747777106792498115395169126619799183010140489721

The same for a dozen of other similar pseudoprimes.

In short, the 2 filters I have added seem to remove all pseudoprimes (which are of a special form and could be used for finding other big primes).

That may hide something obvious, for sure. But, the algorithm below no more finds PRPs/pseudoprimes (or I haven't tested with large-enough numbers, for sure. Or my code is wrong.).
Would you mind explaining why it seems to work ?

Code:
CEk2c(k,c,g)=
{
a=6;
h=a/2;
if(c>0,s=1,s=-1;c*=-1);
for(n=c<<1+1,g,
N=k<<n+s*c;
e=c%4;
if(e==1,,e=-1);
d=((c-e)%8)/4;
f=((-1)^d);
B=f*s;
A=(c-B)/2;
s0=Mod(polchebyshev(k,1,h)<<1,N);
sn=Mod(f*polchebyshev(A,1,h)<<1,N);
my(s=s0);
z=0;
forstep(i=n,3,-1,s=sqr(s)-2;if(s==sn,z=1;break));
s=sqr(s)-2;
if(z==0 && s==sn, y=Mod(N,2*c-1);if(!isprime(N)&&y!=0, print(k,"*2^",n,"+",c)))
);
}

for(k=1,100,for(c=0,100,CEk2c(k,2*c+1,200)))
for(k=1,100,for(c=101,200,CEk2c(2*k+1,2*c+1,800)))

Last fiddled with by T.Rex on 2015-09-08 at 20:19 Reason: orthograph
T.Rex is offline   Reply With Quote
Old 2015-09-08, 21:08   #21
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,629 Posts
Default

Quote:
Originally Posted by T.Rex View Post
...If you eliminate Ns such that <<...>>, and then if you eliminate Ns such that <<...>>, I no more find pseudoprimes.
If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.

Compare it with the way this thread went,
and on to http://www.mersenneforum.org/showthr...943#post380943

This is long ago and well described by A.A. Milne as the character of Tigger.
Tigger first claims: 'Tiggers eat evertyhing'.
After being presented with honey, he "improves" his theory to 'Tiggers eat evertyhing except honey'.
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?
Batalov is offline   Reply With Quote
Old 2015-09-09, 13:23   #22
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2×461 Posts
Default

Quote:
Originally Posted by Batalov View Post
If you eliminate more and more, finally you simply get yourself in an illusory environment when you can no longer find counterexamples, -- and so what? It simply means that no one is willing to find them, but they are still there, only larger.
....
After being presented with acorns, he further "improves" his theory to 'Tiggers eat evertyhing except honey and acorns'.
Can you blame anyone for not taking him all too seriously after that?
Hummmmm I understand your point.
However, don't you think that there are other ways for finding new stuff than using pure Math proof ? Is there a place for experimenting ? Years ago, before computers were there, many mathematicians used pen, paper, and figures, for exploring something that looked weird for them at first, before they search for a math proof. Now, we have computers. Remember S. Ramanujan: he never used more than a slate since he was unable to pay for note-books and paper at first and because he had a wrong idea about what "good" maths are: find a property and PROVE it ; however his findings were remarkable and mathematicians are still studying his findings. However, there was only 1 Srinivasa...

Now, back to what I did:
- primus published 4 conjectures about a property of primes
- I generalized the conjectures into one
- someone proved the conjecture and, as you explained, it was not so difficult to prove and it is simply another way to present something already known
- however, what about pseudoprimes ?
- I found a limited number of pseudoprimes
- I used the idea: not only S(n-1) must have a special value Sn, but S(i) must not be equal to S(n) when i<n-1, because some Sn values are a dead-end, like 2 : 2^2-2=2 , and because we must not enter a cycle with length smaller than n-1, with the idea that a minimum of n-1 different steps are required for showing a prime, as for Mersenne/Fermat LLT. The other idea is that, for very simple numbers like Mersenne and Fermat, so close to 2^n, about n iterations of X^2-2 mod N is enough, though for numbers moving away from pure 2^n more steps should be required, which are the P_k and P(c) functions that add more steps before and after the (s^2-2 mod N) part. The idea is that there must be a minimum of steps to run in order to have something that can be a prime test. A number N being a prime creates a symmetric structure ; running a minimum number of steps in the structure of a number is required in order to discover if the symmetry is broken due to a factor of N. What is magic with LLT for Mersenne/Fermat is this: you run n-1 steps in the digraph, from a starting point to a ending point, and bingo! it is a prime. This should work, under more complex conditions, for other numbers, where starting and ending points are more difficult to define since they depend on other characteristics of the number than the power of n : k and c in addition, like primus did.
- then, I found that ALL the remaining pseudoprimes I can find (c>0) share the same characteristics: c= 1 mod 8 , and N=0 mod (2*c-1) .
- and then I shown that ALL these remaining pseudoprimes look strange: only 1 small factor (2c-1) and a big prime. They do NOT look like random factors as expected for random exceptions in the theory. They share a property, probably showing something deep and interesting to look at.
- and, at the end, filtering this unique class of pseudoprimes, I cannot find more pseudoprimes (up to the limits of my computer).

For sure, that does NOT provides a proof.
That is only showing "strange" properties that seem to exist with very big numbers and with a very big number of numbers tried.
And, as you say, after honey and acorns, there could be ants and mushrooms. Or not.

I remember an example from a book of JP Delahaye, where 2 sequences A(n) and B(n) generate coprime numbers ... up to n being very very big where an exception occured.

But, in our case, we are using methods that are well known and have already provided good results, like LLT for Mersenne numbers and LLT for Fermat numbers, which are true prime tests.
So, we have the expectation to find something that works, under strict conditions.

So, I have only used 2 filters.

Remind also that, for c<0, I found that all pseudoprimes I've found have the same structure.

For sure, there could be another kind of pseudoprimes with much higher values for: k, n, or c . And, in that case, the conjecture will be the Tiger you are talking about.

Last fiddled with by T.Rex on 2015-09-09 at 14:02 Reason: english
T.Rex is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Compositeness test jnml Miscellaneous Math 10 2018-01-27 16:20
Conjectured Primality Test for Specific Class of Mersenne Numbers primus Miscellaneous Math 1 2014-10-12 09:25
Conjectured Primality Test for Specific Class of k6^n-1 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15
Conjectured Primality Test for 2^p-1, (2^p+1)/3 and (2^2^n+1) T.Rex Math 75 2007-09-04 07:53
PRP => LL-tests? Holmes Math 1 2005-05-13 17:18

All times are UTC. The time now is 22:13.


Tue Dec 7 22:13:08 UTC 2021 up 137 days, 16:42, 0 users, load averages: 1.82, 1.70, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.