17 or Bust

[R.D. Silverman]

Hi,

I am not a member of the 17-or-bust effort.

When I tried to send email from their web site, it insisted that I provide
my member number.......

Does anyone have a contact email address?

I would like to discuss the technical details of their sieve procedure with them.

I hope that at the minimum, they are doing the following:

Observe that if a prime p divides k*2^n + 1, then 2^n = -1/k mod p,
whence we have 2^(n + j*phi(p)) = -1/k mod p for all j. This gives
a VERY efficient sieve procedure for eliminating a lot of candidates
without trial division... I hope that they are using this procedure, or
something similar.

[VJS]

Dr Silverman,

Seventeenorbust SoB is basically using Klassons proth sieve, so your probably better off directing specific "proth sieve" questions towards him. He may even send you the source code.

Uncertain if this is his most recent e-mail but:

mklasson (Shift-2) acm (period) organization


On another note, a collective group is currently working on a new sieving program. Some information can be obtained through the forums, however it is a work in progress and conducted mostly by e-mail.

http://www.free-dc.org/forum/forumdi...?s=&forumid=38

Here is also a more specific thread were you can download the most recent beta version if your interested.

http://www.free-dc.org/forum/showthr...threadid=10069

If you'd like to contact Joe_O you can try e-mailing factrange@yahoo.com

[akruppa]

I participated in a brief discussion of their sieving algorithm in thread http://www.mersenneforum.org/showthread.php?t=4310

In short, yes, they compute discrete logarithms and use that to sieve over exponents.

Alex

[R. Gerbicz]

They are using a baby step-giant step algorithm for sieving k multiple values. Running time of this simple version is O(sqrt(k*interval)) for 1 prime number if we are sieving k multiple values for a<n<a+interval. For speed up this you can use small prime power divisors of p-1.
I have written a very efficient speed up using this in june 2003.
You can find the description of this algoritm in my post
http://www.free-dc.org/forum/showthr...9254#post29254
Note that they are using this algorithm for multiply k sieving.

[Joe O]

Originally Posted by R. Gerbicz

They are using a baby step-giant step algorithm for sieving k multiple values. Running time of this simple version is O(sqrt(k*interval)) for 1 prime number if we are sieving k multiple values for a<n<a+interval. For speed up this you can use small prime power divisors of p-1.
I have written a very efficient speed up using this in june 2003.
You can find the description of this algoritm in my post
http://www.free-dc.org/forum/showthr...9254#post29254
Note that they are using this algorithm for multiply k sieving.

Actually "they" are using the speedups from your paper, Silver Pohlig Hellman, and various other algorithms. The Giant Steps - Baby Steps Algorithm is only used on very small cases and ranges shortened by the other speedups. We welcome all suggestions. I do very much appreciate all the techniques mentioned in Robert Gerbicz's post.

[Joe O]

Originally Posted by R.D. Silverman

Observe that if a prime p divides k*2^n + 1, then 2^n = -1/k mod p,
whence we have 2^(n + j*phi(p)) = -1/k mod p for all j.

Dr. Silverman,
What definition of phi are you using? Could you provide a proof for the above?
The definition of phi that I am most familiar with is:
phi(N) is the number of primes less than or equal to N

Now if we define o2p(p) as the order of 2 in Zp, I am familiar with the fact that 2^(n + j*o2p(p)) = -1/k mod p for all j if 2^n = -1/k mod p.
And yes this is made use of.
Also please note that 2^n = -1/k mod p gives us the requirement that for n even, -k must be a quadratic residue of p; and for n odd, -2k must be a quadratic residue of p. This also is made use of.

[Joe O]

Never mind Dr Silverman. I just realized that you were using Euler's Totient function phi(n) which is defined as the number of positive integers that are relatively prime to n (i.e., do not contain any factor in common withn) , where 1 is counted as being relatively prime to all numbers. For this function phi
phi(p) = p-1 for all prime p and yes by Fermat's Little Theorem 2^(p-1)==1 mod p for prime p, so your statement holds. Note that the order of 2 that I mentioned, is defined as the least n such that 2^n == 1 mod p. It can be shown that the order of 2 is a factor of p-1....

[philmoore]

Originally Posted by Joe O

phi(N) is the number of primes less than or equal to N

Euler's phi(N) is defined, for positive integers N, as the number of positive integers less than or equal to N which are relatively prime to N. So phi(p) = p-1.

Originally Posted by R. D. Silverman

2^n = -1/k mod p, whence we have 2^(n + j*phi(p)) = -1/k mod p for all j.

How does "all j" give us any advantage in sieving? In most cases, values of p are much larger than the values of n being sieved over. Is there any useful information beyond that 2^n = -1/k mod p?

[R. Gerbicz]

There is a really fast algorithm to find prime divisors for multiple k sieving problem. The only problem is that the memory requirement is ( very ) large for a PC. However this algorithm isn't very new:
we can find small factors of a sequence see section 20. in this excellent paper by D. J. Bernstein:
http://cr.yp.to/lineartime/multapps-20041007.pdf
using FFT for multiplication, divison and gcd.
Suppose that we have integers h(1),h(2),...,h(s) and f(1),f(2),...,f(t)
and we want to find which f(i)'s divide h(1) and so on.
Then running time of this algorithm is O(u*log(u)^3*loglog(u)), where u is the total number of input bits.
In our case:
Suppose that we have k different values in sieving and we have sieved up to p and we want to sieve a(i)*2^b+1 where i=1,2,..,k and 1<b<n.
If we have sieved up to p then there are only O(n/log(p)) numbers which are survived sieve up to n for a single k value .We've k different values and remaining numbers has got O(n) bits, so these numbers has got altogether O(k*n^2/log(p)) bits, we want to minimize the average cost for a single p prime number so the best choice is that if number of bits of h(1),h(2),...,h(s) sequence and number of bits of f(1),f(2),...,f(t) sequence is the same so:
O(k*n^2/log(p))=t*O(log(p)) // because we have sieved up to p, so we will sieve q>p values where it has got O(log(p)) bits. Solving this:
t=O(k*n^2/log(p)^2). So we are always testing t different prime numbers at once!
Input numbers has got u=O(k*n^2/log(p)) bits, but we are testing t different prime numbers at once so the average time for a single p prime number:
O(u*log(u)^3*loglog(u))/t<=
<=O(k*n^2/log(p)*log(k*n)^3*loglog(k*n))/O(k*n^2/log(p)^2)=
=O(log(p)*log(k*n)^3*loglog(k*n))=
=O(log(p)*log(n)^3*loglog(n))
( I have made some assumption to get this small formula: here k<n ).
and this is much smaller then all of other methods : those has got running time O(sqrt(k*n)) but this running time is only O(log(p)*log(n)^3*loglog(n)).
Bad news is that we need O(k*n^2*log(n)/log(p)) bits of memory to build up the binary tree for multiplications and for divisons.
We can gain O(log(n)) factor in memory cost if we lost O(log(n)) factor in speed ( don't store binary tree, just store product of h(1)*h(2)*...*h(s) then compute in every step the required number in divison/gcd routine. )

[Joe O]

Originally Posted by philmoore

Euler's phi(N) is defined, for positive integers N, as the number of positive integers less than or equal to N which are relatively prime to N. So phi(p) = p-1.

Read my follow up post where I wrote exactly this about Euler's totient function. Dr Silverman did not specify Euler's phi in his post, which is why I queried him on his definition of phi.
There are at least two contradictory definitions of phi. eg see http://www.math.utah.edu/~alfeld/math/machine.html where phi(n) is defined as the number of primes less than n or equal to n
For the sake of conciseness and accuracy a non obfuscatory person should either state that they are referring to Euler's phi and not some other definition, or simply put p-1 where they mean p-1. Would it have been so hard to write 2^(n + j*(p-1)) = -1/k mod p for all j when that is what was meant? I'm all for accuracy, conciseness and clarity in mathematics. Would this have been any less accurate, concise or clear? And yes this statement is of much more use when p is smaller. We are only sieving for n < 100M and there are very few p in the range that we are sieving that would have an order of 2 < 100M so that we would have two or more n's <= 100M ie n1 and n2 where n2 = n1+j*(p-10 for some j. If there are any other consequences of this that would help sieving, I would request that someone post them here so that we may discuss them and possibly put them to use if we have not already done so.

[philmoore]

pi(N) is usually defined as the number of primes less than or equal to N, phi(N) is not the standard notation.

Note that our postings occurred at almost the same time. I hadn't overlooked your posting, it just hadn't shown up yet.