20060914, 04:37  #1 
"William"
May 2003
New Haven
2^{6}×37 Posts 
Any Software for Sieved Trial Factoring in Other Bases?
Is there any software the does this or could be easily modified to do this?
In the thread Finding Factors of Cunninghamlike Numbers we are looking for large factors of Vanishing Fermat Quotients to complete this table. Some of the large cases are similar to trial factoring of Mersenne numbers but in different bases. For example, we would like two factors of 929^(2 * 31099802339)1 We know that factors of either large algebraic factor will be of the form 2k*31099802339+1 So we could sieve this form for primes and trial factor into the whole number. In general, we sometimes have cases of {base}^({small composite} * {large prime})  1 where it makes sense to sieve 2k{large prime}+1 then trial factor the whole composite. Is there a program that does this or could be easily modified to do this? 
20060914, 09:54  #2 
Jun 2003
2^{2}×5×257 Posts 
srsieve (http://geocities.com/g_w_reynolds/srsieve/) can handle these forms. Although it is optimised for multplek nrange sieveing, it can go thru a single k, single n as well. Plus you can specify if the potential factors fall in a specific residue class.

20060914, 22:19  #3  
"William"
May 2003
New Haven
2^{6}×37 Posts 
Quote:
This directory contains source code and some binaries for the srsieve program, a 'fixed k' sieve for numbers of the form k*b^n+c with fixed b, multiple fixed k,c and variable n. This sounds like a Sierpinski/Riesel type siever where you want to find values of n that make the expression prime. What I need is closer to the factor4 program used for Operation Billion Digits or the trial factoring part of Prime95. The k, b, n, c are fixed and the factors have a known form; the sieving step is merely an efficiency measure because it's easy to knock out many cases of the "known form" as clearly not prime. For example, both of these programs presently have code that finds "maybe primes" of the form 2k*31099802339+1. These programs then take the "maybe primes" and sees if they divide 2^310998023391. What I want is to find the same "maybe primes." but then see if the "maybe primes" divide a^(b*31099802339)1, where I can specify the a and b  in this particular instance I'm interested on a=929 and b=2. 

20060917, 14:33  #4  
Banned
"Luigi"
Aug 2002
Team Italia
3·1,609 Posts 
Quote:
Hi William! I can easily modify Factor4 to follow your needs. Anyway, its efficiency would be better if/whether you could give me some hints to rule out candidates that do not comply with the analysis:  For Mersennes I only take care of those "16 mod 120" factors (or 1 or 7 mod 8)  Then i check the factors primality and rule out composites While the second phase is trivial, I actually have no hint on how decrease the number of candidates with efficient modulo algorithms. Point me to some link where I can study this theory, and I'll be happy to help you. Luigi 

20060918, 00:48  #5  
"William"
May 2003
New Haven
2^{6}·37 Posts 
Quote:
Since I posted this, there has been discussion of trial factoring over on the "cunninghamlike thread" 

20060918, 12:56  #6  
Aug 2002
Buenos Aires, Argentina
2^{2}·3·5·23 Posts 
Quote:


20060918, 13:35  #7  
Banned
"Luigi"
Aug 2002
Team Italia
3·1,609 Posts 
Quote:
I read something about it on the thread pointed by William, but still need some help... Luigi 

20060918, 13:43  #8  
"William"
May 2003
New Haven
2^{6}·37 Posts 
Quote:
However, I thought that "eliminating half of the potential factors" was possible only if you were looking for primitive factors of n^{q}±1. If you wanted notnecessarilyprimitve factors of n^{aq}1 with "a" a small number such 2 or 12 or 18, I thought you needed to trial factor all of the potential factors of the form 2kq+1 because the ones that are not primitive for n^{12q}1 might be primitive for n^{2q}1 or n^{3q}+1 etc. Am I wrong? Can you still eliminate potential factors when also looking for notnecessarilyprimitve factors? William 

20060918, 14:27  #9  
Aug 2002
Buenos Aires, Argentina
2^{2}·3·5·23 Posts 
Quote:


20060922, 01:28  #10  
Mar 2003
New Zealand
13·89 Posts 
Quote:
If a is fixed, there is a way to build a list of congruence classes modulo 4a that p must be in to have Legendre symbol 1. I am still trying to work out how to do that myself for the general case (if you find an efficient algorithm then let me now), but for the specific case a=3 it happens that Legendre(3,p)=1 iff p=1 (mod 12) or p=11 (mod 12). So for odd n, p divides 3^n1 only if p=1 (mod 12) or p=11 (mod 12). 

20060922, 01:53  #11 
May 2003
3013_{8} Posts 
Maybe surprisingly (maybe not), but I had never seen this sort of trick before. So I set out to try and understand it a little more fully. I ran into a fun little theorem (which I currently don't see as particularly useful) involving odd perfect numbers, and divisibility of the "special prime" into other prime components. Since then, I've been trying to understand different cases, including the Mersenne prime factors.
So, let p and q be odd primes, with q congruent to 1 mod 4. Also suppose that q(p^a  1), where a is odd. Then there is a solution to x^4 == p mod q. This brought to my mind quartic reciprocity. So I was wondering if this sort of equation put restrictions on q (when p is fixed). It turns out that if p is also congruent to 1 mod 4, and (p/q)=1 (i.e. p is a quadratic residue modulo q) then there is a nifty "Rational biquadractic reciprocity" formula (discussed, for example, in Ireland and Rosen's "A Classical Introduction to Modern Number Theory" pages 127130). However, it doesn't seem to put simple congruence restrictions (over the integers) on q, but rather seems to depend on writing q=a^2+b^2, and using a,b. So, my questions: 1) Is this formula easily implemented? I.e. is it computationally easy to find a,b such that q=a^2+b^2? 2) Does this formula lead to significant improvements in sieving? (It seems to me that about another 1/4 of the potential factors should be disqualified in the sieve.) In the case of Mersenne primes, we take p=2, so this exact formula doesn't work, but I imagine there is some sort of analog. Is it being implemented in Prime95? 3) If we take p congruent to 3 mod 4, is there an analog? In other words, does the information that p is a quartic residue modulo q lead to new restrictions on q that do not arise from the fact that p is a quadratic residue? I know these are pretty deep questions involving algebraic number theory. But you all wanted a challenge, right? Cheers, ZetaFlux 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What is Trial Factoring?  Unregistered  Information & Answers  5  20120802 03:47 
Trial division software for Mersenne  SPWorley  Factoring  7  20090816 00:23 
How far to do trial factoring  S485122  PrimeNet  1  20070906 00:52 
Trial factoring  Citrix  Software  7  20040226 03:24 
About trial factoring  gbvalor  Math  4  20030522 02:04 