Anyone factoring <5M? - Page 5

petrw1 · 2010-09-24, 03:00

Quote:

Originally Posted by markr

Still going! Down to somewhere in the 4.6M range now. There are some left above that that are assigned to others for ECM, but eventually they'll become available.

I'm working towards you; started at 3,000,000 about a month ago with an old PIV that is 30% more efficient below 62 bits than above....currently just passed 3,02x,xxx so don't wait up for me

alpertron · 2010-09-24, 11:57

Someone said above that ECM is a probabilistic algorithm so we are not sure whether a factor is found or not using this method. Notice that the trial division method has two drawbacks:

* It is a lot slower than ECM for the same level, especially for exponents less than 1M.

* We are not sure whether the trial factoring went ok or not. On ECM the probabilistic nature of finding factors can be fighted by running more curves, but in the case of TF the lost factor (if an error occurred in the computer running this algorithm) will never be found.

By completing ECM to the 25-digit level in all exponents less than 1M we are fairly sure that only a few factors with less than 64 bits will be missing (and a lot of prime factors of more than 64 bits will appear), that will be finally found when extending the search to the 30-digit level.

cheesehead · 2010-09-28, 07:04

Quote:

Originally Posted by alpertron

* We are not sure whether the trial factoring went ok or not.

... and we're not sure whether the ECM went okay or not. ECM code is not automatically immune to programming bugs or hardware errors.

The ECM method is not more reliable than the TF method. You're noting that multiple ECM runs decrease the chance of missing a factor, but failing to mention that multiple TF runs with independent hardware and independently developed code does the same.

Correct TF code doesn't miss any factors. Correct ECM code finds as many as predicted. There could be an error in ECM code that missed as many factors, proportionally, as the buggy TF code did, but, because of the probabilistic nature of ECM, would be harder to detect. How long would it take to detect that ECM code had a bug that was systematically missing 1/5000 (or whatever the fraction was in the TF case) of the factors that it should find?

alpertron · 2010-09-28, 11:34

Quote:

Originally Posted by cheesehead

Correct TF code doesn't miss any factors. Correct ECM code finds as many as predicted. There could be an error in ECM code that missed as many factors, proportionally, as the buggy TF code did, but, because of the probabilistic nature of ECM, would be harder to detect. How long would it take to detect that ECM code had a bug that was systematically missing 1/5000 (or whatever the fraction was in the TF case) of the factors that it should find?

I'm not talking about software errors, but about hardware errors, for instance due to overclocking or defective motherboard, memory, etc. When running a TF and a hardware problem occurs, the missing factor will never be found.

markr · 2010-09-28, 13:43

Quote:

Originally Posted by markr

Still going! Down to somewhere in the 4.6M range now. There are some left above that that are assigned to others for ECM, but eventually they'll become available.

Just started at the top of the 4.4M range. Someone cleaned up the few remaining above 4.5M regardless that they were assigned to others for ecm, or to me. Fortunately only a small duplication of effort, and PrimeNet still gave me credit.

Quote:

Originally Posted by petrw1

I'm working towards you; started at 3,000,000 about a month ago with an old PIV that is 30% more efficient below 62 bits than above....currently just passed 3,02x,xxx so don't wait up for me

Great! It will indeed be a long time before we meet, but who cares. Let's see - if it's left to my resources, 4M will be finished in April 2011, maybe. Anyone else working in this area, or thinking about it?

garo · 2010-09-28, 14:40

@markr, petrw1
Have you found any factors guys or have the ECM folks taken them all?

petrw1 · 2010-09-28, 14:58

Quote:

Originally Posted by garo

@markr, petrw1
Have you found any factors guys or have the ECM folks taken them all?

Ahhh.... that explains it; ECM. I was just about to report that something was fishy in this range because I was below they expected 1/61 or so with factors.

BUT...I am still finding some; about half of that:
551 exponents: 5 factors found or about 1/110.

petrw1 · 2010-09-28, 15:05

Quote:

Originally Posted by markr

Great! It will indeed be a long time before we meet, but who cares. Let's see - if it's left to my resources, 4M will be finished in April 2011, maybe. Anyone else working in this area, or thinking about it?

My one 2.8 Ghz PIV is doing just over 13 a day.
The entire 3M Range was just under 24,000.

So let's see: Pi-R-Squared over the Angle of the Hypotenuse; Sine; Tangent; Cosine; carry the 1; Net Present Value; ....

I get just over 5 years....like I said: "Don't wait up".
Though I am considering sneaking in a little time on a couple other PCs

gjmccrac · 2010-09-28, 15:10

Quote:

Originally Posted by markr

Anyone else working in this area, or thinking about it?

I just added 20 exponents to a Pentium II that has been doing TF-LMH.

I started at 4M. I made sure the exponents were not already assigned to anyone.

The machine should start on them in 2 days once the current TF-LMH work clears out.

Grant.

alpertron · 2010-09-28, 15:13

Notice that almost no ECM was running in the 3M range yet. I see that only 3 curves out of 280 curves (in order to complete the 25-digit range) were ran.

petrw1 · 2010-09-28, 15:21

Quote:

Originally Posted by alpertron

Notice that almost no ECM was running in the 3M range yet. I see that only 3 curves out of 280 curves (in order to complete the 25-digit range) were ran.

Is it reasonable that 3 out of 280 curves should have already found nearly half the factors in the 18 or so digit range that 2^62 factoring is looking for?

2010-09-24, 11:57	#46
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	Someone said above that ECM is a probabilistic algorithm so we are not sure whether a factor is found or not using this method. Notice that the trial division method has two drawbacks: * It is a lot slower than ECM for the same level, especially for exponents less than 1M. * We are not sure whether the trial factoring went ok or not. On ECM the probabilistic nature of finding factors can be fighted by running more curves, but in the case of TF the lost factor (if an error occurred in the computer running this algorithm) will never be found. By completing ECM to the 25-digit level in all exponents less than 1M we are fairly sure that only a few factors with less than 64 bits will be missing (and a lot of prime factors of more than 64 bits will appear), that will be finally found when extending the search to the 30-digit level.

2010-09-28, 14:40	#50
garo Aug 2002 Termonfeckin, IE 2⁴·173 Posts	@markr, petrw1 Have you found any factors guys or have the ECM folks taken them all?

2010-09-28, 15:13	#54
alpertron Aug 2002 Buenos Aires, Argentina 1,523 Posts	Notice that almost no ECM was running in the 3M range yet. I see that only 3 curves out of 280 curves (in order to complete the 25-digit range) were ran.