Combine sieving with SoB? - Page 5

VJS · 2005-07-14, 17:12

I'd just like to point out that there are numerous projects with significant firepower testing primes of the k*b^n(+/-)1 form.

Very generally speaking IMHO, the % computer power spent sieving for these projects is too little to late. This might change if we had a more optimized/efficient program to sieve these numbers like prime95.

If anyone has an idea/time to help or optimize the client the sieve community would greatly appreciate it.

I believe M.Klassons program is great and perhaps there is no room for improvement. But considering its version 0.42 would suggest there is room for improvement... Also proth hasn't been updated in several years so perhaps it is possible to improve it or make a 64-bit version for the future etc.

em99010pepe · 2005-07-14, 19:12

Quote:

Originally Posted by VJS

If anyone has an idea/time to help or optimize the client the sieve community would greatly appreciate it.

I can help. Please PM me. I'm sorry but must be this way.

Carlos

Citrix · 2005-07-15, 02:38

Proth_sieve or any client for macs will be useful since we can't use PRP on macs. Sow e can harness the power of macs.

Citrix

akruppa · 2005-07-17, 17:18

Quote:

Originally Posted by garo

Alex,
The person best qualified to answer that question in M. Klasson. I've sent him a PM with the URL of this thread. Hopefully, he will drop in.

Did not show up yet... ok, here is the idea.

Recall the equation for the order of powers:

ord(a^n) = ord(a) / gcd (ord(a),n)

We are looking for n so that k*2^n+1 ≡ 0 (mod p), or equivalently (assuming (k,p)=1)

2^n ≡ -1/k (mod p).

This implies ord(2^n) = ord(2)/gcd(ord(2),n) = ord(-1/k)

So we need ord(-1/k) | ord(2) or no suitable integer n exists.

Rearranging yields ord(2) / ord(-1/k) = gcd(ord(2),n)

So by setting d = ord(2) / ord(-1/k), we know that d|n and only need to check multiples of d in the giant-step-baby-step algorithm which yields a sqrt(d) speedup.

It is not necessary to compute the exact order of 2 and -1/k, you can determine the divisors below some bound B of the orders instead and check if

1. every divisor of ord(-1/k) found divides ord(2), otherwise this p can be discarded
2. choose d as the product of the (prime or prime power) divisors that divide ord(2) but not ord(-1/k)

You can use quadratic reciprocity as well to quickly weed out some candidate primes p (assumed odd): 2 is a QR mod p iff p ≡ 1,7 (mod 8), -1 is a QR iff p ≡ 1 (mod 4) and 1/k is a QR iff k is. So if 2 is a QR, you can determine the quadratic character of k mod p and check that (-1 p) * (k p) = 1. (here, (x p) is the Legendre symbol) If it isn't, this prime p can be discarded.

Testing several k in parallel will let you reuse the divisors of ord_p(2).

For larger p (not sure what the threshold may be) an index calculus method would far outperform the giant-step-baby-set method. If will be much more work to write, though.

Alex.

Citrix · 2005-07-17, 17:57

I don't completely understand your post but an example will help us understand.

akruppa · 2005-07-17, 18:51

Say, k = 4847, p = 1000003 so p-1 = 2*3*166667.

p%8 = 3, so 2 is not a quadratic residue (QR) and 2|ord(2).
p%4 = 3, so -1 is not a QR.
(k p) = -1, so k is not a QR, thus -k is a QR.

Now we know that 2 is not a square in Z/Zp but -1/k is, so if we want 2^n == -1/k, n must be even.

Since 2^((p-1)/3) != 1 (mod p), we know that 2 is not a cube (that means, 3 divides ord(2)).
Since k^((p-1)/3) != 1 (mod p), we know that -1/k is not a cube either. Now we know that 3 does not divide n, as then 2^n would be a cube and cannot equal -1/k.

Let's not bother to check 166667, the probability that either 2 or k is a 166667-th power is very small (1/166667 each).

So we know that n == 2, 4 (mod 6). Now you could use the giant-step-baby-step algorithm with giant step size close to sqrt(nmax) and divisible by 6, and the baby step size even and only check (in your code) c == 1,2 (mod 3) for matches in the hash table.

Alex

akruppa · 2005-07-17, 19:34

Turns out this idea is a special case of the Pohlig-Hellman algorithm. There are many descriptions of it on the net (i.e. here). It's quite possible that the current siever already uses it.

Alex

Citrix · 2005-07-17, 19:37

If I understand it right, I think it is implemented. I suggested something similar to Mklasson last month.
So then according to the method it would be faster to test numbers with smooth p-1?

Citrix

akruppa · 2005-07-17, 19:51

Yup.

Citrix · 2005-07-17, 22:41

Do you think it would be a good idea to sieve the smooth prime numbers first and then the non-smooth? if yes, we will have to convince Mklasson to write such a client.

Citrix

Citrix · 2005-07-18, 04:17

Alex,
I was wondering if it would be possible to run GNFS or SNFS on the PSP numbers. Well I know how the number field sieve works in general but I am not sure if it can be applied to PSP numbers and what the running time will be. Let me know if they will be of any help and if there is any software we can use for some tests.

Thanks for your effort,
Citrix

2005-07-15, 02:38	#47
Citrix Jun 2003 2×7×113 Posts	Proth_sieve or any client for macs will be useful since we can't use PRP on macs. Sow e can harness the power of macs. Citrix Last fiddled with by Citrix on 2005-07-15 at 17:28

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Line sieving vs. lattice sieving	JHansen	NFSNET Discussion	9	2010-06-09 19:25
64-bit sieving	paleseptember	Five or Bust - The Dual Sierpinski Problem	16	2009-01-25 20:26
Should a diskless node run it's own ecm program or should I combine them somehow?	jasong	GMP-ECM	1	2006-02-24 08:34
Sieving	ValerieVonck	Math	9	2005-08-05 22:31
Sieving	OmbooHankvald	Prime Sierpinski Project	4	2005-06-30 07:51

2005-07-14, 17:12	#45
VJS Dec 2004 13×23 Posts	I'd just like to point out that there are numerous projects with significant firepower testing primes of the k*b^n(+/-)1 form. Very generally speaking IMHO, the % computer power spent sieving for these projects is too little to late. This might change if we had a more optimized/efficient program to sieve these numbers like prime95. If anyone has an idea/time to help or optimize the client the sieve community would greatly appreciate it. I believe M.Klassons program is great and perhaps there is no room for improvement. But considering its version 0.42 would suggest there is room for improvement... Also proth hasn't been updated in several years so perhaps it is possible to improve it or make a 64-bit version for the future etc.

2005-07-17, 17:57	#49
Citrix Jun 2003 62E₁₆ Posts	I don't completely understand your post but an example will help us understand.

2005-07-17, 18:51	#50
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Say, k = 4847, p = 1000003 so p-1 = 23166667. p%8 = 3, so 2 is not a quadratic residue (QR) and 2\|ord(2). p%4 = 3, so -1 is not a QR. (k p) = -1, so k is not a QR, thus -k is a QR. Now we know that 2 is not a square in Z/Zp but -1/k is, so if we want 2^n == -1/k, n must be even. Since 2^((p-1)/3) != 1 (mod p), we know that 2 is not a cube (that means, 3 divides ord(2)). Since k^((p-1)/3) != 1 (mod p), we know that -1/k is not a cube either. Now we know that 3 does not divide n, as then 2^n would be a cube and cannot equal -1/k. Let's not bother to check 166667, the probability that either 2 or k is a 166667-th power is very small (1/166667 each). So we know that n == 2, 4 (mod 6). Now you could use the giant-step-baby-step algorithm with giant step size close to sqrt(nmax) and divisible by 6, and the baby step size even and only check (in your code) c == 1,2 (mod 3) for matches in the hash table. Alex

2005-07-17, 19:34	#51
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Turns out this idea is a special case of the Pohlig-Hellman algorithm. There are many descriptions of it on the net (i.e. here). It's quite possible that the current siever already uses it. Alex

2005-07-17, 19:37	#52
Citrix Jun 2003 2×7×113 Posts	If I understand it right, I think it is implemented. I suggested something similar to Mklasson last month. So then according to the method it would be faster to test numbers with smooth p-1? Citrix

2005-07-17, 19:51	#53
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	Yup.

2005-07-17, 22:41	#54
Citrix Jun 2003 11000101110₂ Posts	Do you think it would be a good idea to sieve the smooth prime numbers first and then the non-smooth? if yes, we will have to convince Mklasson to write such a client. Citrix

2005-07-18, 04:17	#55
Citrix Jun 2003 3056₈ Posts	Alex, I was wondering if it would be possible to run GNFS or SNFS on the PSP numbers. Well I know how the number field sieve works in general but I am not sure if it can be applied to PSP numbers and what the running time will be. Let me know if they will be of any help and if there is any software we can use for some tests. Thanks for your effort, Citrix