20171230, 13:28  #34  
"Forget I exist"
Jul 2009
Dartmouth NS
20342_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20171230 at 13:35 

20171230, 13:36  #35  
Dec 2017
50_{10} Posts 
Quote:
yet as our mathematical knowledge increases it would be truelly wonderful to know somethig even more simple and beautiful than that ... besides that, the aks test (ignoring their very nice contribution through appropriate polynomial division for a moment) is nothing than the trivial fact that p is prime iff p divides the all binomial coefficients (p over q) with 1 < q < p ... naively spoken it's a sieve in disguise. (the terms simple and beautiful might not be defined properly, yet i believe we will know and recognize it as soon as we see it ?) Last fiddled with by guptadeva on 20171230 at 14:01 

20171231, 00:26  #36  
Aug 2006
5,987 Posts 
Quote:


20171231, 01:20  #37  
Dec 2017
2·5^{2} Posts 
Quote:
step 3 of the akstest (see attachment above) is in fact a classical sieve. the reason for aks being vastly faster than a full sieve is the existence of the parameter r in step 2, so that the sieve only has to run until min(r,n1) ... yet in the (relatively rare) case, that r>=n1 a full sieve is executed. also the step 5 is relatively slow ... the main contribution of agrawal, kayal and saxena was in fact the introduction of an appropriate polynomial division (with x^r 1) based on grouptheoretical arguments and also to proove that their algorithm is complete. Last fiddled with by guptadeva on 20171231 at 01:49 

20171231, 02:34  #38 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001101_{2} Posts 
Certainly we would want to read more about the AKS test rather than rely on that video. "the aks test [...] is nothing than the trivial fact that [...]" is what everyone thinks after watching that video, which is a disservice to the AKS paper, which the video rolls up in "well that's not quite the same" at 2:352:50.
It's like a video about the LucasLehmer test spending almost all the time explaining Wilson's Theorem, then at the end saying "and then using some fiddly bits from Lucas, Lehmer did some twiddling to make it a bit faster, but we won't show that." "yet in the (relatively rare) case, that r>=n1 a full sieve is executed." Once above tiny size numbers, r is *much* smaller than sqrt(n). The time taken in steps 14 is very small relative to step 5. "also the step 5 is relatively slow ... " Yes it is, but it's faster than trial division once past small inputs and clearly shows polynomial growth in empirical implementations. Much different than trial division. 
20171231, 02:53  #39  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
Quote:
"simple" is relative. I also assume you want "fast" added to your list of items. It's also relative, but without it there are quite a few useless choices. You can also get some not useless but not really fast tests like the BLS75 methods (partial factoring of n1 and/or n+1). They're simple, unconditional, and deterministic. They're also a lot faster than trial division. I do agree that, given the state of most programs / programmers, it'd be nice to have something else. Multiple MillerRabin tests is the height of most nonmath programs. At least adding a strong Lucas test would be nice. APRCL and ECPP do have open source libraries but certainly not many users. 

20171231, 02:56  #40  
Dec 2017
California
2^{3} Posts 
Quote:


20171231, 03:05  #41  
Dec 2017
110010_{2} Posts 
Quote:
aks.pdf to make such simplifying statements  yet sometimes simplification may improve understanding. Last fiddled with by guptadeva on 20171231 at 03:24 

20171231, 03:15  #42  
Dec 2017
2·5^{2} Posts 
Quote:
yet, honestly i'm not interested in "fast" algorithms at the moment  so which algorithms do you have in mind when when mentioning "quite a few useless choices" ? maybe they are "beautiful" ? Last fiddled with by guptadeva on 20171231 at 04:05 

20171231, 03:33  #43 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 

20171231, 05:49  #44  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
38D_{16} Posts 
Quote:
There are a lot of people posting on the internet who see that video then believe that lemma is the AKS test entirely. Sometimes with some confusion over what all the fuss was about or how it could be efficient, but sometimes just recommending people implement it to check 10 digit inputs because it is Moar Faster. Wilson's theorem is quite elegant and simple, but not fast. Similarly the statement about binomials equaling zero, which is elegant though slower than simple trial division. Trial division itself, whether naive, wheel optimized, or using primes generated with a sieve. Miller's test using either n/4 or various proven reductions is pretty straightforward (getting all the way down to 2*log^2(n) requires the GRH). Underwood collects lots of oddball formulas in his 1983 paper Formulas for Primes, most of which devolve into either Wilson's Theorem or a sieve. In practice one usually uses APRCL and/or ECPP. Typically with BPSW used as a pretest. Of course if the input is a special form with an efficient test we would use that. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Claimed proof of the ABC conjecture (Zha, 2009)  R.D. Silverman  Math  6  20190422 00:03 
Collatz Conjecture Proof  Steve One  Miscellaneous Math  21  20180308 08:18 
The Beal Conjecture Proof  Arxenar  Miscellaneous Math  1  20130907 09:59 
A proof for the Twin Prime Conjecture  Carl Fischbach  Miscellaneous Math  7  20090624 05:52 
Proof of Goldbach Conjecture  vector  Miscellaneous Math  5  20071201 14:43 