Head, meet wall

[fivemack]

I have just spent about a week trying to factor an aliquot-series number

4002575656069920142792412245296211078849750530528040085185518889509565302305248202324101206943842421375710626210947

by GNFS. All my square roots gave 1*N, I sieved more, rebuilt the matrix, and all my square roots still gave 1*N.

This is because 4002575656069920142792412245296211078849750530528040085185518889509565302305248202324101206943842421375710626210947 is in fact a prime number.

Well, at least it's not a subtle and hard-to-track-down bug in ggnfs ...

[xilman]

Originally Posted by fivemack

I have just spent about a week trying to factor an aliquot-series number

4002575656069920142792412245296211078849750530528040085185518889509565302305248202324101206943842421375710626210947

by GNFS. All my square roots gave 1*N, I sieved more, rebuilt the matrix, and all my square roots still gave 1*N.

This is because 4002575656069920142792412245296211078849750530528040085185518889509565302305248202324101206943842421375710626210947 is in fact a prime number.

Well, at least it's not a subtle and hard-to-track-down bug in ggnfs ...

OTOH, a test could very easily be built into ggnfs to see whether it is being asked to factor a prime power.


Paul

[akruppa]

So does the Aliquot sequence terminate with a prime? What was the starting value?

alex

[fivemack]

Originally Posted by akruppa

So does the Aliquot sequence terminate with a prime? What was the starting value?
alex

Nothing so exciting ... I pulled out factors less than 10^5 by trial division, then ran gmp-ecm (which doesn't by default check primality on its input) for a while, then ggnfs. The idea that a randomish 115-digit number might be prime hadn't crossed my mind, and if it had I'd have expected the tools to pick it up.

I've switched to running gmp-ecm on the full numbers ... it's not the efficient way to get out factors of 2 or 41, it gets out the small composites in bunches which I have to split with gp, but it does give a primality test after pulling out the small bits.

[akruppa]

GMP-ECM has a trial division option: -t <limit>
It is quite useful for getting rid of really small factors before actual ECM starts up. It also has a -primetest option, which checks inputs for primality, but you have to specify it - there's no such check by default.

Alex

[schickel]

Fivemack,

On the other hand you could do what I do. I start out with a number and put it Dario's ECM applet (http://www.alpertron.com.ar/ECM.HTM).

This has the nice feature of taking out all the small primes and any easy ECM factors before I put any remaining composite into my (smallish) ECM cluster.

As a bonus, Dario's applet also prime checks the final factorization before pasting the results into the sequence file.

And as one more bonus the applet will also perform the sigma calculation, so all I have to do is subtract the previous result right in the applet to start the next step off.

I'm currently extending three sequences right now; I might take on a couple more as the numbers get longer.

Later,
Frank

[FactorEyes]

Originally Posted by fivemack

I have just spent about a week trying to factor an aliquot-series number

4002575656069920142792412245296211078849750530528040085185518889509565302305248202324101206943842421375710626210947

... in fact a prime number.

Well, at least it's not a subtle and hard-to-track-down bug in ggnfs ...

According to what Bill Gates has said, this is not a fallow research direction:

The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. Any person or organization possessing this power could counterfeit money, penetrate any personal, corporate, or government file, and possibly even undermine the security of nations.

With more experience, you might enhance your financial and social standing.

[ewmayer]

Originally Posted by akruppa

GMP-ECM has a trial division option: -t <limit>
It is quite useful for getting rid of really small factors before actual ECM starts up. It also has a -primetest option, which checks inputs for primality, but you have to specify it - there's no such check by default.

Alex, I suggest you make -primetest the default in future releases. Given how cheap a PRP test is and that the needed functionality already is there, no good reason not to always do one prior to starting serious crunching.

(NFS program authors take not as well.)

This will also catch any occurrences of composites due to potential other reasons, e.g. candidate-processing scripts in some kind of automated factoring flow, data corruption in a networked effort, etc.

Sure, it's not unreasonable to assume users of such code will do such a test themselves, but like I said if the functionality is already there or is trivial to add...

[xilman]

Originally Posted by ewmayer

Alex, I suggest you make -primetest the default in future releases. Given how cheap a PRP test is and that the needed functionality already is there, no good reason not to always do one prior to starting serious crunching.

(NFS program authors take not as well.)

As I suggested earlier, a test for a prime power would be a very good idea for any utility which attempts to find non-trivial solutions to x^2-y^2 == 0 mod N. Such algorithms include QS and NFS.


Paul

[akruppa]

Ernst,

the problem is that with large input numbers that are to be tried with low B1 values, doing a PRP test first will take several times the time of the P-1/ECM/whatever attempt. We'd need some threshold for which numbers get a PRP test and which ones don't. So far, we'd simply taken 0 as that threshold...

Alex

[Greenbank]

I agree, in my hacked version of ecmnet I test for primality when adding the number to the server, not before each and every curve.

It may be ok if you're making ecm do multiple curves on the same number, but the way my ecmnet works is that each client does one curve and then reports back. A primality test each time would soon add up, especially as the server has had several million curves returned.