Small n factoring

**Nuri** · 02-11-2006, 04:04 PM

Thanks Msytwalker. I'll report back in acouple of weeks when I have sufficient data.

BTW, as I've already tested all of the candidates to B1=100000 B2=1000000, it's not efficiency of P-1 vs ECM. It's more like marginal efficiency of ECM vs P-1 to find the remaining factors for already easier to find ones found.

**Greenbank** · 02-16-2006, 11:11 AM

4593042024525125134486811 | 24737*2^6127+1

The 8th smallest unfactored n for k=24737.

Found using GMP-ECM 6.0.1 on an Apple Mac Mini (1.42GHz) with suggested bounds for 25 digits. It was the 6th curve out of the suggested 206!

Using B1=50000, B2=14000000, polynomial x^2, sigma=2555558430
Step 1 took 232468ms
Step 2 took 59168ms
********** Factor found in step 2: 4593042024525125134486811
Found probable prime factor of 25 digits: 4593042024525125134486811
Composite cofactor (24737*2^6127+1)/4593042024525125134486811 has 1825 digits

**Keroberts1** · 02-22-2006, 10:04 PM

New status: 25 digits 30 digits 35 digits 40 digits 45 digits

21181,1148 ok ok ok ok reserved (kroberts5)

21181,1172 ok ok ok ok reserved (kroberts5)

10223,1181 ok ok ok ok reserved (kroberts5)

21181,1268 ok ok ok ok

10223,1517 ok ok ok reserved

24737,1567 ok ok ok reserved (44.8%)

55459,1666 ok ok ok reserved

55459,1894 ok ok ok reserved (69.8%)

as long as noone has a problem with this or has started these already

**Mystwalker** · 04-26-2006, 11:57 AM

New status:

Code:

		25	30	35	40	45

21181,1148	ok	ok	ok	ok	reserved (kroberts5)
21181,1172	ok	ok	ok	ok	reserved (kroberts5)
10223,1181	ok	ok	ok	ok	reserved (kroberts5)
21181,1268	ok	ok	ok	ok
10223,1517	ok	ok	ok	ok
24737,1567	ok	ok	ok	reserved (66.0%)
55459,1666	ok	ok	ok	reserved (45.2%)
55459,1894	ok	ok	ok	ok

No new factor found so far.

**Mystwalker** · 06-04-2006, 07:17 AM

New status:

Code:

		25	30	35	40	45

21181,1148	ok	ok	ok	ok	reserved (kroberts5)
21181,1172	ok	ok	ok	ok	reserved (kroberts5)
10223,1181	ok	ok	ok	ok	reserved (kroberts5)
21181,1268	ok	ok	ok	ok
10223,1517	ok	ok	ok	ok
24737,1567	ok	ok	ok	reserved (89.5%)
55459,1666	ok	ok	ok	ok
55459,1894	ok	ok	ok	ok

Factors still refuse to be discovered.

In a week or two, the 40 digit level should be complete.

What's you status, kroberts5?

**Keroberts1** · 06-07-2006, 10:51 PM

i actually have no idea my computer got fried a month ago and i recently aquired a new system with an AMD64 and I'm still waiting ot get it running on ecm-gmp. I don't remember how to get it running though. I don't even have the program and i don't remember how to get .tar file to work. I haven't really played much with any computers since i starte the thing running a few months ago. I'm more of a point and click kind of guy. Some help though and i would be back on track in no time.

**Mystwalker** · 06-10-2006, 09:38 AM

This guide should help you.
The versions of the programs have changed to GMP 4.2.1 and ECM 6.1, though. In addition, ECM 6.1.1 will be out "soon", so maybe you want to wait. On the other hand, it's not that hard to compile a new version once you're familiar with the process...

Unfortunately, I have no AMD64-equipped PC, so I can't provide you with optimized binaries...

**Keroberts1** · 06-11-2006, 05:10 PM

ok i have it installed but what do i do when running it i selected run from the start menu and found the directory to run it from but i can't remember the format to give the inputs with. once again any help is appreciated

**Keroberts1** · 06-23-2006, 01:32 AM

qnyone all I need is the command format for calling the program I know the first is the B1 bounds thats all I'm sure about

**Mystwalker** · 06-23-2006, 02:31 PM

Sorry for my late answer - I must have overlooked your question.
It should be somewhere in this thread.
Try

echo 21181*2^^^^1148+1 | ecm.exe -c 100 -n 11e6 > result.txt

This should run 100 curves with B1=11M and the default B2 on 21181^2*1148+1.

**Keroberts1** · 06-23-2006, 06:54 PM

yeh i figured it out last night but how many curves do i need?

**Mystwalker** · 06-25-2006, 11:24 AM

When you add the "-v" parameter, you can see it. Just look at the 45 digit value.

**hhh** · 11-29-2006, 07:10 AM

I just encountered the following strange behaviour with mprime:

I put into the worktodo.ini the following line:

Pminus1=168451,2,1116,1,4294967295,4294967295,0

This should p-1 the number 168451*2^1116+1 with the maximal bounds of B1=B2=4294967295=2^32-1. (This is from PSP)

I gave mprime 300 or 400MB RAM.
The program starts factoring, but once at 100%, it immediately restarts at 0%, with the same number, without doing the GCD or what it is called.

Not enough memory? Other ideas?

H.

**vjs** · 11-29-2006, 09:27 AM

It's possible that your computer is not stable enough to compute a stage 1 for that many days in a row without error.

I'm not saying this is the case but it's one possibility.

Also you can try,

168451,2,1116,1,4294967295,1,0

I think this works as well (running stage one only).

Your other option is to break the P-1 into stages.

Not sure of the exact way to do it but...

168451,2,1116,1,1000000000,1,0

168451,2,1116,1,2000000000-1000000000,1,0
etc...

**hhh** · 11-29-2006, 01:13 PM

The whole test took only a few hours (at my surprise). It's because of the low n, I thought.
(P4, 3GHz)
H.

**hhh** · 11-30-2006, 10:15 AM

Yet the same thing with
Pminus1=168451,2,1116,1,4294967295,1,0

I had to stop it. Now 400MB were assigned for sure.

**vjs** · 11-30-2006, 06:39 PM

How many are a few hours < 10?

I think 2^991 which is roughly the same size took me something like 3 days on a 2.4G P4...

**hhh** · 12-01-2006, 01:27 PM

Yes, about 5 hours.
Today, I tried the factorisation with B1=2G, it worked, tough the GCD took 0 seconds. Then I extended to 3G, but had to leave before the end.

Normally, one gets a residue, doesn't one? It think I got none.
We'll see on monday.

**SlicerAce** · 10-15-2007, 03:30 AM

Is anyone still doing ECM factoring?

**jasong** · 10-16-2007, 09:58 PM

I'm assuming you're interested in participating, so my response to

Originally Posted by SlicerAce

Is anyone still doing ECM factoring?

is:

Who cares? If you want to get involved in ecm factoring of Sierpinski numbers, go for it.

My advice is to go to the gmp-ecm forum at http://www.mersenneforum.org/ and tell them your intentions. Or you could simply surf that sub-forum and probably be able to figure things out on your own, at which point you would come back here to get some numbers.

On second thought, your first stop should be the User Guides in the 'Information and Answers' Forum at that same website I listed.

Good luck.

**Kman1293** · 12-14-2007, 11:35 PM

There may not be much of a point to calculating the lower n values, but I still think its kinda fun to get rid of them. Anyways, I believe I may be the first person to have found a factor for 10223*2^1181+1. It came up on the 2260th curve I was calculating.

2869295942753555058435842630879466239475749080003 | 10223*2^1181+1

**sturle** · 01-06-2009, 07:03 PM

Originally Posted by SlicerAce

Is anyone still doing ECM factoring?

I have been playing a bit with gmp-ecm latey, and run a few more rounds on 24737*2^991+1.

an unreasonable amount of rounds with B1 < current levels.
ca 22000 rounds of B1=1.08e9, B2 ~ 22e12 (54558 recommended for 65 digit factors)
ca 7000 rounds of B1=2.52e9, B2 ~ 78e12 (118242 recommended for 70 digit factors)

No luck. A smallest factor with less than 60 digits is very unlikely. I will probably give up soon. This number may break with SNFS some day, but it is much to large for me.

**hhh** · 01-06-2009, 08:31 PM

Originally Posted by sturle

an unreasonable amount of rounds with B1 < current levels.

Wow. You meant B1> current levels, though, right? I thought about attacking a bit of the 55 digit level with my limited horsepower, but I will not mess with sturle, of course. Please post your progress when you are definitely fed up.

Code:

EDIT: How did you come up with your B1/B2-bounds? The readme states: 

       digits D  optimal B1   default B2           expected curves
                                                       N(B1,B2,D)
                                              -power 1         default poly
          45       11e6        3.5e10           4949             4480 [D(12)]
          50       43e6        2.4e11           8266             7553 [D(12)]
          55       11e7        7.8e11          20158            17769 [D(30)]
          60       26e7        3.2e12          47173            42017 [D(30)]
          65       85e7        1.6e13          77666            69408 [D(30)]

Yours seem way too high...

BTW, Kman1293, how many curves did you run, on which numbers? Not to duplicate work, if someone wants to continue. Did you submit your factor? n=1181 is still in the .dat file...

H.

**sturle** · 01-07-2009, 01:12 PM

Originally Posted by hhh

Wow. You meant B1> current levels, though, right?

B1 less than 1.08e9.

How did you come up with your B1/B2-bounds?

I did something like this on the particular CPU / memory combination I am mainly using:

Code:

for i in `seq 1 300`; do 
  ./ecm-time -v -inp 24737.991.inp -maxmem 4000 ${i}e7 >> timings-4g.txt
done

And similar for 8000 MiB RAM. Among the output, gmp-ecm reports the following interesting lines:

Code:

Using B1=2520000000, B2=77978684123358, polynomial Dickson(30), sigma=1683006743
dF=1048576, k=6, d=11741730, d2=19, i0=196
Expected number of curves to find a factor of n digits:
40      45      50      55      60      65      70      75      80      85
30      96      338     1303    5454    24566   118242  608303  3288378 1.9e+07
[...]
Expected time to find a factor of n digits:
40      45      50      55      60      65      70      75      80      85
18.06d  57.24d  201.29d 2.13y   8.91y   40.12y  193.09y 993.37y 5370y   30569y

I selected B1 levels and default B2 level which gave the lowest expected time to find a factor of given size. For the machines I have been using the optmal B1 is 1080000000 for 65 digit factors using up to 4 GB RAM for stage 2, and 2520000000 for 70 digit factors using up to 8 GB ram for stage 2. This test is using a modified gmp-ecm to get expected times for factors > 65 digits.

**vjs** · 01-08-2009, 11:15 PM

Sturle,

Wow you bring a tear to my eye with this one.

I tried on 24737*2^991+1 quite a bit quite a few years back now.

I'm pretty sure I ran a P-1 out to B1=B2=4G or whatever the maximum value is for B1 with version 24.???. Took quite a few days if not weeks...

Also ran quite a few ECM curves as well. Our numbers look similar except my B2 was smaller I only had 4G to work with.

Sorry can't say that I remember how many but it wasn't much.

I also ran at least 2 P+1 at high values as well.

I think your right that SNFS is probably the way to go but I don't think we are there yet with NFS.

Thread: Small n factoring

Thread Tools

Rate This Thread

Display

Posting Permissions