mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Head, meet wall (https://www.mersenneforum.org/showthread.php?t=7209)

fivemack 2007-02-27 08:26

Head, meet wall
 
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 ...

:sad: :mad: :blush: :down:

xilman 2007-02-27 08:52

[QUOTE=fivemack;99482]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 ...

:sad: :mad: :blush: :down:[/QUOTE]OTOH, a test could very easily be built into ggnfs to see whether it is being asked to factor a prime power.


Paul

akruppa 2007-02-27 10:21

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

alex

fivemack 2007-02-27 11:01

[QUOTE=akruppa;99496]So does the Aliquot sequence terminate with a prime? What was the starting value?
alex[/QUOTE]

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 2007-02-27 11:51

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 2007-03-05 07:20

Fivemack,

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

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 2007-03-05 16:38

[QUOTE=fivemack;99482]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 ...

:sad: :mad: :blush: :down:[/QUOTE]

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

[QUOTE] 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. [/QUOTE]

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

ewmayer 2007-03-05 18:15

[QUOTE=akruppa;99501]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.[/QUOTE]

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 2007-03-05 18:55

[QUOTE=ewmayer;99977]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.)[/QUOTE]As I suggested earlier, a test for a [b]prime power[/b] 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 2007-03-06 08:22

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 2007-03-06 12:07

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.


All times are UTC. The time now is 20:53.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.