Program:        AFACTOR2
Author:         Rob Gaebler
Date:           3/22/03
Includes:       AFACTOR2        70 bytes        BASIC launcher program
                ZFACTOR2        1523 bytes      ASM main program
                ZASMLOAD        224 bytes       ASM utility program


AFACTOR2 is an assembly program for the TI-83 that finds all the prime factors
of a positive integer.  Run program AFACTOR2 from the home screen, SOS or
ASHELL.  At the prompt, enter a number to be factored.

AFACTOR2 was built for speed.  It is much faster than any other factoring
program for any TI-8x calculator (other than the TI-89).  A typical factoring
program for the TI-83 takes more than an hour to factor 10000000019 (the
smallest 11-digit prime), AFACTOR (the second-fastest factoring program for the
TI-83) takes about 2 minutes, and AFACTOR2 takes a mere 8 seconds.

Other features of AFACTOR2 include the following:

-->     Displays prime factors as it finds them.  Displays the factor multiple
        times if a power greater than 1 is a factor.

-->     When done factoring the number, displays the factors in a two-column
        matrix with prime factors on the left and their powers on the right.  For
        example, if you enter 1960, AFACTOR2 will display the matrix
        [[2 3]
         [5 1]
         [7 2]]
        which simply means that the prime factorization is 1960 = 2x2x2x5x7x7.

-->     Can be interrupted in the middle of factoring.  Press the [Del] key to
        interrupt and exit the program.  If any factors were found already,
        displays them in a matrix.  Returns to SOS or ASHELL if you used one of
        them.

-->     Pauses after completing the factorization or quitting.  This is helpful
        if you used SOS or ASHELL.

-->     Correctly factors any number up to 20000000000000 (that has 14 digits).
        Numbers greater than that may be factored incorrectly due to the
        limitations of the TI-83.

-->     Uses only the variables X, Y, and matrix [A].

-->     Handles bad input (not a positive integer) gracefully, and does not crash
        your calculator.

-->     Has no known bugs.


WARNING: If you run AFACTOR2 from SOS, DO NOT exit by pressing [ON] or
[2nd][QUIT] or [2nd][OFF] while AFACTOR2 is prompting you for a number or
pausing.  Due to a flaw in SOS, this can cause almost 800 bytes to leak from
your calculator's memory.  To recover the lost memory, you must reset your
calculator.  This is not a problem if you start AFACTOR2 from the home screen
or ASHELL.



HISTORY
-------
AFACTOR2 is the culmination of over 3 years of my creating faster and faster
factoring programs for the TI-83.  It is my factoring masterpiece.  In January
1999, I released ABIGSIV ("A Big Sieve"), at the time the fastest factoring
program for TI calculators.  Since then, PRIMEC has been written for
the TI-83, TI-83+, and TI-86, PRMASM85 has been written for the TI-85 and
TI-86, and PRIME has been written for the TI-83+.  In June
1999, I started teaching myself z80 assembly so I could write faster factoring
programs than were possible with BASIC.  In March 2000, I released AFACTOR,
which remained the fastest factoring program for 15 months.  (I updated AFACTOR
in January 2001.)  After I finished AFACTOR, I started work on AFACTOR2, using
a new, faster algorithm that I found in Donald Knuth's The Art of Computer
Programming, Vol. 2.  I intended to create a program that could factor numbers
up to 100 digits long, but eventually changed my mind.  Finally, in August
2001, I finished AFACTOR2, likely my final factoring program.  In January 2002,
I made a few minor improvements to increase its speed and decrease its size.  I
also ported AFACTOR and AFACTOR2 to the TI-83 Plus for the first time.  In March
2003, Anthony Cutler notified me that AFACTOR2 had a bug.  It incorrectly said
that some large composite numbers were prime.  For example, 99999997=1297x77101,
but AFACTOR2 said that 99999997 was prime.  I then released an updated version
with the bug fixed.  I apologize to everyone who used my program in the
meantime.

AFACTOR2 is 1593 bytes, while AFACTOR is only 340 bytes.  AFACTOR is just as
fast as AFACTOR2 for numbers less than 1000000.  For larger numbers, AFACTOR2
can be as much as 15 times faster than AFACTOR.  If you only intend to factor
small numbers, AFACTOR is your best choice.



THE MATHEMATICS OF AFACTOR2
---------------------------
All factoring programs for the TI-83 that I have seen search for factors of the
input N by dividing N by each potential factor F to see if N/F is an integer.
I will call this method "trial division."  This method is very simple, but it
is slow because so many numbers must be tested as potential factors.  This
procedure can be sped up considerably by using the fact that only prime numbers
from 2 to sqrt(N) have to be tested.  To use this fact in a program, we need
modular arithmetic.  

We can use the first D primes 2, 3, 5, 7, ... as moduli.  First we test each of
them as factors.  Now we only have to test potential factors if they are not
divisible by any of the moduli 2, 3, 5, 7, ....  Both ABIGSIV and PRIMEC use
this method with 4 moduli, and AFACTOR uses this method with 17 moduli.

AFACTOR2 combines this trial division method with a much faster, more
sophisticated method explained in The Art Of Computer Programming, Vol. 2.
This method relies on the fact that if N has a factor F, then F = X-Y and N/F =
X+Y for some positive integers X and Y (assuming N is odd).  Thus N =
(X-Y)(X+Y) = X^2-Y^2.  To use this fact most effectively, we first use the
trial division method described above to test all potential factors up to an
arbitrary bound B between 1 and sqrt(N).  We then search for an integer X
between sqrt(N) and 1/2(B+N/B) such that X^2-N is a perfect square, namely Y^2.
This gives us the factorization N =(X-Y)(X+Y).  The only possible glitch is if
X-Y or X+Y is not prime.  To remedy this problem, we could factor both X-Y and
X+Y; but then we might have to factor their factors, and so on.  A much simpler
remedy, which AFACTOR2 uses, is to use trial division to check for all factors
up to at least the cube root of N.  This ensures that N has at most two prime
factors, so we don't have to factor X-Y and X+Y.

I call the method that searches for a solution to N = X^2-Y^2 the "quadratic
residue sieve" method, because we can use properties of quadratic residues to
increase its speed by decreasing the number of values of X we have to test.
The "quadratic residues" mod M are the integers from 0 to M-1 that are
congruent to perfect squares mod M.  For example, let M = 6.  0^2 = 0 (mod 6),
1^2 = 1 (mod 6), 2^2 = 4 (mod 6), 3^2 = 9 = 3 (mod 6), 4^2 = 16 = 4 (mod 6),
and 5^2 = 25 = 1 (mod 6).  Thus the quadratic residues mod 6 are 0, 1, 3, and
4, but not 2 or 5.  For a prime M, only about M/2 numbers are quadratic
residues mod M.

So how are these quadratic residues helpful?  X^2 and Y^2 must both be
congruent to quadratic residues for any modulus M.  Since Y^2 = X^2-N, X^2-N
must also be congruent to a quadratic residue for any modulus M.  For any given
M, we can easily make a table of the quadratic residues mod M.  Given N, we
also make a table of the values of X (mod M) such that X^2-N is a quadratic
residue mod M.  This cuts approximately in half the number of values of X that
we have to test.  The happy news is that different prime moduli work
independently of each other, so if we use two prime moduli M1 and M2, we only
have to test 1 of every 4 values of X.  If we use 20 prime moduli M1, ..., M20,
we only need to test 1 of every 2^20 values of X.  It is possible to only need
to test 1 or even 0 values of X total.  The sad news is that the more moduli we
use, the more time it takes the program to do the other stuff besides testing
X, so we can't make the program arbitrarily fast.  AFACTOR2 uses 12 moduli,
because any more or less would make it slower.

That's essentially the method AFACTOR2 uses to factor numbers.  AFACTOR2 uses a
couple of tricks to be even faster, such as using some composite moduli, and
testing 8 values of X simultaneously.  Many more, much faster factoring methods
exist, some of which are described in The Art of Computer Programming, Vol. 2.
However, I consider AFACTOR2 my final factoring program for the TI-83.




On a more personal note, I am 21 years old, Christian, red-headed, a junior
at Harvey Mudd College in Claremont, CA, the oldest of 7 children in my family,
very interested in mathematics, and I wrote AFACTOR2 because I wanted to.  You
can email me with questions, comments, or suggestions at rgaebler@hmc.edu.  I
always enjoy hearing from people who have noticed my programs, and I welcome
suggestions for improving my programs.