Yafu

[lorgix]

Originally Posted by bsquared

...because GMP-ECM's library entry point provides no mechanism for returning the B2 value actually used during a computation. I will change the screen/log output text to reflect this fact in the next release...

Does this mean that you can not change the 'gmp-ecm default'-output to the B2 actually used? If such change could be done I would find it particularly interesting when using non-standard B1.

Also, while I realize there are software more suited for tasks requiring B1>4e9; will that limit be removed?

[xilman]

Originally Posted by lorgix

Also, while I realize there are software more suited for tasks requiring B1>4e9; will that limit be removed?

I don't like to see arbitrary limits imposed by software either.

I'm interested in why you think the limit on B1 is an issue right now. Setting B1 to 4G is optimal for finding factors around 72 digits in size and each factor is expected to take 300K curves for a (1-1/e) probability of it being found on the assumption that one exists to be found. That's actually rather a lot of computation, for each curve and for each factor. There are rather few outfits who can manage that intensity of computation right now.

Personally, I would not like to see an implementation slowed down significantly so that computations which are hardly every performed become possible. The better approach, IMO, would be to have two implementations, one with the present 32-bit limitation and another which is not so limited.


Paul

[lorgix]

Originally Posted by xilman

I don't like to see arbitrary limits imposed by software either.

That made me laugh. For real.

I'm interested in why you think the limit on B1 is an issue right now. Setting B1 to 4G is optimal for finding factors around 72 digits in size and each factor is expected to take 300K curves for a (1-1/e) probability of it being found on the assumption that one exists to be found. That's actually rather a lot of computation, for each curve and for each factor. There are rather few outfits who can manage that intensity of computation right now.

It's not an issue to me. I don't have the hardware to find a record size ECM factor anyway. And if I did I wouldn't be using YAFU for that purpose.

It's mostly just the "arbitrary limit" thing.

But...

Personally, I would not like to see an implementation slowed down significantly so that computations which are hardly every performed become possible. The better approach, IMO, would be to have two implementations, one with the present 32-bit limitation and another which is not so limited.

If the rest would have to be slowed down to accommodate B1>4e9 doing so would make no sense at all. None that I can see.

I'm not nearly familiar enough with programming to understand the implications here...

On the subject; where the 73-digit factors lucky finds under 32-bit? If not, then what is the highest B1 doable at the moment?

[xilman]

Originally Posted by lorgix

On the subject; where the 73-digit factors lucky finds under 32-bit? If not, then what is the highest B1 doable at the moment?

Not particularly lucky. As I said, a B1 of around 2^32 is optimal for finding factors of about that size.


Paul

[lorgix]

So what's the next step?

Going by the pattern.... B1= 2^64 could split a 1536bit RSA key with about 2e12 curves....

I'm just gonna assume that's not actually the next step.

[bsquared]

Originally Posted by lorgix

Does this mean that you can not change the 'gmp-ecm default'-output to the B2 actually used? If such change could be done I would find it particularly interesting when using non-standard B1.

Also, while I realize there are software more suited for tasks requiring B1>4e9; will that limit be removed?

That's right, it would require a (minor) change to gmp-ecm. I could contribute this change, I suppose, but I'm not currently a developer of gmp-ecm.

As to removing the B1 limitation, its not hard to do, but it's not high on my priority list. A single curve with B1=4e9 would take 6-8 hours on a fast machine. Not many people work at that level.

[WraithX]

Hello Ben, I just downloaded Yafu and it works great! I was looking for a couple of features, but couldn't find them. Can you let me know if these features exist in some form, or if they could be implemented in future versions of yafu?

1) Set a flag to have factor() stop after finding just 1 factor
2) Somehow have factor() work on a range of numbers
maybe like: factor(10^101+x;x,1,1000),
or a new function name like factor_range(10^101+x,1,1000)
3) Set an upper limit on work to do, like tell factor to only do ecm up to B1=50K (or 250K) ie, it will still trial divide, fermat, rho, pp1, pm1, and then stop searching for a factor if it can't find one after searching through all of its recommended curves for a B1
4) Somehow have factor() append numbers to a file that it thinks is prime/prp
maybe a command line of -op <filename> or ini file value op=<filename>
5) Somehow have factor() append numbers to a file that is has factored
maybe a command line of -oc <filename> or ini file value oc=<filename>
6) Somehow have factor() append numbers to a file if it hasn't found any factors (because of #3 above)
maybe a command line of -ou <filename> or ini file value ou=<filename>
7) When outputting these numbers to files, can we output their functional forms and not their expanded decimal form?

Hmmm, that seems like a lot. If you'd like I can look at implementing some of these myself. I just looked at the source, would factor_common.c probably be the right place to make some of these changes? I don't know if I can compile all of yafu, has anyone done this with mingw-64? If I can't compile, could I post modified source here and see if it works for you? Thanks for the great program. Looking forward to see what you think of the above.

[bsquared]

Originally Posted by WraithX

Hello Ben, I just downloaded Yafu and it works great! I was looking for a couple of features, but couldn't find them. Can you let me know if these features exist in some form, or if they could be implemented in future versions of yafu?

1) Set a flag to have factor() stop after finding just 1 factor
2) Somehow have factor() work on a range of numbers
maybe like: factor(10^101+x;x,1,1000),
or a new function name like factor_range(10^101+x,1,1000)
3) Set an upper limit on work to do, like tell factor to only do ecm up to B1=50K (or 250K) ie, it will still trial divide, fermat, rho, pp1, pm1, and then stop searching for a factor if it can't find one after searching through all of its recommended curves for a B1
4) Somehow have factor() append numbers to a file that it thinks is prime/prp
maybe a command line of -op <filename> or ini file value op=<filename>
5) Somehow have factor() append numbers to a file that is has factored
maybe a command line of -oc <filename> or ini file value oc=<filename>
6) Somehow have factor() append numbers to a file if it hasn't found any factors (because of #3 above)
maybe a command line of -ou <filename> or ini file value ou=<filename>
7) When outputting these numbers to files, can we output their functional forms and not their expanded decimal form?

Thanks WraithX!

Also thanks for the requests... here are my initial reactions:
1) Yes, this should be easy.
2) I've considered things like this before, but every time I do I balk at the thought of writing a robust scripting language parser. It seems like this could be accomplished in a line of perl or two. If you or anyone else wanted to write quick "helper scripts" like this, it might be a nice thing to add to yafu's SVN repository and include in the download package.
3) This should also be easy to do, but I've been kicking around a few other ideas for making factor() much more tailorable as well. Not sure yet what direction to take.
4) - 6) This info is all accessible in factor.log, but I take it you don't want to comb through all that baggage to get what you want, which I can understand. This could also probably be accomplished with helper scripts. Anyone else have input on this?
7) I've also considered things like this before: a command line switch which causes all screen/log output to be functional form (-f), or mixed form (-m). mixed form would be functional form followed by a shortened decimal form, i.e, (123...789). Maybe it's time to implement that.

Originally Posted by WraithX

Hmmm, that seems like a lot. If you'd like I can look at implementing some of these myself. I just looked at the source, would factor_common.c probably be the right place to make some of these changes? I don't know if I can compile all of yafu, has anyone done this with mingw-64? If I can't compile, could I post modified source here and see if it works for you? Thanks for the great program. Looking forward to see what you think of the above.

command line parsing happens mostly in driver.c. factor_common.c is where the factor() function and supporting functions live. If you want to take a shot at one of these, feel free. Maybe let me know by email if so, so I can coordinate with you and/or help you navigate my morass of code.

Thanks again for your feedback!

[lorgix]

Now this isn't supposed to happen, is it?


Some really nice suggestions by WraithX, btw. All of them really.

[bsquared]

Originally Posted by lorgix

Now this isn't supposed to happen, is it?

Nope, good catch!

Fixed in source... I'll update the binaries tonight with this collection of fixes.

Thanks again,
- ben.

[bsquared]

I just updated version 1.22 binaries with fixes for several issues:

+ remove B2 cap in ecm
+ factor() now properly ignores user defined B2 flags for ecm, pp1, and pm1
+ fixed the issue seen here
+ merged in code from wraithx implementing a new switch, -one, causing factor() to stop after finding at least one factor.

cheers,
- ben.