20200308, 01:05  #1 
"Sam"
Nov 2016
101001111_{2} Posts 
Comparison to ECPP?
For PARI/GP:
Code:
rset(n)={ prime_fact_r=[]; cr=1; cr_max=round(log(n))^2; q=2*round(log(log(n))); while(cr<cr_max, q=nextprime(q+1); if(n^2%q!=1 & n%q!=0, o=znorder(Mod(n,q)); if((cr%(q1))!=0, cr=lcm(o,cr); prime_fact_r=concat(prime_fact_r,q); ); ); ); return(prime_fact_r) } verify_rset(n)={ new_rset=[]; old_rset=rset(n); j=length(old_rset); cr=1; cr_max=round(log(n))^2; while(cr<cr_max, q=old_rset[j]; o=znorder(Mod(n,q)); if((cr%(q1))!=0, cr=lcm(o,cr); new_rset=concat(new_rset,q); ); j = j1 ); return(vecsort(new_rset)) } my_isprime(n)={ qlist=verify_rset(n); l=length(qlist); if(n==4, return(0) ); for(i=1,l, q=qlist[i]; U=floor(sqrt(eulerphi(q))*log(n)); if( Mod(Mod(1,n)*x+U,x^q1)^n!=x^(n%q)+U, return(0) ); ); return(1) } Correctness for algorithm relies on the truth of some of the findings here. Also note I replaced steps [2] and [5] in the algorithm demonstrated in the paper as follows: Replacement for Step [2]: r is not necessarily prime, and ord(n,r) > log(n)^2 Replacement for Step [5]: floor(sqrt(eulerphi(r))*log(n)) is floor(sqrt(eulerphi(q))*log(n)) for each prime q  r. 
20200310, 00:51  #2 
Aug 2006
13543_{8} Posts 
It seems to be rather fast. I generated a random thousanddigit number and it took only 47 seconds, compared to other ECPP implementations I had laying around: 355 seconds with Primo, 234 seconds with PARI/GP using primecert(,0), and 225 seconds with PARI/GP using isprime(,3).

20200311, 01:07  #3 
"Sam"
Nov 2016
335_{10} Posts 
I've modified the code with some print statements:
Code:
rset(n)={ prime_fact_r=[]; cr=1; cr_max=round(log(n))^2; q=2*round(log(log(n))); while(cr<cr_max, q=nextprime(q+1); if(n^2%q!=1 & n%q!=0, o=znorder(Mod(n,q)); if((cr%(q1))!=0, cr=lcm(o,cr); prime_fact_r=concat(prime_fact_r,q); ); ); ); return(prime_fact_r) } verify_rset(n)={ new_rset=[]; old_rset=rset(n); j=length(old_rset); cr=1; cr_max=round(log(n))^2; while(cr<cr_max, q=old_rset[j]; o=znorder(Mod(n,q)); if((cr%(q1))!=0, cr=lcm(o,cr); new_rset=concat(new_rset,q); ); j = j1 ); return(vecsort(new_rset)) } my_isprime(n)={ qlist=verify_rset(n); printf("Testing using q=\n"); print(qlist); l=length(qlist); if(n==4, return(0) ); for(i=1,l, q=qlist[i]; printf("Computing (x+U)^n mod(x^%d1,n)...\n",q); U=floor(sqrt(eulerphi(q))*log(n)); if( Mod(Mod(1,n)*x+U,x^q1)^n!=x^(n%q)+U, printf("%d is composite. \n",n); return(0) ); ); printf("%d is prime! \n",n); return(1) } Code:
> my_isprime(n) Testing using q= [47, 53, 59, 67, 73, 83] Computing (x+U)^n mod(x^471,n)... Computing (x+U)^n mod(x^531,n)... Computing (x+U)^n mod(x^591,n)... Computing (x+U)^n mod(x^671,n)... Computing (x+U)^n mod(x^731,n)... Computing (x+U)^n mod(x^831,n)... ... is prime! = 1 time = 3162.419 seconds Code:
> my_isprime(n) Testing using q= [3511, 3517, 3527] Computing (x+U)^n mod(x^35111,n)... *** at toplevel: my_isprime(p) *** ^ *** in function my_isprime: ...f(Mod(Mod(1,n)*x+U,x^q1)^n!=x^(n%q)+U,printf( *** ^ *** _^_: the PARI stack overflows ! current stack size: 128000000 (122.070 Mbytes) [hint] set 'parisizemax' to a nonzero value in your GPRC If anyone's is interested I will hopefully post another (heuristic of course) test, where the cyclotomic polynomials used in this test are replaced with polynomials defining cyclotomic subfields (and thus are cyclic polynomials). I've also been debating about writing a C++ version of this algorithm, but I'm not sure if it's worth the effort if what the achievement is speed and efficiency. (All suggestions and modifications to the current GP code are welcome!) Last fiddled with by carpetpool on 20200311 at 01:09 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PRP vs LL speed comparison and probabilities  JuanTutors  Software  6  20190727 03:15 
Comparison of NFS tools  CRGreathouse  Factoring  3  20180205 14:55 
APRCL implementations comparison  ldesnogu  Computer Science & Computational Number Theory  11  20151028 12:54 
Comparison Page Not Working  wblipp  Operation Billion Digits  0  20121124 06:33 
PFGW vs LLR comparison discussion  henryzz  Conjectures 'R Us  37  20100219 07:42 