Number Theory Programs for the TI-92 Version 1.0 While scouring the old GRAPH-TI program archives I came across some real jewels for the TI-85; unfortunately, since the 85 could only handle relatively small integers, the number theory programs I found weren't as useful as I would have liked. When I received my 92, I set about to change that. After converting several of the 85 programs, I stumbled across an excellent package called UBASIC - an advanced version of BASIC featuring extended precision arithmetic and integers with up to 2600 digits (over 4 x as many as the 92!). I also downloaded MALM, a pack of number theoretical programs for UBASIC. I set about converting some of these as well. The programs below are the fruits of my labor. Improvements over version 0.9 (never publicly released) include: 1. isqrt(x) now uses Newton's method instead of bisection, allowing it to calculate trunc(sqrt(x)) MUCH more efficiently The improvements over version 0.5 include: 1. Fixed a bug with primlist from version 0.5; the list contained 83 twice and left out 89 2. Pollard has been slightly optimized, renamed to Rho and is now a function instead of a program, making it much more convenient. It also checks after finding a factor to see if the number/factor is a possible prime, so as to not spend time digging further if it is. The user can also specify an upper bound, allowing him to factor 'tougher numbers' 3. Includes isqrt to return trunc(sqrt(x)) 4. Programs now use sumult instead of mod(x,y,n) so that if a version of sumult comes out that supports integers both >1e300, the programs will be able to take advantage of it. I have a version like this planned, and will make it available ASAP. 5. Structured code [I know, I know.. real programmers think structured programming is a commie plot. :) ] The following programs/functions are included with v1.0: psprime(n): Returns true or false depending on whether or not 2^n=2 (mod n); if it passes, the number is probably prime -- if it doesn't, the number is composite. The first composite to pass is 341. mprime(n, a): If n is an integer <341 trillion, outputs with certainty a number's primality; if n >= ~ 341 trillion, checks to see if a number is a strong SPRP for all primes p | 1 < p < a. A VERY strong test -- if it passes through 19, the odds that your number is composite are extraordinarily small. Note that the second paramter must be <= 97 (*). modpwr(a,b,n): Returns a^b (mod n), where a^b would normally overflow or be an integer with more than 614 digits. polpm1(n,b,u): Attempts to factor n using base b (where u is the upper bound) by Pollard's p-1 method of factorization. Quite useful! rho(n, a, ub): Attempts to factor n by Pollard's Rho method into numbers that may or may not be prime. Make 'a' larger or smaller if n grows larger or smaller, respectively. For numbers around 9-10 digits, a good 'a' is about 10. The variable ub contains the upper bound, which may have to be adjusted depending on how difficult a number is to factor. Try 1000 for a starting value; bigger values will enable you to factor 'tougher' numbers, but will take more time. isqrt(n) : Returns trunc(sqrt(n)) by getting the first 14 or so digits by int(sqrt(n)) and then extracting the remaining digits by Newton's method. MUCH faster than the original algorithm using bisection. hprime() : Front end/help for psprime and mprime. Other files included: sumult(a,b,n): Returns a*b (mod n) by brute force. I may implement a more elegant algorithm in the future... primlist : A list of the first 25 primes (the primes between 1 and 100). You can extend the list yourself -- a program to do so may be available in the next version. * By extending the list, you can use a larger second parameter in mprime. Note that you MUST place this group in the folder ntheory for it to work correctly! Examples (leaving off the mandatory ntheory\ before each command): rho(4900280003,10,1000) returns: "70001 * 70003" rho(28084628320459997,10,1000) returns: "28084628320459997" rho(28084628320459997,10,5000) returns: "265371653 * 1058313049" polpm1(2^64+1,100,1000) returns: "274177 * 67280421310721" mprime(2^127-1,2) returns: true Special thanks are due to Yuji Kida, author of the excellent UBASIC programming language, Donald E.G. Malm, author of a pack of terrific UBASIC number theory programs and Mark Janeba, authors of the original TI-85 programs. I'd also like to thank the people of #calc-ti for their support, friendly advice and general knowledge. If you're interested, #calc-ti is on EfNet -- irc.portal.com (6662) is one of many EfNet IRC servers. Right now I'm looking for good PDF articles on factoring algorithms (such as the ones implemented above); if you know where I can find any papers that go into detail about them (the algorithm, why it works, available implementations, etc.) on the 'Net, I'd really appreciate a note telling me where to find them. Be sure to check the official docs at . If you have any questions or suggestions, feel free to write me at paulp@televault.com [PaulP on IRC]. Thanks! - Paul Pollack