On Tue, Nov 16, 2010 at 2:18 AM, David Kirkby <david.kir...@onetel.net> wrote: > > On 16 November 2010 09:43, William Stein <wst...@gmail.com> wrote: > > On Tuesday, November 16, 2010, David Kirkby <david.kir...@onetel.net> wrote: > >> On 16 November 2010 06:57, William Stein <wst...@gmail.com> wrote: > > >>> It is completely clear from the documentation above Mathematica *only* > >>> uses > >>> a pseudo prime test. It says right there "gives a pseudorandom prime > >>> number > >>> in the range". > >>> William > >> > >> I was interpreting that as a prime generated by a pseudo random number > >> generator, whereas you are interpreting it as a random pseudoprime. > > > > Mathematica's documentation is misleading. > > You previously wrote it was "completely clear" ! > > > Eg, how would you > > interpret the docs for PrimeQ? > > > http://reference.wolfram.com/mathematica/ref/PrimeQ.html > > I would interpret that as Mathematica's PrimeQ[] tests with 100% > certainty if the number is prime or not.
And the next poster (Don Morrison) writes: "Mma probably uses the fast "psuedo-primality tests" in the range where they are known to be correct (less than about 2^64, though they can go higher.) After that, sieving or AKS is necessary." OK, now both of you should click on the link labeled "Implementation notes: Numerical and Related Functions" at the bottom of the page http://reference.wolfram.com/mathematica/ref/PrimeQ.html In fact, PrimeQ does not "tests with 100% certainty if the number is prime or not." The mathematica documentation is deeply misleading. They mention that Mathematica does have a "proof = True" version of PrimeQ called ProvablePrimeQ that one can optionally load. I just tried it on a 200-digit number and it took 22 seconds as compared to 3 seconds in PARI (hence Sage). I also just looked at the compiled binary "source code" of RandomPrime.mx in Mathematica. It's some sort of encrypted binary format, but all the names of functions that get called are left readable, and one sees that RandomPrime calls PrimeQ; there is no mention of ProvablePrimeQ in that file. I'm idly curious about how all of Mathematica's interpreter level source code of functions is encrypted... It is so sad that we can't just resolve questions like this once and for all by simply reading the little 17K source file for RandomPrime. I hate this aspect of Mathematica with a passion. > But I somehow expect as a number theorist you are going to tell me > that there's no publicly known algorithm to 100% prove a number is > prime at the speed Mathematica does - i.e. Mathematica's test is > almost certainly a probabilistic test, which has a finite chance of > being wrong. That's certainly true, and indeed I knew that instantly based on the size of primes being considered... But I also knew that the default primality testing in Maple and Mathematica is "proof=False", since I investigated these things when teaching elementary number theory classes over the years. > Perhaps some of these issues should be raised with Wolfram Research. I encourage you to complain about the documentation from PrimeQ. It is clearly very misleading. > > it would be good to sort out the issues I found at #10112, where I > found by some brute-force testing that pseudo_prime() hangs if fed > silly input values, rather than reporting they are silly. +1 to fixing 10112. > > Dave > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org -- William Stein Professor of Mathematics University of Washington http://wstein.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
