I'll extend my database of all factors to include computed P+1 B1 and B2 values along with the existing P-1 values.
Printable View
I'll extend my database of all factors to include computed P+1 B1 and B2 values along with the existing P-1 values.
The P+1 figures are interesting.
I'm in the middle of computing the B1 and B2 values for P+1 (to go along with the B1, B2 for P-1). 1/3 of the way so far.
Both methods provide the roughly the same number of factors (where p < 2^50) and the overlap (where a specific B1,B2 would have found a factor using either method) is relatively small.
(Sticking with B2=B1*100)
228541 factors < 2^50. B1=1000 B2=100000
P-1 finds 3516
P+1 finds 3423
BOTH: 44
229376 factors < 2^50. B1=40000 B2=4000000
P-1 finds 47113
p+1 finds 45112
BOTH: 9005
However, I'm having trouble with ecm 6.0.1 which I'm using for P+1. It segfaults in step 2 whenever I use an n > 1M. Will look into this further.
More stats later when I've factored all P+1's.
One of the major problems with P+1 is the group order (from mersenne) basically there is only a 50% probablility that you actually do a P+1 and not a P-1.
What most people do is 3 curves at 3-levels higher than they would typically ecm.
Not sure why it's segfaulting for you remember there are many different ecm versions optimized for different platforms. I'm sure your using the correct one but you might just want to check for a new version.
Intersting. Got any links to where I can read up on p+1 and the group orders?
[EDIT] http://magma.maths.usyd.edu.au/magma...lp/text529.htm
Googled for it. "p+1" is not that easy to search for as google strips out the +, even when it is in double quotes.
Quoth the page: "A base x_0 is used, and not all bases will succeed: only half of the bases work (namely those where the Jacobi symbol of x_0^2 - 4 and p is -1.) Unfortunately, since p is usually not known in advance, there is no way to ensure that this holds. However, if the base is chosen randomly, there is a probability of about 1/2 that it will give a Jacobi symbol of -1 (so that the factor p would be found assuming that p + 1 is smooth enough). A rule of thumb is to run pPlus1 three times with different random bases."
Thank you for pointing me in the right direction.
As for the segfaulting, I think it's a general GMP problem. I had the same thing when implementing my own p-1 code with GMP, it kept on coring in mpz_powm(). I've compiled the whole thing myself (gmp and ecm) so there cannot be any compatability problems.
You might just want to browse the mersenneforums.org under the factoring section.
Since you have the data and bounds (presumably) you should be able to double check to see if P+1 works for a particular k/n value (i.e. get it in the first or second shot). This could prove interesting.
If so it may be worth P+1'ing all values with (??? we can probably make a guess from your 48+ bit data) ???? 20K/300K before the enter prp in addition to P-1 assuming we get enough factoring computer power.
I personally believe more people will start to factor these numbers in the future as test continue to take longer and longer.
I think the only thing we can really do is experiment, I prefer experimentation to theory.
Probably stack overflow. There is an option and/or a dll to not use the stack. Check the documentation. It's probably libgmp vs libgmpa but I'm not sure.Quote:
Originally posted by Greenbank
However, I'm having trouble with ecm 6.0.1 which I'm using
for P+1. It segfaults in step 2 whenever I use an n > 1M. Will
look into this further.
New status:
Code:25 30 35 40
21181,1148 ok ok ok ok
21181,1172 ok ok ok reserved
10223,1181 ok ok ok
21181,1268 ok ok ok
10223,1517 ok ok ok
24737,1567 ok ok ok
55459,1666 ok ok ok
55459,1894 ok ok ok reserved
New status:
Code:25 30 35 40
21181,1148 ok ok ok ok
21181,1172 ok ok ok reserved
10223,1181 ok ok ok
21181,1268 ok ok ok
10223,1517 ok ok ok
24737,1567 ok ok ok reserved (13.2%)
55459,1666 ok ok ok
55459,1894 ok ok ok reserved (32.6%)
i tried to do some curves a whileago but i was unable to do s obecause 991 required too much memory at the level itwas at. I would like ot help out with the other numbers though is there anyway someon can tell me what i need to place in different files and what command line i should use ot work on say
10223,1181 ok ok ok
for the 40 digit level
Maybe this posting gof the current thread helps.
If not, just ask or search the forum - there should be a better instruction somewhere...
For the 40 digit level, you'll need ~200 MB for optimal performance, IIRC.
ok well where r the decimal expansions of the remaining canidates and is this the correct command line to call
C:\gnu\msys\home\sKetch\ecm-6.0.1\ecmfactor.exe ecm -c 100 -n -one 11e7 < SB.txt >> SBresult.txt
it doesn't seem to work
I'd suggest using prime95 for stage1 its faster anyways...
The other thing you could do is create the decimal expansion with dario's applet.
Google ECM applet dario
I thought ECM-6.0.1 was able to take non-expanded input?
Yup, just checked. My work files have:-
METHOD=ECM; SIGMA=2568500344; B1=100000; N=10223*2^4169+1; X=...
You can check this with (finds a low B1 B2 value factor)...
# echo 33661*2^1918512+1 | ./ecm -pm1 300 400
GMP-ECM 6.0.1 [powered by GMP 4.1.4] [P-1]
Input number is 33661*2^1918512+1 (577535 digits)
No expansion required.
For Windows systems, the number probably has to be entered differently:
http://www.mersenneforum.org/showthread.php?t=4536 (especially starting from #11)
But I'd also use prime95 for stage1 (using GmpEcmHook=1 in prime.ini). That way, you don't need to do anything about the number, as it is entered into the results file.
If you use ecm only, tryQuote:
C:\gnu\msys\home\sKetch\ecm-6.0.1\ecmfactor.exe ecm -c 100 -n -one 11e7 < SB.txt >> SBresult.txt
- not ecmfactor.exeCode:echo 10223*2^^^^1181+1 | ecm.exe -n -one -c 2440 3e6 >> SBresult.txt
- maybe use 1 or 2 "^"
- on a fast PC, this should be doable in about a week
- it's faster when you use Prime95 for stage1, but more complicated (which will hopefully change in a couple of weeks)
- when you close the program, you'll only loose the current curve (approx. 5-10 minutes lost)
well nothing seems to be working right now... I'm looking to know exactly what to type in for the correct number of curves to be done for any K and N value. I want to start it directly fro mthe start menu and simply click run and enter a command line. I'm not an expert in dealing with computers so please make it simple. if someone uses AIM and wants to give me a little one on one advise it'd be appreciated but it isn't that important. After all this isn't even a productive part of the project, just a fun one. If anyone wants to assist me yo ucan send me a PM and I'll get back ot yo uwithin a day or so.
If your using windows
C:\gnu\msys\home\sKetch\ecm-6.0.1\ecmfactor.exe ecm -c 100 -n -one 11e7 < SB.txt >> SBresult.txt
almost correct
C:\gnu\msys\home\sKetch\ecm-6.0.1\ecmfactor -n -one -c 100 11e7 7e11 <SB.txt >>SBresult.txt
Where sb.txt contains the decimal expanded number, try that and see if it works.
Also your ecm file is called ecmfactor???
If you tell me what O/S, processor, ram you have I could e-mail you a complete zipped folder where all you have to do is click.
i have windows XP and a AMD athalon 2000+ with 256 MB of memory. I am planning to get more memory sticks soon. Interestingly enough i have no problem installing new hardware on my machine but for somereason i just can't friggin figure out how to d osimply things with windows. I hate microsoft.
New status:
Keroberts:Code:25 30 35 40
21181,1148 ok ok ok ok
21181,1172 ok ok ok ok
10223,1181 ok ok ok Keroberts1
21181,1268 ok ok ok reserved
10223,1517 ok ok ok
24737,1567 ok ok ok reserved (26.5%)
55459,1666 ok ok ok
55459,1894 ok ok ok reserved (66.2%)
Did you make gmp-ecm run your number?
not really i kinda gave up after i failed 50 times and never got any responses in the fourum. I mean i have sbfactor working fine and at some point in the past i was having no problem running GMPecm but i forgot waht to do adn can't find where i read how to do it. My main problem is i can't remember what to use for formatting when calling the program and i don't remember the windows syntax for calling programs from the start menu. whether i need to seperate comands with - or < or " or - . or just spaces. I also don't remember which order the commands should be in. I forgot all of this a while ago when i dropped all of my programming courses. I love the math but hate the computers. Tis a shame they seemed like they would have fun together.
Can you navigate to the directory that contains ecm.exe?
You can also use "command prompt here" (this one probably only works for WinXP SP2, but it should be available for other Windows versions as well). Just install it, then right-click on the folder in the Explorer and select the resp. command from the pop-up menu.
Now, first try something likeDoes this work?Quote:
echo 547398 | ecm.exe 100 1000
seemed to work found a factor of 2 immediatly where do i go from here?
Sorry for the late reply... :(
Now, tryThe expected behavior:Quote:
echo 10223*2^^^^1181+1 | ecm.exe -n -one -c 2440 3e6 >> SBresult.txt
- Nothing will be in the window
- a few seconds later, a file named "SBresult.exe" will appear in the directory. Its contents:
(The sigma value will be different, though...)Code:GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Input number is 10223*2^1181+1 (360 digits)
Using B1=3000000, B2=4016636513, polynomial Dickson(6), sigma=1083634601
- every now and then (depending on your PC's performance; maybe every 1 or 2 minutes), the text file should grow
If this doesn't work, try this one instead:
Quote:
echo 10223*2^^1181+1 | ecm.exe -n -one -c 2440 3e6 >> SBresult.txt
I've got itrunning nowhowlong does a single curve take? Howlong should i expect it to take on an athalon 2000+ for it to finish?
edit: nevermind answered my own question should be done in 15 days.
how much memory shouldi have to even attempt to help with the 991 factoring? I would relly love to see that one fall and it would be cool to find a record factor.
I was reviewing some old posts and i saw someone mentioning an obvious fact that there can at most be 6 5 0digit factors or 5 60 digit factors and so on for something adding up to 300 digits. This means that if there are going to be multiple 50 or 60 digit factors then perhaps fewer curves should be performed because there are likely to be more than 1 factor in the certain digit range.
Has the 50 digit range been finished? 55? I just upgraded my system's RAM to 512 MB of DDR. would this be enough ot help out? I am usually just a siever and I like ot play with P-1 but i don't find enough factors in either of these to really make me feel like I'm helping the project much so I'd just like to try something a little more interesting for a while. Does anyone know what the statistical odds of the factors being distributed i ndifferent fashions? We know that the value is not prime so the absolute worst scenerio would be two prime factors around 150 digits. This is not extremely likely though.
Would ECM work at all if the factors that are at say the 70 digit level were composed of 2 primes both of 35 digits hence that factor = P1+P2+1 ?
How often do 2 primes +1 add up to equal another prime... I believe there was a specia lname for this type of a number but i am not up to date on my number theory. I am hopping ot take a few more courses on it next semiester (have some empty blocks n my schedual) I would really love to be able ot understand a little better how exactly all of this works.
512 MB should be enough for the 50 digit level. For 55 digits, 1 GB would be good and 2 GB even better.Quote:
Originally posted by Keroberts1
how much memory shouldi have to even attempt to help with the 991 factoring? I would relly love to see that one fall and it would be cool to find a record factor.
Has the 50 digit range been finished? 55? I just upgraded my system's RAM to 512 MB of DDR. would this be enough ot help out?
The 50 digit range is still underway. I guess we're approx. half-way through, so there's still a lot of work to be done.
This is possible, but not very likely. According to [utl=http://home.earthlink.net/~elevensmooth/MathFAQ.html#NoFactors]William Lipp[/url], the probability of a factor between 10^a and 10^b is 1-a/b.Quote:
I was reviewing some old posts and i saw someone mentioning an obvious fact that there can at most be 6 5 0digit factors or 5 60 digit factors and so on for something adding up to 300 digits. This means that if there are going to be multiple 50 or 60 digit factors then perhaps fewer curves should be performed because there are likely to be more than 1 factor in the certain digit range.
This is where ECM differs from P-1/P+1 factoring. You don't need a smooth P-1/P+1 (which rely on "P_1 * P_2 * ... * P_n +/- 1", by the way).Quote:
Would ECM work at all if the factors that are at say the 70 digit level were composed of 2 primes both of 35 digits hence that factor = P1+P2+1 ?
I haven't completely figured it out myself, but I think the following is a nice (but definitely wrong) way of putting it (call it a lie - but a useful lie ;) ):
Each curve uses a random sigma value.
Just imagine that a curve tries to find a smooth P+sigma.
Again, this is not how it works, but it can be understood easily.
I was thinking that such a formula would not work atthis point because of the extensive factoring already done for this value. I believe it is more likely that there is a few factors that are just above what we are currently searching through. This would mean that fewer curves should be necessary for us to find one of those factors and hence we'd want to switch to higher bounds sooner, perhaps alot sooner. I'm planning to work out the stats tonight but i probably won't have time because ofmy workload for school. I just wish i paid more atention in stats class last year so I'd remember how to do this quickly without having to g othrough the book again. What I'd really like is a probability graph showing the likelyhood of multiple factors in the different digit ranges. it is likely that there is a range around 70 digits that is more likely to have several factors within it and would therefore require fewer curves to find a factor.
so where is the current stand of the 991 factoring effort? when i finish my current factoring range and my sieve range i would like to help. what are the neccessary bounds? How many curves are needed?
My personal opinion is that people have plowed far too much time into trying to factor this number already. Even my rubbish proth_gmp binary can PRP it in about 1/100th of a second and prove that it is composite.Quote:
Originally posted by Keroberts1
so where is the current stand of the 991 factoring effort? when i finish my current factoring range and my sieve range i would like to help. what are the neccessary bounds? How many curves are needed?
However, you are free to contribute to the project in whatever way you want. My opinions are my own ;-)
You should find this thread useful:-
http://www.free-dc.org/forum/showthr...&threadid=9595
It explains the bounds and number of curves that people have run in the past, along with a few expected execution times per curve for certain hardware, plus the bounds for different factor lengths.
Joe posted his Excel spreadsheet here.Quote:
Originally posted by Keroberts1
so where is the current stand of the 991 factoring effort? when i finish my current factoring range and my sieve range i would like to help. what are the neccessary bounds? How many curves are needed?
It's almost half a year old.
In the meantime, I did approx. 10% of the required curves, Joe probably did some more.
Thus we're at 30%+...
my computer crashed after 1490 curves for 1181 and i was hopping i coul djust start it again and finish the last 950 but I'm worried its going ot start off with the same sigma values again. How should i go about continueing this?
no everytime the simga value is chosen at random. ALso several sigma values will fit what's required for a factor if there is one.
That would be surprising for me...Quote:
Originally posted by vjs
no everytime the simga value is chosen at random.
Actually, each sigma value should be random, in the sense that it is highly unlikely to get the same value twice in such a short time.
Even if it happens, it's not that bad. That one curve is useless then, but the next curve should have a new (and unused) sigma value.
Your 1490 curves are completely valid, assuming you still have the output and/or checked that no factor has been found.
O.K. then I'm not understanding where are the sigma values of the previous curve stored or?
I know there are functions to start with a particular sigma value then incrementally increase. But I wouldn't know which sigma to start at or what increment to use.
It would make sence that if one wanted to conduct "all" of the 45-digit curves etc that there would be a minimum sigma to start with and an sigma increase etc.
They aren't stored. There are 2^32 (4294967296) possible sigma values it could pick at random.
Let's have a look at the odds.
If N=2^32 (number of possible sigma values):-
For one sigma value to be unique (which it obviously will be):
N/N = 1
For two sigma values:-
N*(N-1)/ N^2.
For three sigma values:-
N*(N-1)*(N-2) / N^3
Or: N! - (N-c)! / N^c (where c is the number of curves)
Continuing this up to 5000 sigma values (and knocking up a quick GMP program to calculate this).
The chances of picking 5000 unique sigma values is 99.70944%. So there is a 1 in 344 chance that you won't have picked 5000 unique sigma values.
either way all of the curves are completed and no factors found (where would the factor be outputted?) No fact.txt file or other new files that i can see.
Do you have the ">> SBresult.txt" at the end of your command?
If yes, all output will be there. Thus, just open it and search for "factor".
If you haven't specified an output file, then you either have to use the parameter "-one" (which stops factoring once a factor is found; nevertheless, the output is only on screen by default) or search through all screen output.
Mystwalker is correct of course...
The other option is to yet again use more switches, take the following commmand line for example
k7 -one -c 900 3e6 <991.num >>results.txt
This commandline would 900 curves and b1=3e6 (the 40-digit level) and save all the output to results.txt.
The two options of >>results.txt and >results.txt,
>results.txt this basically means write the output for the curve to a text file results.txt
>>results.txt this basically means write the output for the curve to the end of the text file results.txt
The differences are suttle but with the first case only the last curve will appear in the file the one with the factor. With the secondcase all curves are written to the file with the factor producing curve at the end.
Using >> is the better choice since you can see the progress of your ecm by checking txt file size. I think a 900 curve file is about ???88k??? when completed???
Here is the important part
-one
When using this switch the ecm program will stop once a factor is found, therefore the last curve i.e. the last curve written to the curve containing the factor.
Here is an example of what's contained in a sucessful factor using the above commmandline (note b1=11e6)
GMP-ECM 6.0 [powered by GMP 4.1.4] [ECM]
Input number is 2366206759345660958438496174396247604384804004693614461892003255335430183968544739660002801882779222 8876627301931 (113 digits)
Using B1=11000000, B2=50000000000, polynomial Dickson(12), sigma=1539336453
Step 1 took 121896ms
Step 2 took 102287ms
Using B1=11000000, B2=50000000000, polynomial Dickson(12), sigma=2897668340
Step 1 took 121628ms
Step 2 took 102263ms
Using B1=11000000, B2=50000000000, polynomial Dickson(12), sigma=1080738149
Step 1 took 121945ms
Step 2 took 102188ms
********** Factor found in step 2: 109152212865049578528408617691239
Found probable prime factor of 33 digits: 109152212865049578528408617691239
Probable prime cofactor 216780466216577989739156624879506765269560601796002467513388819212013895038704029 has 81 digits
The bolded portion is the only curve which produced a factor. IF you don't use the -one switch the factor could be buried somewhere in the file, if you use the -one and only use > only the factoring curve is written.
I think I made this more complicated than it need to be. Simply do a text search for words factor or prime or simply search for *** as mystwalker suggested.
On another note it will take quite some effort for us to find a factor for this number. It's quite possible that there are no factors less than 100 digits in size. But then again we may find a 45-digit factor for it in the next curve. We just don't know.
Correct me if I'm wrong, but I'd think that with ">", all curves of one run of the application are written to the resp. file.Quote:
Originally posted by vjs
>results.txt this basically means write the output for the curve to a text file results.txt
>>results.txt this basically means write the output for the curve to the end of the text file results.txt
The differences are suttle but with the first case only the last curve will appear in the file the one with the factor. With the secondcase all curves are written to the file with the factor producing curve at the end.
In other words, the file is only overwritten when you start gmp-ecm another time, not when another curve is calculated.
Apart from that, I completely concur with you. :)
ok well i did use -one and there were no factors at the end of the file so i guess no luck this time. What bounds should i use for 991 i am thinking i should do 10 or 20 curves just to see if i can push that one along a little more. what optional commands should i use to save memory?
B1 bounds is 44M at the moment.
For B2, it's generally sensible to use the default value when performing stage1 with gmp-ecm as well.
When you have few memory, there are 3 options:
1. use smaller B2 bounds
Curves will be completed faster and need less memory, but more are needed for a certain digit level.
For 49e9, I need upto 340MB.
2. use the parameter "-k <x>" where <x> is a number
By default, x = 4. It's basically the number of fractions the b2 "space" gets divided in.
Increasing this value saves memory, but curves take a bit longer.
Quadrupling the value halves the memory consumption.
3. use the parameter "-treefile <x>" where <x> is a name
Now, some tables are written to disk instead of stored in memory. This considerably reduces memory requirements, but of course lessens performance, but not as much as one might expect.
Mystwalker,
Hummm... > or >>
Now you have me thinking, it doesn't make sence at if you decided to run 400 curves with the > that only the first curve were reported. Since if a factor were found on the 249th curve the client would stop but you wounldn't know the factor. (Not saying your wrong but... I always thought the txt was simpley overwritten and the >> was an append?)
Well lets just agree that one shouldn't use the > but the >> option instead.
Keroberts,
Mystwalker is giving you great advise I'd stick with with his guidance.