mersenneforum.org > Math Elementary Literature on probabilistic aspects of prime searching
 Register FAQ Search Today's Posts Mark Forums Read

 2014-03-16, 13:20 #1 hhh     Jun 2005 17516 Posts Elementary Literature on probabilistic aspects of prime searching 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 The prime number theorem The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name The probabilistic nature of the ECM 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.
2014-03-16, 15:23   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

24·5·7·19 Posts

Quote:
 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 The prime number theorem The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name The probabilistic nature of the ECM 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

Last fiddled with by xilman on 2014-03-16 at 15:25 Reason: Add url

2014-03-16, 17:17   #3
hhh

Jun 2005

373 Posts

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

Quote:
 different probabilistic topics in relation to prime numbers and number theory

2014-03-16, 17:39   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

24·5·7·19 Posts

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

2014-03-16, 20:12   #5
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts

Quote:
 Originally Posted by hhh A few ideas I had were The prime number theorem The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name The probabilistic nature of the ECM 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.

Last fiddled with by Mini-Geek on 2014-03-16 at 20:13

2014-03-17, 17:34   #6
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 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 The prime number theorem The distribution of (second-)largest factors of P-1 and its importance to the factoring process of the same name The probabilistic nature of the ECM 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.

2014-03-17, 18:19   #7
CRGreathouse

Aug 2006

32×5×7×19 Posts

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

2014-03-18, 14:37   #8
Qubit

Jan 2014

2·19 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Dale Mahalko Software 7 2015-03-21 19:55 Trilo Riesel Prime Search 33 2013-09-19 21:21 Mini-Geek Twin Prime Search 8 2011-01-30 00:18 xilman Lounge 23 2010-05-05 18:48 ltd Prime Sierpinski Project 3 2006-03-23 19:27

All times are UTC. The time now is 07:48.

Mon Apr 12 07:48:06 UTC 2021 up 4 days, 2:28, 1 user, load averages: 1.48, 2.16, 2.23