mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-10-11, 17:22   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default 17 or Bust

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-10-11, 18:10   #2
VJS
 
VJS's Avatar
 
Dec 2004

1001010112 Posts
Default

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

Last fiddled with by VJS on 2005-10-11 at 18:13
VJS is offline   Reply With Quote
Old 2005-10-11, 18:21   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-10-11, 19:03   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·13·53 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2005-10-11, 20:54   #5
Joe O
 
Joe O's Avatar
 
Aug 2002

3×52×7 Posts
Default

Quote:
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 is offline   Reply With Quote
Old 2005-10-11, 21:10   #6
Joe O
 
Joe O's Avatar
 
Aug 2002

52510 Posts
Default

Quote:
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 is offline   Reply With Quote
Old 2005-10-11, 21:39   #7
Joe O
 
Joe O's Avatar
 
Aug 2002

3×52×7 Posts
Default

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....
Joe O is offline   Reply With Quote
Old 2005-10-11, 21:42   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

21358 Posts
Default

Quote:
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.


Quote:
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?
philmoore is offline   Reply With Quote
Old 2005-10-11, 23:48   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·13·53 Posts
Default Fast multiple k sieving

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. )
R. Gerbicz is offline   Reply With Quote
Old 2005-10-12, 02:42   #10
Joe O
 
Joe O's Avatar
 
Aug 2002

3·52·7 Posts
Default

Quote:
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.

Last fiddled with by Joe O on 2005-10-12 at 02:48
Joe O is offline   Reply With Quote
Old 2005-10-12, 04:03   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fourteen or Bust, or ECM attack on C300+ XYYXF XYYXF Project 25 2016-11-29 22:54
Seventeen or Bust drive philmoore Lounge 6 2014-05-26 23:10
17 or bust - get restarted Jud McCranie PrimeNet 3 2014-04-27 04:25
Five or Bust hhh Lounge 1 2008-10-10 15:26
Seventeen or Bust found a prime! Mystwalker Math 5 2005-01-04 17:00

All times are UTC. The time now is 19:14.

Tue Aug 11 19:14:35 UTC 2020 up 25 days, 15:01, 2 users, load averages: 1.48, 1.62, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.