mersenneforum.org Comparison to ECPP?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-03-08, 01:05 #1 carpetpool     "Sam" Nov 2016 5×67 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 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.
 2020-03-10, 00:51 #2 CRGreathouse     Aug 2006 10111011000112 Posts 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).
 2020-03-11, 01:07 #3 carpetpool     "Sam" Nov 2016 1010011112 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 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

 Similar Threads Thread Thread Starter Forum Replies Last Post JuanTutors Software 6 2019-07-27 03:15 CRGreathouse Factoring 3 2018-02-05 14:55 ldesnogu Computer Science & Computational Number Theory 11 2015-10-28 12:54 wblipp Operation Billion Digits 0 2012-11-24 06:33 henryzz Conjectures 'R Us 37 2010-02-19 07:42

All times are UTC. The time now is 00:58.

Tue Jan 31 00:58:17 UTC 2023 up 165 days, 22:26, 1 user, load averages: 0.82, 1.04, 1.00