Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Plot Truncation in RealTime3D
  • Next by Date: Re: Composition of series
  • Previous by thread: Re: How to use NMinimize with a numerical function
  • Next by thread: Re: [heur] Two independent y axes ?