A while back (back in high school, actually) I programmed a program for the TI-83+ that goes through factoring numbers. I thought it would be nice if it could test to see if it's a prime number before continuing the factoring. The problem is, the calculator only has up to 13 digits of accuracy in its calculations, and can only work with numbers less than 100 digits. One of the equations I found for testing for compositeness is

(a^n - a)

a is an integer greater than or equal to 2, and n is your number you're testing. If n does not divide evenly into that number, it is not prime.

fPart((a^n - a)/n) = 0

Problem is, if I'm testing any number above 47, I'm going to get a number larger than 13 digits. If used as-is, it's completely useless to me.

Is there some way to break the calculation up so it doesn't have to use such large numbers, or is there some other method that can work, or is this just a waste of my time? Pretty much every method I saw besides trial division had a^n in it. Maybe I should work on implementing something like wheel factoring instead?

Here are the pages I was looking at:
http://primes.utm.edu/prove/index.html

And here's a very fast factorization program that I've looked at:
http://www.alpertron.com.ar/ECM.HTM

Well, at least it's fast compared to my program... many orders of magnitude faster.

Like, I enter 8979845161989798708094513 as the number to test, and it turns out to be prime. It calculates this in less than one second. If it really took 2^n, that would be a vast amount of memory taken up. There's got to be something I'm missing here.

Well, so is your computer's CPU. ^^

In any case that program uses the miller-rabin strong pseudoprime test, which is a probabalistic test. Which doesn't involve numbers quite as huge as a^n.

I think it may follow up with some sort of deterministic test though.... Like elliptic curve primality proving.

*Shrug*

For the method that you were trying to implement, you only need to know the residue of a^n mod n. You can find this without actually evaluating a^n. A fast way to do this is as follows:

1: Write n as a sum of powers of 2. This is done for you if you work in binary.

2: Evaluate a^(2^k) for each 2^k in the above sum. This can be done quickly by squaring a, reducing mod n, and repeating as needed.

3: Multiply these terms, reducing mod n after each multiplication.

The key here is that you only need to know anything about residues mod n, and the results of any calculations mod n are unchanged by replacing one integer by another representative of its equivalence class mod n, so you can reduce after every calculation to keep your numbers small.

Edit: For the record, this method of testing for pseudoprimality is still radically inefficient compared to the most sophisticated algorithms in use. The fastest that I know of is a variant of Lenstra's Elliptic Curve Algorithm. Unfortunately, if you want to code a prime tester yourself, then these algorithms are probably inaccessible, as they require a considerable amount of theoretical background to properly understand.

Thanks. I'll see what I can do with this information. I've been procrastinating on stuff so now I'm a bit busy and won't have time to test it for a little while, unfortunately.