User directed prime testing for smallish integers (100-1000 decimal digits)

Question

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 :)

Answer 1

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!