mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory > PARI/GP

Reply
 
Thread Tools
Old 2020-03-08, 01:05   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

1010011112 Posts
Post 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%(q-1))!=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%(q-1))!=0,
		cr=lcm(o,cr);
		new_rset=concat(new_rset,q);
	);
	j = j-1
);
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^q-1)^n!=x^(n%q)+U,
		return(0)
	);
);
return(1)
}
Is the test faster than ECPP and or practical for large (multi-thousand digit) numbers?

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.
carpetpool is offline   Reply With Quote
Old 2020-03-10, 00:51   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135438 Posts
Default

It seems to be rather fast. I generated a random thousand-digit 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).
CRGreathouse is offline   Reply With Quote
Old 2020-03-11, 01:07   #3
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

33510 Posts
Post

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%(q-1))!=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%(q-1))!=0,
		cr=lcm(o,cr);
		new_rset=concat(new_rset,q);
	);
	j = j-1
);
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^%d-1,n)...\n",q);
	U=floor(sqrt(eulerphi(q))*log(n));
	if( Mod(Mod(1,n)*x+U,x^q-1)^n!=x^(n%q)+U,
		printf("%d is composite. \n",n);
		return(0)
	);
);
printf("%d is prime! \n",n);
return(1)
}
I've run it on a random 5000-digit prime number and it took under an hour:

Code:
> my_isprime(n)
Testing using q=
[47, 53, 59, 67, 73, 83]
Computing (x+U)^n mod(x^47-1,n)...
Computing (x+U)^n mod(x^53-1,n)...
Computing (x+U)^n mod(x^59-1,n)...
Computing (x+U)^n mod(x^67-1,n)...
Computing (x+U)^n mod(x^73-1,n)...
Computing (x+U)^n mod(x^83-1,n)...
... is prime!
= 1
time = 3162.419 seconds
The computational aspect of it is quite simple: If the set of primes q that are used is relatively small (like what the code produced above), the test will run faster, without as much memory. The set of primes used depends on n modulo many small primes. Fortunately for most primes, the set consists of very small primes (so odds are, most inputs will work!). However, the worst case scenario appears to be when polynomials such as n-1, n+1, n^2-1, n^4-1, n^6-1, n^12-1 have "many" small prime factors. I've generated a 5000-digit number n (here) which would be one of the "worst case" scenarios for this test: n-1 is divisible by every prime from 2 to 3500, (3499#), yet the factorization is not substantial for a 33.33% factor n-1 proof. As expected:

Code:
> my_isprime(n)
Testing using q=
[3511, 3517, 3527]
Computing (x+U)^n mod(x^3511-1,n)...
  ***   at top-level: my_isprime(p)
  ***                 ^-------------
  ***   in function my_isprime: ...f(Mod(Mod(1,n)*x+U,x^q-1)^n!=x^(n%q)+U,printf(
  ***                                                       ^---------------------
  *** _^_: the PARI stack overflows !
  current stack size: 128000000 (122.070 Mbytes)
  [hint] set 'parisizemax' to a non-zero value in your GPRC
As I mentioned before, this algorithm is heuristic (relies on unproven assumptions), but it should be an indicator that this test would be practical for (most) large numbers once it or a similar test is theoretically proven to be correct. To fix the memory problem, one should use polynomials such that the degree d is dependent on only the size of the input, NOT congruences modulo small prime numbers. A simple solution would be a variant of one of the tests here (which I have yet to work out). I'd be willing to take a shot at proving some of these ideas if I had more knowledge of number theory and group theory.

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 2020-03-11 at 01:09
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PRP vs LL speed comparison and probabilities JuanTutors Software 6 2019-07-27 03:15
Comparison of NFS tools CRGreathouse Factoring 3 2018-02-05 14:55
APRCL implementations comparison ldesnogu Computer Science & Computational Number Theory 11 2015-10-28 12:54
Comparison Page Not Working wblipp Operation Billion Digits 0 2012-11-24 06:33
PFGW vs LLR comparison discussion henryzz Conjectures 'R Us 37 2010-02-19 07:42

All times are UTC. The time now is 21:36.


Tue Dec 6 21:36:09 UTC 2022 up 110 days, 19:04, 1 user, load averages: 0.72, 0.79, 0.83

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔