mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2014-03-16, 13:20   #1
hhh
 
hhh's Avatar
 
Jun 2005

37310 Posts
Default 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
  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.
hhh is offline   Reply With Quote
Old 2014-03-16, 15:23   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,253 Posts
Default

Quote:
Originally Posted by hhh View Post
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

Last fiddled with by xilman on 2014-03-16 at 15:25 Reason: Add url
xilman is online now   Reply With Quote
Old 2014-03-16, 17:17   #3
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

Quote:
Originally Posted by xilman View Post
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
hhh is offline   Reply With Quote
Old 2014-03-16, 17:39   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,253 Posts
Default

Quote:
Originally Posted by hhh View Post
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).
xilman is online now   Reply With Quote
Old 2014-03-16, 20:12   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by hhh View Post
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.

Last fiddled with by Mini-Geek on 2014-03-16 at 20:13
Mini-Geek is offline   Reply With Quote
Old 2014-03-17, 17:34   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by hhh View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-03-17, 18:19   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2014-03-18, 14:37   #8
Qubit
 
Qubit's Avatar
 
Jan 2014

2·19 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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.)
Qubit is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
HTML5 prime number searching? Dale Mahalko Software 7 2015-03-21 19:55
Question about multi-core prime searching. Trilo Riesel Prime Search 33 2013-09-19 21:21
idea for twin prime searching Mini-Geek Twin Prime Search 8 2011-01-30 00:18
Literature xilman Lounge 23 2010-05-05 18:48
Searching for user BlueSoda (no its not a prime) ltd Prime Sierpinski Project 3 2006-03-23 19:27

All times are UTC. The time now is 18:04.

Fri Sep 25 18:04:45 UTC 2020 up 15 days, 15:15, 0 users, load averages: 1.54, 1.45, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.