Wheel factorization: Efficient? - Page 43

3.14159 · 2010-08-06, 18:16

I did the factor work, and the factorization is complete! This qualifies for third place in the factor work department.

Data:

Code:

08/06/10 12:51:44 v1.18  starting SIQS on c95: 32174438273843079981142915951736520108605272417142076547338510339651236088951473095688773110437
08/06/10 12:51:44 v1.18  random seeds: 0, 4115476484
08/06/10 12:51:45 v1.18  ==== sieve params ====
08/06/10 12:51:45 v1.18  n = 96 digits, 317 bits
08/06/10 12:51:45 v1.18  factor base: 83220 primes (max prime = 2255009)
08/06/10 12:51:45 v1.18  single large prime cutoff: 293151170 (130 * pmax)
08/06/10 12:51:45 v1.18  double large prime range from 44 to 51 bits
08/06/10 12:51:45 v1.18  double large prime cutoff: 1740864372327309
08/06/10 12:51:45 v1.18  allocating 14 large prime slices of factor base
08/06/10 12:51:45 v1.18  buckets hold 1024 elements
08/06/10 12:51:45 v1.18  sieve interval: 26 blocks of size 32768
08/06/10 12:51:45 v1.18  polynomial A has ~ 12 factors
08/06/10 12:51:45 v1.18  using multiplier of 5
08/06/10 12:51:45 v1.18  using small prime variation correction of 19 bits
08/06/10 12:51:45 v1.18  using SSE2 for trial division and x128 sieve scanning
08/06/10 12:51:45 v1.18  trial factoring cutoff at 97 bits
08/06/10 12:51:45 v1.18  ==== sieving started ( 4 threads) ====
08/06/10 13:56:01 v1.18  trial division touched 88813950 sieve locations out of 226219880087552
08/06/10 13:56:01 v1.18  83402 relations found: 20674 full + 62728 from 1151241 partial, using 132763132 polys (1015 A polys)
08/06/10 13:56:01 v1.18  on average, sieving found 0.01 rels/poly and 303.88 rels/sec
08/06/10 13:56:01 v1.18  trial division touched 88813950 sieve locations out of 226219880087552
08/06/10 13:56:01 v1.18  ==== post processing stage (msieve-1.38) ====
08/06/10 13:56:02 v1.18  begin with 1171915 relations
08/06/10 13:56:02 v1.18  reduce to 214997 relations in 11 passes
08/06/10 13:56:14 v1.18  recovered 214997 relations
08/06/10 13:56:14 v1.18  recovered 194301 polynomials
08/06/10 13:56:14 v1.18  attempting to build 83402 cycles
08/06/10 13:56:15 v1.18  found 83402 cycles in 6 passes
08/06/10 13:56:15 v1.18  distribution of cycle lengths:
08/06/10 13:56:15 v1.18     length 1 : 20674
08/06/10 13:56:15 v1.18     length 2 : 14825
08/06/10 13:56:15 v1.18     length 3 : 13975
08/06/10 13:56:15 v1.18     length 4 : 11413
08/06/10 13:56:15 v1.18     length 5 : 8399
08/06/10 13:56:15 v1.18     length 6 : 5700
08/06/10 13:56:15 v1.18     length 7 : 3616
08/06/10 13:56:15 v1.18     length 9+: 4800
08/06/10 13:56:15 v1.18  largest cycle: 21 relations
08/06/10 13:56:15 v1.18  matrix is 83220 x 83402 (23.0 MB) with weight 5700471 (68.35/col)
08/06/10 13:56:15 v1.18  sparse part has weight 5700471 (68.35/col)
08/06/10 13:56:15 v1.18  filtering completed in 3 passes
08/06/10 13:56:15 v1.18  matrix is 79326 x 79390 (22.1 MB) with weight 5475398 (68.97/col)
08/06/10 13:56:15 v1.18  sparse part has weight 5475398 (68.97/col)
08/06/10 13:56:16 v1.18  saving the first 48 matrix rows for later
08/06/10 13:56:16 v1.18  matrix is 79278 x 79390 (18.9 MB) with weight 4844908 (61.03/col)
08/06/10 13:56:16 v1.18  sparse part has weight 4472001 (56.33/col)
08/06/10 13:56:16 v1.18  matrix includes 64 packed rows
08/06/10 13:56:16 v1.18  using block size 31756 for processor cache size 4096 kB
08/06/10 13:56:17 v1.18  commencing Lanczos iteration
08/06/10 13:56:17 v1.18  memory use: 15.6 MB
08/06/10 13:57:04 v1.18  lanczos halted after 1255 iterations (dim = 79277)
08/06/10 13:57:04 v1.18  recovered 17 nontrivial dependencies
08/06/10 13:57:06 v1.18  prp49 = 2350151639312606531488128176319925773812471249593
08/06/10 13:57:06 v1.18  prp47 = 13690366925963019470343985220651488583365093709
08/06/10 13:57:06 v1.18  Lanczos elapsed time = 63.9260 seconds.
08/06/10 13:57:06 v1.18  Sqrt elapsed time = 1.9650 seconds.
08/06/10 13:57:06 v1.18  SIQS elapsed time = 3922.3530 seconds.

Methods used: Self-explanatory.

P.S: Won't be able to do factor work on anything larger than about 97-105(?) digits, halfway done with factoring the c89 in the sequence.
Done with factoring the c89, but shortly afterwards, my fun ended. Back to sieving for the prime search!

I'm left with this cofactor:

Code:

8199152352981332514772255157657319674377134862589922476252241838563243745027066773349596897319872230040055056371526888680809022286295759946081821435323930525369553827027273932535753135066156554984730990311332203906286801272598511814119001961 (241 digits)

3.14159 · 2010-08-06, 21:22

Sieved up to 5.9 * 10¹² for k * 2⁸⁵⁶⁷⁸⁰ + 1. Screenshot can be seen here

Also: Any recommended factor work that is feasible?

Mathew · 2010-08-06, 21:55

Quote:

Originally Posted by 3.14159

I work as an individual when it comes to prime searching.

Of course you mean

1) After the people who came up with the formulas and

2) After the people who wrote programs

Since this is the crackpot thread I have to ask.

3.14159 · 2010-08-06, 23:03

Quote:

Originally Posted by Mathew Steine

Of course you mean

1) After the people who came up with the formulas and

2) After the people who wrote programs

Since this is the crackpot thread I have to ask.

I merely do not work in co-op projects. I never claimed any credit for the programs/formulas of others, if this is what you're implying. You fling meaningless accusations at me for little or no reason. Added to the ignore list for trolling.

3.14159 · 2010-08-06, 23:17

I think I'm going to continue sieving until I reach the 10-20 trillion range, or perhaps further.. A 257920-digit prime isn't something that's easily found.

axn · 2010-08-06, 23:26

Quote:

Originally Posted by 3.14159

A 257920-digit prime isn't something that's easily found.

True. A sum total of only 700 known primes > that size. It indeed requires non trivial effort to find one.

However, this is where a fixed-k (variable-n) approach has the advantage. There, every composite test means that the next try will be for a much bigger prime.

3.14159 · 2010-08-06, 23:44

Quote:

Originally Posted by axn

True. A sum total of only 700 known primes > that size. It indeed requires non trivial effort to find one.

It would be 700th place? Excellent!

Quote:

Originally Posted by axn

However, this is where a fixed-k (variable-n) approach has the advantage. There, every composite test means that the next try will be for a much bigger prime.

Right, but the probability of it being prime also rapidly shrinks. This is why I prefer the constant exponent search, because the probability remains constant, and I know when to expect a prime.

The tradeoff is either speed or probability.

A varied n-search offers faster testing, but vanishing probabilities of finding a prime.
A fixed n-search offers slow testing, but increases the odds of success after sieving.

It boils down to whether one prefers speed or odds. P.S: I have 13⁴ candidates left as of now, out of 750000.

CRGreathouse · 2010-08-07, 00:40

Quote:

Originally Posted by 3.14159

Right, but the probability of it being prime also rapidly shrinks.

Rapidly?

Even if he had to sieve through a million candidates, the chance that a given candidate would be prime (after a fixed level of sieving) would only decrease to (1/log(1e300006))/(1/log(1e300000)) = 300000/300006 ≈ 99.998% of the chance at the beginning of the range.

3.14159 · 2010-08-07, 01:10

Quote:

Originally Posted by CRGreathouse

Even if he had to sieve through a million candidates, the chance that a given candidate would be prime (after a fixed level of sieving) would only decrease to (1/log(1e300006))/(1/log(1e300000)) = 300000/300006 ≈ 99.998% of the chance at the beginning of the range.

For a variable n-range of one million?

Also: I lost 100 GB of memory. I lost everything concerning the collection of primes.. I had worked on that random primes list for about a year.. It was about 1/3 of a megabyte of data, too.. I think I had about 3000-5000 primes saved there, including all of my personal records' full decimal expansions. I think I remember part of what I collected, and what digit ranges I had collected.. Luckily, part of that prime collection file is also in PFGW's diary.

CRGreathouse · 2010-08-07, 01:21

Quote:

Originally Posted by 3.14159

For a variable n-range of one million?

Sure. Do the calculation yourself, if you like. I used a starting size of 300,000 digits since that's where axn is working.

kar_bon · 2010-08-07, 01:28

I've made some stats the last years here in the forum. This is the next one:

Using pictures only in this thread:
- ORLY Owl: 12 times (11 times from the-one-and-only 3.14159)
- OMG Cat: 4 times (all from same)
- some other pictures: (out of contest)

Now thats's a remarkable record!

2010-08-06, 21:22	#464
3.14159 May 2010 Prime hunting commission. 3220₈ Posts	Sieved up to 5.9 * 10¹² for k * 2⁸⁵⁶⁷⁸⁰ + 1. Screenshot can be seen here Also: Any recommended factor work that is feasible? Last fiddled with by 3.14159 on 2010-08-06 at 21:27

2010-08-06, 23:17	#467
3.14159 May 2010 Prime hunting commission. 2⁴×3×5×7 Posts	I think I'm going to continue sieving until I reach the 10-20 trillion range, or perhaps further.. A 257920-digit prime isn't something that's easily found. Last fiddled with by 3.14159 on 2010-08-06 at 23:17

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Wheel Factorization	a1call	Factoring	11	2017-06-19 14:04
Efficient Test	paulunderwood	Computer Science & Computational Number Theory	5	2017-06-09 14:02
LL tests more credit-efficient than P-1?	ixfd64	Software	3	2011-02-20 16:24
A Wheel	storm5510	Puzzles	7	2010-06-25 10:29
Most efficient way to LL	hj47	Software	11	2009-01-29 00:45

2010-08-07, 01:28	#473
kar_bon Mar 2006 Germany 2²·727 Posts	I've made some stats the last years here in the forum. This is the next one: Using pictures only in this thread: - ORLY Owl: 12 times (11 times from the-one-and-only 3.14159) - OMG Cat: 4 times (all from same) - some other pictures: (out of contest) Now thats's a remarkable record!