3200 more curves at 43M completed. no factor.

[QUOTE=fivemack;178890]1800@43e6 set going over the weekend; by Monday either we'll have a factor or should start polynomial search.[/QUOTE]

[QUOTE=bsquared;178998]3200 more curves at 43M completed. no factor.[/QUOTE]

I guess it is time to start the poly selection. If Tom does indeed find a factor, we can abort.

You can use the Dickman function ρ(α) (a.k.a [URL="http://en.wikipedia.org/wiki/Dickman-de_Bruijn_function"]Dickman-de Bruijn function[/URL]) to estimate the probability that an integer N has no prime factors >N[SUP]1/α[/SUP].

You can add a correction term described in Knuth and Pardo, "Analysis of a Simple Factorization Algorithm," to reduce the error term of ρ(α). That by itself doesn't lead to better estimates for ECM, though, as ρ(α) estimates the average density of smooth numbers in [1, N], not the density of smooth numbers close to N, and that error term is just as big as the one Knuth-Pardo fix. Fortunately, the latter can be fixed too, and then you end up with reasonably good estimates.

To estimate the probability that a factor is found in stage 2, you can integrate over the stage 2 primes p to sum the probabilities that p|N and N/p is smooth. This is described, for example, in Silverman and Wagstaff, "A practical analysis of the Elliptic Curve Factoring Algorithm," but they give the relevant integral incorrectly. It is correct in Brent, "Some integer factorization algorithms using elliptic curves." The standard recommendation Crandall and Pomerance, prime numbers, it probably the best place to start reading about it.

With the Brent-Suyama extension (e.g., with f(x)=x^k or a k-th Dickman polynomial), you also sum over the probability that a p>B2 appears as a divisor among the various f(j)-f(j), divides N, and N/p is smooth.

The order of elliptic curves does not behave like a random integer, though, for example with Brent-Suyama's curve parameterization you know the order of the curve is divisible by 12. But they don't behave like integers that are a multiple of 12, either, for example the average exponent of 2 in the order is close to 10/3, not 3, the average exponent of 3 is close to 27/16, not 3/2, and average exponents of larger primes are also slightly greater than for "random" integers. All in all the order is as likely smooth as if it were smaller by a factor of about 23.4.

Similarly, for the P-1 method, the order p-1 is divisible by a prime power q^k with probability (q-1)*q^(k-1), which makes the order as likely smooth as if it were smaller by a factor of 3.41. For P+1 you can play a few tricks with the starting point to get order divisibly by 4 or 6, or favour some other small primes in the order. Estimating this isn't implemented yet in GMP-ECM.

All in all there's no simple answer. To get accurate estimates, you need to take a lot of different effects into account... it gets a bit messy. If you'd like to get into this (which I recommend, it's a [I]fun[/I] mess!) I can send you the relevant papers and give you a guided tour of the GMP-ECM rho.c code, if you like.

Alex

Guys, assuming we do end up needing to do a team sieve for this, the FTP server is, as before, open for business. This time uploads will go in the c157-relations directory.

Note that I will be out of town from late afternoon (EST) Monday, June 29 to late evening Saturday, July 4 with essentially no internet access. The FTP server doesn't really require any maintenance, so you guys should be OK to use it even while I'm not around. (That's why I figured I'd better set up the directory now, since most likely the team sieve will not begin until after I'm goine.)

If, while I'm away, you guys find a factor for the C157 and need to do a team sieve on a different number, I obviously wouldn't be around to make another directory for the next number. It's easy enough to plop a directory on the server--just log in as you normally do for an upload, and execute the command "mkdir [i]name[/i]".

Max :smile:

@Alex: Thanks.

P.S.: aborting ECM @B1=11e7 (I had to restart my laptop anyway), starting msieve poly search. (a5=5k ... 10k)

i will create a poly selection thread for the c157
edit: done

i just made a bit of a beginer mistake i copied andi47's post to the new thread and then discovered that it appeared before mine so i deleted his post(physically removing it so it dint look weird to mods)
unfortunately this deleted the thread:redface:
i will recreate it

[quote=henryzz;179015]i just made a bit of a beginer mistake i copied andi47's post to the new thread and then discovered that it appeared before mine so i deleted his post(physically removing it so it dint look weird to mods)
unfortunately this deleted the thread:redface:
i will recreate it[/quote]
Hey, wait a minute...I didn't know mods could physically remove posts. You sure about that? Because I can only soft delete stuff (in the forums where I have mod privileges, that is, not here).

[quote=mdettweiler;179016]Hey, wait a minute...I didn't know mods could physically remove posts. You sure about that? Because I can only soft delete stuff (in the forums where I have mod privileges, that is, not here).[/quote]
you have to edit and then there is a delete menu at the top which includes physically delete post
this mistake makes me realize how much power i have:smile:

Xyzzy warned the supermods that physically deleting posts is, in his words, "kinda permanent" and urged us to be cautious.

Alex

[quote=henryzz;179019]you have to edit and then there is a delete menu at the top which includes physically delete post
this mistake makes me realize how much power i have:smile:[/quote]
Huh, I had no idea I could do that all this while. I just tried it on a test post in the NPLB forum and lo and behold, it works! Previously I had only seen the choice to soft delete on the menu; it must have been changed since then.