mathcadd's profile - activity

As you can see, it's all quite complicated. I would suggest (and have suggested to myself) to look at one or two modern factorization algorithms if we are to show something of interest to our students. This appears to be a good rundown of a few relevant algorithms:

http://www.cs.columbia.edu/~rjaiswal/factoring-survey.pdf (http://www.cs.columbia.edu/~rjaiswal/...)

Looking down at the definition of ispseudoprime() we get:

"Checks whether x has no small prime divisors (up to 101 included) and is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime. Such a pseudo prime passes a Rabin-Miller test for base 2, followed by a Lucas test for the sequence (P,1), where P ≥ 3 is the smallest odd integer such that P^2 - 4 is not a square mod x."

This entry ends with the interesting statement:

"There are no known composite numbers passing the above test, although it is expected that infinitely many such numbers exist."

Continuing where tmotell left off, we can find more documentation at the following page: https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html (https://pari.math.u-bordeaux.fr/docht...)

In particular, if you go to the the definition of factor(), you are sent (for integerts) to the definition of factorint() which gives in part:

"Factors the integer n into a product of pseudoprimes (see ispseudoprime), using a combination of the Shanks SQUFOF and Pollard Rho method,... Lenstra's ECM,... and MPQS,... as well as a search for pure powers."