Question

siegert81 · 2011-08-01, 22:54

In the factoring programs, when a factor is discovered, did the program actually perform a full division and evaluate the result as having no remainder, or is some sort of divisibility test used?

In other words, is there a divisibility test that gives a "yes or no" answer to the question "is N divisible by p?"

For the purposes of finding factors, we don't really need all of the information a full division provides. All we need is the binary "yes or no" result. Exact quotients and remainders are useless.

wblipp · 2011-08-02, 04:40

"is N divisible by p" is answered by finding the answer to "does N mod p = 0." N mod p is also known as the remainder. In many cases it can be calculated much more quickly than "doing a division" by using the rules of modular arithmetic. In particular,

(a+b) mod p = ((a mod p) + (b mod p)) mod p.
(ab mod p) = ((a mod p) * (b mod p)) mod p

The last one is especially useful for large powers, which you calculate through successive squarings or sometimes even cleverer "ladders."

S485122 · 2011-08-02, 04:46

Look on the GIMPS site. In the menu on the left you will find an item "About GIMPS", when you click on the + on the left of the line it it will expand. Then you will find a line "The Math". The method GIMPS uses for trial factoring is explained there.

Jacob

2011-08-01, 22:54	#1
siegert81 Dec 2010 2×37 Posts	Question In the factoring programs, when a factor is discovered, did the program actually perform a full division and evaluate the result as having no remainder, or is some sort of divisibility test used? In other words, is there a divisibility test that gives a "yes or no" answer to the question "is N divisible by p?" For the purposes of finding factors, we don't really need all of the information a full division provides. All we need is the binary "yes or no" result. Exact quotients and remainders are useless.

2011-08-02, 04:40	#2
wblipp "William" May 2003 New Haven 2·7·13² Posts	"is N divisible by p" is answered by finding the answer to "does N mod p = 0." N mod p is also known as the remainder. In many cases it can be calculated much more quickly than "doing a division" by using the rules of modular arithmetic. In particular, (a+b) mod p = ((a mod p) + (b mod p)) mod p. (ab mod p) = ((a mod p) * (b mod p)) mod p The last one is especially useful for large powers, which you calculate through successive squarings or sometimes even cleverer "ladders." Last fiddled with by wblipp on 2011-08-02 at 04:42

2011-08-02, 04:46	#3
S485122 Sep 2006 Brussels, Belgium 13·131 Posts	Look on the GIMPS site. In the menu on the left you will find an item "About GIMPS", when you click on the + on the left of the line it it will expand. Then you will find a line "The Math". The method GIMPS uses for trial factoring is explained there. Jacob