Elementary Literature on probabilistic aspects of prime searching

[hhh]

Hello folks,

I fire up my account after a long time.

Next semester, I am going to teach a seminar on probability for future teachers for primary schools and schools which go until 10th grade (Haupt- und Realschule in Germany). These future teachers know less about mathematics than one would hope, but they are motivated, and I would like to teach something that they might be able to use later, and that still has some mathematical background.

I am a probabilist, and know virtually nothing about number theory. But this not going to stop me.

A few ideas I had were

1. The prime number theorem
2. The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name
3. The probabilistic nature of the ECM
4. The estimate of the expected time/exponents projects like Seventeen or bust will take to finish

The literature should be readable with very basic undergraduate level understanding of mathematics. If in german, that would help some of them. I would rather have them do something below their potential than giving them something they cannot chew.

Any hints and comments are very much appreciated, also on different probabilistic topics.

Cheers, H.

[xilman]

Originally Posted by hhh

Hello folks,

I fire up my account after a long time.

Next semester, I am going to teach a seminar on probability for future teachers for primary schools and schools which go until 10th grade (Haupt- und Realschule in Germany). These future teachers know less about mathematics than one would hope, but they are motivated, and I would like to teach something that they might be able to use later, and that still has some mathematical background.

I am a probabilist, and know virtually nothing about number theory. But this not going to stop me.

A few ideas I had were

1. The prime number theorem
2. The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name
3. The probabilistic nature of the ECM
4. The estimate of the expected time/exponents projects like Seventeen or bust will take to finish

The literature should be readable with very basic undergraduate level understanding of mathematics. If in german, that would help some of them. I would rather have them do something below their potential than giving them something they cannot chew.

Any hints and comments are very much appreciated, also on different probabilistic topics.

Cheers, H.

Bayes Theorem and some of its possibly counter-intuitive consequences?

Nice intro at https://de.wikipedia.org/wiki/Satz_von_Bayes

[hhh]

Originally Posted by xilman

Bayes Theorem and some of its possibly counter-intuitive consequences?

Nice intro at https://de.wikipedia.org/wiki/Satz_von_Bayes

Yes, of course. I am sorry I wasn't very clear in my last sentence. What I meant was

different probabilistic topics in relation to prime numbers and number theory

[xilman]

Originally Posted by hhh

Yes, of course. I am sorry I wasn't very clear in my last sentence. What I meant was

OK. Analysis of the run time of the Pollard rho factoring algorithm.

If you're doing P-1 and ECM, you should also do P+1.

The likelihood of needing n dependencies from the linear algebra in NFS, QS, etc, to find the prime factors of N. This is trickier than it sounds. I'll explain why if it's not obvious to you.

Probability of N being p-smooth --- related to ECM as you already note, but also to sieving algorithms. Extend to case where N/P (where P is p-smooth) has a small number of factors all of which are less than q (the so-called large prime).

[Mini-Geek]

Originally Posted by hhh

A few ideas I had were

1. The prime number theorem
2. The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name
3. The probabilistic nature of the ECM
4. The estimate of the expected time/exponents projects like Seventeen or bust will take to finish

SoB/CRUS-style searches (where you search until you find a prime) are more complicated than GIMPS/NPLB-style searches, where you search the entirety of a range. E.g. in SoB you don't generally find more than one prime per k, so the expected number of primes is lower. I'd teach the latter before the former.

Also of note in this area: https://en.wikipedia.org/wiki/Poisson_distribution As one who learned much about probability through my prime searches, I can say that understanding Poisson probabilities is a major part of it: it helps make sense of the random event of finding a prime. Sorry I can't recommend specific literature for the class, I learned through online resources.

[R.D. Silverman]

Originally Posted by hhh

Hello folks,

I fire up my account after a long time.

Next semester, I am going to teach a seminar on probability for future teachers for primary schools and schools which go until 10th grade (Haupt- und Realschule in Germany). These future teachers know less about mathematics than one would hope, but they are motivated, and I would like to teach something that they might be able to use later, and that still has some mathematical background.

I am a probabilist, and know virtually nothing about number theory. But this not going to stop me.

A few ideas I had were

1. The prime number theorem
2. The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name
3. The probabilistic nature of the ECM
4. The estimate of the expected time/exponents projects like Seventeen or bust will take to finish

The literature should be readable with very basic undergraduate level understanding of mathematics. If in german, that would help some of them. I would rather have them do something below their potential than giving them something they cannot chew.

Any hints and comments are very much appreciated, also on different probabilistic topics.

Cheers, H.

Tenenbaum's book: Introduction to Analytic and Probabilistic Number Theory
may be of help. Elliott's book may help as well.

[CRGreathouse]

Originally Posted by R.D. Silverman

Tenenbaum's book: Introduction to Analytic and Probabilistic Number Theory
may be of help.

I think this is probably too hard for that level (and also not available in German AFAICT).

[Qubit]

Originally Posted by Mini-Geek

Also of note in this area: https://en.wikipedia.org/wiki/Poisson_distribution As one who learned much about probability through my prime searches, I can say that understanding Poisson probabilities is a major part of it: it helps make sense of the random event of finding a prime. Sorry I can't recommend specific literature for the class, I learned through online resources.

Hmm I was curious, so I dug up the article regarding prime numbers in the link you gave (the 1976 one by Patrick X. Gallagher) =]
(If anyone wants it, you can send me a private message.)