mersenneforum.org > Math Elementary Literature on probabilistic aspects of prime searching
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-03-16, 13:20 #1 hhh     Jun 2005 373 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

5·2,207 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

1011101012 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

5×2,207 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

10AE16 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

22×5×373 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

597910 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.)

 Thread Tools

 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 13:59.

Wed Dec 8 13:59:27 UTC 2021 up 138 days, 8:28, 1 user, load averages: 1.22, 1.39, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.