View Single Post
Old 2010-11-03, 17:10   #5
CRGreathouse's Avatar
Aug 2006

596110 Posts

My understanding of sm88's idea: if you're factoring a number that is 5 mod 6, at least one of its prime divisors must be 5 mod 6. Can this be used to speed trial division? (This was stated only in the case of Mersenne numbers, but it seems to be more general.)

Generally, the answer seems to be "no". You could search only for primes that are 5 mod 6, but it's quite possible that all such primes are large -- greater than sqrt(n). In essence, you're trading a factor of 2 for a factor of sqrt(n) which is a losing proposition.

Example: Suppose you're factoring 15419076477348026044248723582269. There are about 1.12e14 primes below the square root of this number, so trial division will take at most this many divisions to factor the number. (In fact it will take 1.3926475881e10 divisions, since the smaller factor is 355894230031.)

But the smallest factor that is 5 mod 6 is 43324884688366413299. Now only about half the primes up to that number need be tested, but this is 4.9e17 which is not only greater than 1.4e10 but greater than 1.1e14.
CRGreathouse is offline