mersenneforum.org Head, meet wall
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-02-27, 08:26 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 33·239 Posts 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 ...
2007-02-27, 08:52   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101100000111112 Posts

Quote:
 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

 2007-02-27, 10:21 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts So does the Aliquot sequence terminate with a prime? What was the starting value? alex
2007-02-27, 11:01   #4
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

33·239 Posts

Quote:
 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.

 2007-02-27, 11:51 #5 akruppa     "Nancy" Aug 2002 Alexandria 9A316 Posts GMP-ECM has a trial division option: -t 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
 2007-03-05, 07:20 #6 schickel     "Frank <^>" Dec 2004 CDP Janesville 84A16 Posts 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
2007-03-05, 16:38   #7
FactorEyes

Oct 2006
vomit_frame_pointer

23×32×5 Posts

Quote:
 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:

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.

2007-03-05, 18:15   #8
ewmayer
2ω=0

Sep 2002
Repรบblica de California

32×1,303 Posts

Quote:
 Originally Posted by akruppa GMP-ECM has a trial division option: -t 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...

2007-03-05, 18:55   #9
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101100000111112 Posts

Quote:
 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

 2007-03-06, 08:22 #10 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
 2007-03-06, 12:07 #11 Greenbank     Jul 2005 2·193 Posts 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime Monster Lounge 25 2022-05-13 13:20 Gandolf Math 49 2017-04-13 20:00 ixfd64 Lounge 24 2012-08-20 21:00 wblipp Lounge 27 2010-09-18 13:03 Numbers Puzzles 27 2005-07-02 10:19

All times are UTC. The time now is 01:36.

Fri May 20 01:36:27 UTC 2022 up 35 days, 23:37, 2 users, load averages: 2.08, 1.45, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐