Featured request

[PhilF]

Originally Posted by storm5510

I have never understood the use of a random number, Sigma in this case. It seems to overly complicate the process.

With quadrillions upon quadrillions (that is a huge understatement actually) of possible ECM curves that could be run, do you have an alternative to random when it comes to picking which one to run?

[storm5510]

Originally Posted by PhilF

With quadrillions upon quadrillions (that is a huge understatement actually) of possible ECM curves that could be run, do you have an alternative to random when it comes to picking which one to run?

No, I do not. I wish there was another way. A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender. At the time, I remember someone writing, "A factor will be found using SNFS." If a person takes it out into decimal form, it is 385 digits long, if I remember correctly. As far as I know, none of the YAFU functions can handle something that large. As the same time, other programs would say this is too small. All of us will simply have to carry on with what is available now.

[PhilF]

Originally Posted by storm5510

No, I do not. I wish there was another way. A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender. At the time, I remember someone writing, "A factor will be found using SNFS." If a person takes it out into decimal form, it is 385 digits long, if I remember correctly. As far as I know, none of the YAFU functions can handle something that large. As the same time, other programs would say this is too small. All of us will simply have to carry on with what is available now.

That is true. But I recall someone else wrote "M1277 will never be factored".

It is easy to lose perspective of how large the numbers we are dealing with really are. We talk about a 385 digit number like it is just a number, when the total number of atoms in the entire universe is only 70 or 80 digits. That puts it somewhere between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion

No, I have never heard of a vigintillion until now either.

[VBCurtis]

Originally Posted by storm5510

A lot of people spent a lot of time running ECM's on M1277. In the end, everyone had to surrender.

Who says we surrendered? A typical estimate (not very accurate at this size) for ECM depth to run in pretesting before SNFS is 0.21 * digits. 0.21 * 385 is just over 80 digits. So, ECM curves at the 80 digits level should be run before we move to SNFS. As far as I know, we're not done with the 75-digit level yet, so we are maybe 10-15% of the way done with ECM on this number.

Some very rough numbers:
Let's say we've done t73 worth of ECM. The nth digit worth of ECM has a 1/n chance to find a factor, so going from 73 digits to 80 digits has, say, 8-9% chance to find a factor.

Before we get to t80 worth of ECM, someone will more precisely calculate the "right" amount of ECM to do. The SNFS job itself can be run with current software (and a cluster to solve the matrix); it is perhaps 4-8x tougher than RSA-240, the largest GNFS job known to be solved.

[storm5510]

Originally Posted by VBCurtis

Who says we surrendered?

Surrendered? The last time I looked at it on PrimeNet. The amount of submitted work had dropped off a lot.

Forgive me for my ignorance: T73?

[VBCurtis]

Tnn = digit level to which ECM has been performed. e.g. T50 is shorthand for saying the standard number of curves have been performed at the 50-digit level (B1 = 43M, with the exact number of curves depending on B2 choice).

There are conversions available to convert from other B1 choices, usually via the GMP-ECM -v flag, which tells you how many curves at your chosen B1/B2 it would take to complete T50 or T55 or whatever.

Common use is to only report in 5-digit increments, e.g. T65 or T70; I used T73 as a non-standard way to say "half a T75", while also saying that we've run enough curves to expect to find 71 or 72 digit factors (with "expect" far from "sure we would have found").

Speaking in generalities, it takes about 6x as much work to complete the 5-digit-higher T-level. So, T50 is about 6x longer than T45, likewise T80 is about 6x longer than T75.

Edit: as for surrender, Ryan does more work than the rest of us put together; primenet showing a slowdown may just mean he moved on to other candidates. I interpret "surrender" as "gave up", while the reality is that many folks remain interested and may continue ECM in 2020.

Edit2: I typo'ed, and should have said T73 expects to find factors 73 digits or smaller. That is, after a T70 has been completed, one would expect that half a T75 would find "most" 71 72 73 digit factors (as well as nearly any <71 digit factors that the T70 missed).

[storm5510]

Originally Posted by VBCurtis

...Edit2: I typo'ed, and should have said T73 expects to find factors 73 digits or smaller. That is, after a T70 has been completed, one would expect that half a T75 would find "most" 71 72 73 digit factors (as well as nearly any <71 digit factors that the T70 missed).

I got it. Thanks! PhilF did a lot of work as well using GMP-ECM by running stage one with Prime95.

M1277 was factored to 2^67, I believe. None of the current programs will run an exponent this small, except for Prime95 and GMP-ECM. Prime95 says to run ECM.

Someone in the past ran a huge P-1 test. The lower bound was 13 digits long.

[LaurV]

Originally Posted by storm5510

M1277 was factored

Man, you gave me palpitations...

[WraithX]

Can we add a group of options to yafu that will stop factoring early if certain conditions are met?
I'm thinking about the case where someone may be factoring a bunch of numbers, searching for something like smooth numbers or brilliant numbers.

The options I think would be helpful are:

-stoplt n : Stop after finding a factor with Less than n digits
-stople n : Stop after finding a factor with Less than or Equal to n digits
-stopeq n : Stop after finding a factor with n digits
-stopge n : Stop after finding a factor with Greater than or Equal to n digits
-stopgt n : Stop after finding a factor with Greater than n digits
-stopbase b : Base to use for stopXY options (default 10, range: 2 <= b <= 62)
  ie: the bases supported by "mpz_get_str"

If a factoring step is really fast and finds multiple factors in a fraction of a second (like trial div),
I don't think it would be needed to "stop after literally finding one factor" that meets a stop condition.
I think it would be ok to check factors as they become known to the main thread.
Does this sound like something that would be easy to add to yafu?

[bsquared]

Originally Posted by WraithX

Can we add a group of options to yafu that will stop factoring early if certain conditions are met?
I'm thinking about the case where someone may be factoring a bunch of numbers, searching for something like smooth numbers or brilliant numbers.

The options I think would be helpful are:

-stoplt n : Stop after finding a factor with Less than n digits
-stople n : Stop after finding a factor with Less than or Equal to n digits
-stopeq n : Stop after finding a factor with n digits
-stopge n : Stop after finding a factor with Greater than or Equal to n digits
-stopgt n : Stop after finding a factor with Greater than n digits
-stopbase b : Base to use for stopXY options (default 10, range: 2 <= b <= 62)
  ie: the bases supported by "mpz_get_str"

If a factoring step is really fast and finds multiple factors in a fraction of a second (like trial div),
I don't think it would be needed to "stop after literally finding one factor" that meets a stop condition.
I think it would be ok to check factors as they become known to the main thread.
Does this sound like something that would be easy to add to yafu?

Yeah that should be pretty straightforward, actually. But it will be a little while until I can get to it.

[Tyler Busby]

Originally Posted by WraithX

Can we add a group of options to yafu that will stop factoring early if certain conditions are met?
I'm thinking about the case where someone may be factoring a bunch of numbers, searching for something like smooth numbers or brilliant numbers.

The options I think would be helpful are:

-stoplt n : Stop after finding a factor with Less than n digits
-stople n : Stop after finding a factor with Less than or Equal to n digits
-stopeq n : Stop after finding a factor with n digits
-stopge n : Stop after finding a factor with Greater than or Equal to n digits
-stopgt n : Stop after finding a factor with Greater than n digits
-stopbase b : Base to use for stopXY options (default 10, range: 2 <= b <= 62)
  ie: the bases supported by "mpz_get_str"

If a factoring step is really fast and finds multiple factors in a fraction of a second (like trial div),
I don't think it would be needed to "stop after literally finding one factor" that meets a stop condition.
I think it would be ok to check factors as they become known to the main thread.
Does this sound like something that would be easy to add to yafu?

To piggyback off this, it would be helpful (for me) to also have an argument for "stop after finding k factors" and/or a function in the scripting language for "iskalmostprime(n, k)" that would stop factoring a number after k factors had been found (or after k-1 factors and a composite test on the remainder). YAFU is uniquely the fastest and most complete program for semi-prime/k-almost prime testing, but funny enough doesn't actually explicitly support it.

I wrote a python script to do trial division and prime testing for a given n to detect k-almost primes, but after needing to implement pollard's rho and starting to think about adding ecm, I figured it might be easier/faster to just wrap the yafu process and read the factor.log (after trial div etc failed), rather than reinventing the wheel. But parsing the log for factors and running my own prime tests for the remaining numbers (and killing the process and whatnot) is a little messy if it can be avoided by first party support.