mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2006-09-14, 04:37   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default 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 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?
wblipp is offline   Reply With Quote
Old 2006-09-14, 09:54   #2
axn
 
axn's Avatar
 
Jun 2003

2·32·269 Posts
Default

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.
axn is offline   Reply With Quote
Old 2006-09-14, 22:19   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

Quote:
Originally Posted by axn1 View Post
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.
wblipp is offline   Reply With Quote
Old 2006-09-17, 14:33   #4
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×5×479 Posts
Default

Quote:
Originally Posted by wblipp View Post
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
ET_ is offline   Reply With Quote
Old 2006-09-18, 00:48   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by ET_ View Post
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"
wblipp is offline   Reply With Quote
Old 2006-09-18, 12:56   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32×149 Posts
Default

Quote:
Originally Posted by wblipp View Post
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?
alpertron is offline   Reply With Quote
Old 2006-09-18, 13:35   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×5×479 Posts
Default

Quote:
Originally Posted by alpertron View Post
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
ET_ is offline   Reply With Quote
Old 2006-09-18, 13:43   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by alpertron View Post
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 nq±1. If you wanted not-necessarily-primitve factors of naq-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 n12q-1 might be primitive for n2q-1 or n3q+1 etc.

Am I wrong? Can you still eliminate potential factors when also looking for not-necessarily-primitve factors?

William
wblipp is offline   Reply With Quote
Old 2006-09-18, 14:27   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24758 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 nq±1. If you wanted not-necessarily-primitve factors of naq-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 n12q-1 might be primitive for n2q-1 or n3q+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.
alpertron is offline   Reply With Quote
Old 2006-09-22, 01:28   #10
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Quote:
Originally Posted by ET_ View Post
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).
geoff is offline   Reply With Quote
Old 2006-09-22, 01:53   #11
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is Trial Factoring? Unregistered Information & Answers 5 2012-08-02 03:47
Trial division software for Mersenne SPWorley Factoring 7 2009-08-16 00:23
How far to do trial factoring S485122 PrimeNet 1 2007-09-06 00:52
Trial factoring Citrix Software 7 2004-02-26 03:24
About trial factoring gbvalor Math 4 2003-05-22 02:04

All times are UTC. The time now is 08:20.

Mon Jan 18 08:20:04 UTC 2021 up 46 days, 4:31, 0 users, load averages: 2.67, 2.05, 2.00

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.