mod function and AKS paper
- To: mathgroup at smc.vnet.net
- Subject: [mg65368] mod function and AKS paper
- From: "Kai Gauer" <kai.g.gauer at gmail.com>
- Date: Tue, 28 Mar 2006 04:05:53 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
The celebrated "Primes is in P" paper ( http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf ) seems to call in a special-purpose version of mod at its formula (2) on page 2 (notice the 2 arguments). Is this similar to the call of the Mathematica version of Mod or PowerMod? If not, is there a way that I can write mod in terms of some Mathematica calls? Of course, I may also have not read the paper carefully enough to find this version of the mod definition. The remaining portion of the algorithm's notation on page 3 seems to make sense. Also, I've since heard that there are better guesses for the bounds, being ~ O[(ln^(6+epsilon)) p] and ~O[(ln^(4+epsilon)) p], the latter having a small probability of ambiguous return ( http://mathworld.wolfram.com/AKSPrimalityTest.html ). Which tricks in the code would one change to apply the quicker bounds of AKS-test? Apologies if this has been asked and answered in a previous thread. Thanks, Kai G. Gauer