Any Software for Sieved Trial Factoring in Other Bases?

[wblipp]

Is there any software the does this or could be easily modified to do this?

In the thread Finding Factors of Cunningham-like 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?

[axn]

srsieve (http://geocities.com/g_w_reynolds/srsieve/) can handle these forms. Although it is optimised for multple-k n-range 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.

[wblipp]

Originally Posted by axn1

srsieve (http://geocities.com/g_w_reynolds/srsieve/) can handle these forms. Although it is optimised for multple-k n-range 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.

The site says:
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^31099802339-1. 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.

[ET_]

Originally Posted by wblipp

The site says:
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^31099802339-1. 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.

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

[wblipp]

Originally Posted by ET_

I actually have no hint on how decrease the number of candidates with efficient modulo algorithms.

I could be wrong, but I think the "modulo algorithms" work at cross purposes to the "simultaneous factoring" aspect. For example, with Mersenne numbers, I think the factors eliminated are potential factors of 2^n+1, so if we are looking for factors of 2^(2n)-1 we skip the "modulo algorithm" stage and then must test every factor found to determine which primitive part it belongs to.

Since I posted this, there has been discussion of trial factoring over on the "cunningham-like thread"

[alpertron]

Originally Posted by wblipp

I could be wrong, but I think the "modulo algorithms" work at cross purposes to the "simultaneous factoring" aspect. For example, with Mersenne numbers, I think the factors eliminated are potential factors of 2^n+1, so if we are looking for factors of 2^(2n)-1 we skip the "modulo algorithm" stage and then must test every factor found to determine which primitive part it belongs to.

Since I posted this, there has been discussion of trial factoring over on the "cunningham-like thread"

I think that Luigi wants to know how to eliminate half of the potential factors using the quadratic reciprocity law for prime bases different from 2. Am I right?

[ET_]

Originally Posted by alpertron

I think that Luigi wants to know how to eliminate half of the potential factors using the quadratic reciprocity law for prime bases different from 2. Am I right?

You are right!

I read something about it on the thread pointed by William, but still need some help...

Luigi

[wblipp]

Originally Posted by alpertron

I think that Luigi wants to know how to eliminate half of the potential factors using the quadratic reciprocity law for prime bases different from 2. Am I right?

I also think that is what Luigi wanted to know.

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 not-necessarily-primitve 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 not-necessarily-primitve factors?

William

[alpertron]

Originally Posted by wblipp

I also think that is what Luigi wanted to know.

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 not-necessarily-primitve 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 not-necessarily-primitve factors?

William

The trick works when the exponent is odd. In this case it does not matter if the factors are primitive or not.

[geoff]

Originally Posted by ET_

Hi William!
- For Mersennes I only take care of those "16 mod 120" factors (or 1 or 7 mod 8)

For prime p to divide a^n-1 it must be that a^n=1 (mod p). If n is odd, n=2m+1 say, then a*(a^m)^2=1 (mod p). Thus a = (1/a^m)^2 (mod p), and so a is a quadratic residue wrt p. So when n is odd, for each potential prime factor p, you only need test those which have Legendre(a,p)=1.

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^n-1 only if p=1 (mod 12) or p=11 (mod 12).

[Zeta-Flux]

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 127-130). 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,
Zeta-Flux