mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-02-27, 08:26   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7·919 Posts
Default 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 ...

fivemack is offline   Reply With Quote
Old 2007-02-27, 08:52   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1086210 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
xilman is offline   Reply With Quote
Old 2007-02-27, 10:21   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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

alex
akruppa is offline   Reply With Quote
Old 2007-02-27, 11:01   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7·919 Posts
Default

Quote:
Originally Posted by akruppa View Post
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.
fivemack is offline   Reply With Quote
Old 2007-02-27, 11:51   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-03-05, 07:20   #6
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2·1,061 Posts
Default

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
schickel is offline   Reply With Quote
Old 2007-03-05, 16:38   #7
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

23×32×5 Posts
Default

Quote:
Originally Posted by fivemack View Post
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:

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.
With more experience, you might enhance your financial and social standing.
FactorEyes is offline   Reply With Quote
Old 2007-03-05, 18:15   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

11,657 Posts
Default

Quote:
Originally Posted by akruppa View Post
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...
ewmayer is offline   Reply With Quote
Old 2007-03-05, 18:55   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

251568 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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
xilman is offline   Reply With Quote
Old 2007-03-06, 08:22   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-03-06, 12:07   #11
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

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.
Greenbank is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wall-Sun-Sun primes Gandolf Math 49 2017-04-13 20:00
If you could meet any Mersenne prime discoverer... ixfd64 Lounge 24 2012-08-20 21:00
The Hello - I am - Nice to meet you thread.... Prime Monster Lounge 23 2012-02-11 11:08
Meet the English? wblipp Lounge 27 2010-09-18 13:03
The Ladder Against The Wall Numbers Puzzles 27 2005-07-02 10:19

All times are UTC. The time now is 12:23.


Sat Sep 25 12:23:40 UTC 2021 up 64 days, 6:52, 0 users, load averages: 1.74, 1.79, 1.67

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.