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

• For references, Crandall and Pomerance's book is very good and quite practical. Cohen's Computational Number Theory book is also recommended for more math details. Riesel's 1994 book is a favorite of mine as well because I think he gives good succinct explanations for a number of practical algorithms. – DanaJ Jun 29 '16 at 20:13
• @DanaJ There seem to be two Cohen yellow books (Course and Advanced Topics). Which did you mean? I seem to remember looking at one of them a few years ago and thinking it was rather heavy going ... Happy to upvote if you put even brief thoughts into an answer. – almagest Jun 29 '16 at 21:51
• @almagest, Sorry! "A Course in Computational Algebraic Number Theory" is the one I use. He has a good section on a number of basic algorithms, on APR-CL and ECPP, and more. I think C&P's "Prime Numbers: A Computational Perspective" is more useful if you only had one source, but I find myself quite often looking up some detail in Cohen. I will say that there are huge chunks of the Cohen's book that I haven't looked at and may never get to. Original papers are also useful, especially (IMO) Baillie-Wagstaff 1980 "Lucas pseudoprimes", and BLS 1975. – DanaJ Jun 30 '16 at 2:19

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!

• +1 @ccorn Many thanks. Sorry for the delay in responding. – almagest Jun 29 '16 at 16:42
• Definitely agree with Pari/GP. C+GMP is a standard method for writing your own programs, but Pari/GP is great for getting stuff done, and I believe most people active in the community are quite familiar with it. – DanaJ Jun 29 '16 at 20:19
• @DanaJ Many thanks to both you and ccorn for your help on this. I have collected some material together and will try to find time to acquire at least the basics over the next few weeks. – almagest Jul 2 '16 at 5:05