User directed prime testing for smallish integers (100-1000 decimal digits) I have become interested recently in

(A1) what one can do, if anything, about ~100 digit numbers with no easy factors and no access to anything but basic calculators/software that can cope with the number of digits but offer no programming facilities;
(B) what software (preferably open source) is available for "controlled testing" of 100-1000 digit numbers. By "controlled" I mean that one is in full control of exactly which tests are being applied, with a clear understanding of what conclusions can legitimately be drawn from the testing.

It may be that the answer to (A1) is "not much". In that case, I would add that I am also interested in

(A2) what is the largest number of digits for which one gets a more hopeful answer to (A1).

This interest has been prompted by several recent MSE questions which indirectly tangle (whether the OP realized it or not) with such issues.
As background, I am a reasonably competent coder (preferred language C, but can cope with most well-known languages), having written short pieces of code (rarely over 1000 loc) more or less every year since 1968 when I took my first maths courses at Cambridge University. I am a less competent user of Mathematica. There I rarely write more than 50 loc, but I typically write short snippets every day.
On the maths side, my competence is roughly equivalent to a typical math professor (US jargon, not UK jargon) - I am reasonably competent with the core undergraduate courses, but my knowledge is patchy beyond that level (a sad consequence of frittering away precious decades in finance).
Oh, I am happy to assume generalised RH - since I have spent inordinate amounts of time on the basic RH and find it hard to believe it is not true (whilst accepting that nothing is certain until you have a proof, preferably a well-distilled proof).
So this is basically a

reference request. Book references welcome. I have just ordered the apparently obvious one: David Bressoud - Factorization and Primality Testing, and I am wondering about Lasse Rempe-Gillen - Primality Testing for Beginners. Opinions on those two welcome. References to obscure, hard-to-obtain ones probably ok, because I have borrowing rights at the Cambridge math libraries. Articles, websites, brilliant guys in London, UK whom I could doorstep, concise summaries of the scene, would all be welcome :)

 A: Some quick hints:


*

*For (A1), you need to know the algorithms.
The Prime pages
provide a good start, including the underlying mathematics and
references. I recommend following those references too.

*For (A2), $100$ digits are easily handled with the right algorithms.
Primality proving for general numbers below $400$ decimal digits
takes less than half a minute, but requires sophisticated algorithms.
If you do not need a proof, strong pseudoprime tests are much faster,
easy to implement, and scale to much higher lengths.

*For (B), there is a variety of feasible approaches,
using the knowledge gained from (A1):


*

*If you want to code in C, you might want to take a look at the
GMP integer functions, particularly these and those.

*I'd however suggest something more interactive and higher-level for
experimenting. I recommend Pari/GP.
Its interpreter gp somehow feels much more accessible than Mathematica.
Many number-theoretic functions and algorithms are already built in.
It's also
quite popular here.



Happy number-crunching!
