1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – DanaJ Jun 29 '16 at 20:13
  • $\begingroup$ @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. $\endgroup$ – almagest Jun 29 '16 at 21:51
  • $\begingroup$ @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. $\endgroup$ – DanaJ Jun 30 '16 at 2:19
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ +1 @ccorn Many thanks. Sorry for the delay in responding. $\endgroup$ – almagest Jun 29 '16 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$ – DanaJ Jun 29 '16 at 20:19
  • $\begingroup$ @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. $\endgroup$ – almagest Jul 2 '16 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.