mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-08-02, 10:41   #34
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·7·227 Posts
Default

Thanks. It worked now in Linux with Prime95 28.9 source, but not in Windows with MSYS2, but that is ok.



When I tried the newest 29.4b7 source gwnum compiled fine, but hybrid.c did not:

gwnum/gwnum.a(gwbench.o): In function `unixDlError':
gwbench.c:(.text+0x1e2f1): undefined reference to `dlerror'
gwnum/gwnum.a(gwbench.o): In function `unixDlClose':
gwbench.c:(.text+0x55d4): undefined reference to `dlclose'
gwnum/gwnum.a(gwbench.o): In function `unixDlSym':
gwbench.c:(.text+0x55e7): undefined reference to `dlsym'
gwnum/gwnum.a(gwbench.o): In function `unixDlOpen':
gwbench.c:(.text+0x55f9): undefined reference to `dlopen'
collect2: error: ld returned 1 exit status

These are functions in the sqlite3.c, but it is not important for me to use the newest gwnum, I was just curious.
ATH is online now   Reply With Quote
Old 2018-08-02, 11:48   #35
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

2×52×11 Posts
Default

--- Stoopid answer removed :)

Last fiddled with by ldesnogu on 2018-08-02 at 11:48
ldesnogu is offline   Reply With Quote
Old 2018-08-02, 11:56   #36
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,291 Posts
Default

Code:
LIBS = ../gwnum/gwnum.a ../gwnum/gwnum.ld -lm -lpthread -Wl,-Bstatic -lhwloc -Wl,-Bstatic -lcurl -Wl,-Bdynamic -lrt -lstdc++ -ldl -lgmp
Lifted from the linux64 29.4b7 make file. Obviously replace ../gwnum/gwnum.a with gwnum/gwnum.a -- too lazy to create a make file. I can imagine adding -ldl -lgmp to my list will do it. Obviously you will need GMP installed, which could be used for the jacobi symbol calculation instead of my dead slow gwnum/giants implementation of it.

Last fiddled with by paulunderwood on 2018-08-02 at 12:05
paulunderwood is offline   Reply With Quote
Old 2018-08-08, 15:07   #37
GP2
 
GP2's Avatar
 
Sep 2003

5×11×47 Posts
Default

I wonder if it would make sense to have a Python extension module for gwnum, something similar to gmpy2 for GMP?

Last fiddled with by GP2 on 2018-08-08 at 15:07
GP2 is offline   Reply With Quote
Old 2018-11-26, 19:42   #38
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,291 Posts
Default Speeding up "hybrid"

I have a new test based on a fusion of the components of the (Q=1) Baillie-PSW test:

Code:
{tst(n)=local(a);!issquare(n);
a=3;while(kronecker(a^2-4,n)!=-1,a++);
Mod(Mod(1,n)*x*2,x^2-a*x+1)^(n+1)==4}
To get the two selfridges, I observe for squaring:

Code:
Mod(s*x+t,x^2-a*x+1)^2
Mod((a*s^2 + 2*t*s)*x + (-s^2 + t^2), x^2 - a*x + 1)
and multiplying by the base x*2:

Code:
Mod((s*x+t)*2*x,x^2-a*x+1)
Mod((2*a*s + 2*t)*x - 2*s, x^2 - a*x + 1)
However, we cannot just check 2-PSPs. For example [n,a]=[48599, 146] is a (non-minimal a) pseudoprime to this test, but gcd(Mod(2,n)^n-2,n)==23. I am continuing to find a gcd==1.

Last fiddled with by paulunderwood on 2018-11-26 at 19:44
paulunderwood is offline   Reply With Quote
Old 2018-11-27, 03:25   #39
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,291 Posts
Default

The main problem with efficiency is the computation of "-2*s" -- I don't think GWNUM handles negative numbers. So I had to introduce a new variable "wZ" to hold zero and subtract from it.

The new program "fusion.c" is attached. It is very slightly slower than "hybrid.c".

Can anybody shed any light on why gcd(Mod(2,n)^n-2,n)!=1 for such pseudoprimes?
Attached Files
File Type: zip fusion.c.zip (2.0 KB, 190 views)
paulunderwood is offline   Reply With Quote
Old 2018-11-27, 15:36   #40
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

387310 Posts
Default erratum

Code:
{tst(n)=local(a);!issquare(n);
a=3;while(kronecker(a^2-4,n)!=-1,a++);
Mod(Mod(1,n)*x*2,x^2-a*x+1)^(n+1)==4}
should be

Code:
{tst(n)=local(a=3);!issquare(n)&&
while(kronecker(a^2-4,n)!=-1,a++);
Mod(Mod(1,n)*x*2,x^2-a*x+1)^(n+1)==4}



Further: If

Code:
Mod(Mod(1,n)*a*x,x^2-a*x+1)^(n+1)==a^2
also seems to imply

Code:
gcd(Mod(a,n)^n-a,n)!=1

Last fiddled with by paulunderwood on 2018-11-27 at 15:52
paulunderwood is offline   Reply With Quote
Old 2018-11-30, 04:18   #41
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,291 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
However, we cannot just check 2-PSPs. For example [n,a]=[48599, 146] is a (non-minimal a) pseudoprime to this test, but gcd(Mod(2,n)^n-2,n)==23. I am continuing to find a gcd==1.
If we calculate r=Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2), then r has to be -2 or +2. I cannot determine which, but now we can check against 2-PSPs... I have just checked for non-square odd 2-PSPs < 2^64

The modified program is attached.
Attached Files
File Type: zip fusion.c.3.zip (2.1 KB, 192 views)
paulunderwood is offline   Reply With Quote
Old 2018-12-13, 16:11   #42
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3×1,291 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
If we calculate r=Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2), then r has to be -2 or +2. I cannot determine which, but now we can check against 2-PSPs... I have just checked for non-square odd 2-PSPs < 2^64
I finally worked it out. In general, for some integer b with gcd(b,n)=1 (with jacobi(a^2-4,n)=-1):

(bx)^{\frac{n+1}{2}} \equiv jacobi(b,n)jacobi(a+2,n)b \pmod{n,x^2-ax+1}

I claim that b^{\frac{n-1}{2}} \equiv jacobi(b,n) \pmod{n} is a necessary condition.

Last fiddled with by paulunderwood on 2018-12-13 at 16:41
paulunderwood is offline   Reply With Quote
Old 2018-12-16, 21:48   #43
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·1,291 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I finally worked it out. In general, for some integer b with gcd(b,n)=1 (with jacobi(a^2-4,n)=-1):

(bx)^{\frac{n+1}{2}} \equiv jacobi(b,n)jacobi(a+2,n)b \pmod{n,x^2-ax+1}

I claim that b^{\frac{n-1}{2}} \equiv jacobi(b,n) \pmod{n} is a necessary condition.
b-PRP is guaranteed!

Attached is the latest fusion.c which gets the sign of 2 right:
Attached Files
File Type: c fusion.c (6.4 KB, 206 views)

Last fiddled with by paulunderwood on 2018-12-16 at 21:52
paulunderwood is offline   Reply With Quote
Old 2018-12-27, 13:02   #44
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

387310 Posts
Default

A tiny speed up can be had in my sloooow "giants" Jacobi symbol calculations by noting that: jacobi(2,n) * jacobi(a+2,n) = jacobi(2*(a+2), n)
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
LLR V3.8.2 using gwnum 26.2 is available! Jean Penné Software 25 2010-11-01 15:18
GWNUM? Unregistered Information & Answers 3 2010-09-12 19:52
GWNUM library and llr leizhoucn Programming 2 2007-11-05 09:34
Compiling GMP-ECM With GWNUM tmorrow GMP-ECM 5 2007-04-04 00:39
GWNUM as DLL? Cyclamen Persicum Software 1 2007-01-02 20:53

All times are UTC. The time now is 05:47.


Mon Oct 25 05:47:27 UTC 2021 up 94 days, 16 mins, 0 users, load averages: 0.96, 1.07, 1.02

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.