A basic math question

iconized · 2012-01-28, 20:26

I am looking into the math behind PSP-PRP and other prime number finding projects. It is obvious that a lot of test candidates already have been eliminated. It's easy enough to figure out that all numbers dividable by 3 or 5 can easily be eliminated. Then in the past this project also did some sieve and eliminated even more test candidates.

Beyond that, are there more smart tricks that for example can easily exclude other numbers? Sorry in advance if this has been documented somewhere already, but it is hard to find stuff here on Mersenneforum.

petrw1 · 2012-01-28, 21:01

Quote:

Originally Posted by iconized

I am looking into the math behind PSP-PRP and other prime number finding projects. It is obvious that a lot of test candidates already have been eliminated. It's easy enough to figure out that all numbers dividable by 3 or 5 can easily be eliminated. Then in the past this project also did some sieve and eliminated even more test candidates.

Beyond that, are there more smart tricks that for example can easily exclude other numbers? Sorry in advance if this has been documented somewhere already, but it is hard to find stuff here on Mersenneforum.

Did you look here?
http://www.mersenne.org/various/math.php

Mini-Geek · 2012-02-03, 00:01

There are various algebraic factorizations (applicable to some bases/k's, anyway; I'm not sure if PSP in particular benefits from them) that can eliminate numbers that don't have any small factors. An example of something like that are Aurifeuillian factorizations. While Aurifeuillian factorizations aren't useful for prime searching (they are useful for factoring), that's just an example.

2012-01-28, 20:26	#1
iconized Apr 2010 Netherlands 17 Posts	A basic math question I am looking into the math behind PSP-PRP and other prime number finding projects. It is obvious that a lot of test candidates already have been eliminated. It's easy enough to figure out that all numbers dividable by 3 or 5 can easily be eliminated. Then in the past this project also did some sieve and eliminated even more test candidates. Beyond that, are there more smart tricks that for example can easily exclude other numbers? Sorry in advance if this has been documented somewhere already, but it is hard to find stuff here on Mersenneforum. Last fiddled with by iconized on 2012-01-28 at 20:39

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Question regarding basic routines being used in Yafu.	storflyt32	YAFU	2	2015-06-29 23:25
basic question for assignment	wong8888	Information & Answers	5	2015-03-22 12:15
Very basic question about Wiedemann methods	fivemack	Math	0	2008-06-16 10:57
Basic optimisation question	fivemack	Puzzles	6	2008-04-08 13:50
Basic Question about ECM factoring?	drake2	Math	1	2006-01-12 07:40

2012-02-03, 00:01	#3
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 2×3×23×31 Posts	There are various algebraic factorizations (applicable to some bases/k's, anyway; I'm not sure if PSP in particular benefits from them) that can eliminate numbers that don't have any small factors. An example of something like that are Aurifeuillian factorizations. While Aurifeuillian factorizations aren't useful for prime searching (they are useful for factoring), that's just an example.