mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-10-02, 01:08   #23
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·23·37 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You're talking about Mr. P-1, right? I laughed.
.
bsquared is offline   Reply With Quote
Old 2013-10-02, 07:09   #24
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

11·853 Posts
Default

You all seem like you are sure that Mr. Guy will die in 3 years...

Who the hack cares about factors for Fermat numbers? I wish that none would be found till 2026 and Mr. Guy lose the bet, but personally pay the 20 bucks with his own hand after the expiration in 2026...

Last fiddled with by LaurV on 2013-10-02 at 07:09
LaurV is offline   Reply With Quote
Old 2013-10-02, 08:30   #25
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100101011112 Posts
Default

Quote:
Originally Posted by LaurV View Post
You all seem like you are sure that Mr. Guy will die in 3 years...
I cannot believe I've just read that. Rude? Illogical? Both?
Batalov is offline   Reply With Quote
Old 2013-10-02, 09:11   #26
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

939110 Posts
Default the tyranny of evil men

Always wanted to find this speech, but it is too obscure for people to know. And it's a shame. A hundred times more people probably think in terms of, say, "Five Easy Pieces", you know, or Jules-"I'm-trying-real-hard-to-be-the-shepherd" from Pulp Fiction. (And by all means, go ahead thinking that we are the tyranny of evil men, complete with a Mr.9 mm in your face while reading from the Bible. "But that sh!t ain't the truth either." "Go.")

But here's an explanation that really matters, in my opinion:
Batalov is offline   Reply With Quote
Old 2013-10-02, 13:08   #27
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Batalov View Post
A hundred times more people probably think in terms of, say, "Five Easy Pieces"
Do you mean the Houston Comets?
R.D. Silverman is offline   Reply With Quote
Old 2013-10-02, 19:00   #28
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
So, toying with this idea further...how hard would it be to make a script to do a false sieve for this? I imagine (no experience with programming beyond BASIC) that one could create a script to find all factors of numbers of the form F(X)-(sqrt(F(X)-1)-n) below, say, 1M, then either a) write the n value to postsieve.txt if all factors are to an even power, then increase the n value by 1 and continue or b) increase the n values by one and continue without writing.

@RDS- please, don't bother lecturing me about the fact that this is not a feasible effort. If you care to explain how high the n value would be expected to reach before success as a function of X or F(X), however, feel free, I would enjoy seeing how that would be approximated.


Caution: F(X) is assumed to be the Xth Fermat number.
Can someone at least confirm that the above equation would be right for finding these types of numbers (sums of squares for Fermat numbers)?
c10ck3r is offline   Reply With Quote
Old 2013-10-02, 23:25   #29
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
So, toying with this idea further...how hard would it be to make a script to do a false sieve for this? I imagine (no experience with programming beyond BASIC) that one could create a script to find all factors of numbers of the form F(X)-(sqrt(F(X)-1)-n) below, say, 1M, then either a) write the n value to postsieve.txt if all factors are to an even power, then increase the n value by 1 and continue or b) increase the n values by one and continue without writing.

Caution: F(X) is assumed to be the Xth Fermat number.
We actually want to look at the expression F(X)-(sqrt(F(X)-1)-n)2 (note the exponent) and determine if it is a perfect square rather than find its factors. The value for n = 0 is trivially the square 1, so we start at n = 1 and increase it. In general, we can eliminate non-squares by sieving. Any square must be congruent to 0, 1, or 4 mod 8, for example, so any values of F(X)-(sqrt(F(X)-1)-n)2 which are congruent to 2, 3, 5, 6, or 7 mod 8 need not be further considered. This immediately eliminates all values of n congruent to 2 mod 4. Next we consider that any square must be congruent to 0 or 1 mod 3. This eliminates all values of n congruent to 1 mod 3. (Or we could say congruent to 0, 1, 4, or 7 mod 9 to eliminate more values of n.) In general, we set up a table for each prime p that we use for sieving that allows us to infer from n's congruence class mod p whether the above expression is a non-square or possibly a square. After we sieve with a reasonable number of different p's (Lehmer used all p's less than or equal to 127 in his Delay Line Sieve, later increased to 157) we expect that the few remaining n values are good candidates for generating perfect squares in the above expression. We can then test those candidates for each remaining n by taking the integer square root of F(X)-(sqrt(F(X)-1)-n)2, squaring that, and seeing if it is equal to the original expression.

I have coded such a sieve in C, but to optimize it, the sieving routines should be done in assembly language. It would be a good learning exercise, though, to code it in a higher level language. The integer square-root function is only called occasionally, and the C routine in GMP or MPIR would probably work just fine. Or you could just write the candidate n values to a list (there shouldn't be very many) and check to see if the resulting expression is a square using PARI or some other computational package. Try it with F5. You are sieving values of F5 - (65536 - n)2 = 1 + 131072*n - n2 by all small primes p to eliminate all values of n for which this expression is not a perfect square mod p. If you set up an array to check all n values from 1 to say, 20,000, you should find that the only value of n which gives you a perfect square will be 3272 = 65536 - 62264.

There is more to my method than this, I suggested working in general on trying to find sums of squares representations of N, where N could be a Fermat number, or a composite factor of a Fermat number, or either of these two possibilities multiplied by a product of distinct prime factors which all have representations of sums of squares. Or N could be any other number whose factors are all equal to 1 mod 4. The possibilities of trying many multipliers takes this from being a deterministic method of order n1/2 to a probabilistic method of order n1/4. The method of sieving was around for centuries before the Lehmers used an electronic device to automate and speed up the sieving. In general, we sieve on N - (sqrt(N) - n)2 where sqrt(N) is the integer truncation of the square-root of N.
philmoore is offline   Reply With Quote
Old 2013-10-03, 03:00   #30
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2·7·739 Posts
Default

Hum. Factoring a 1133-digit number or primality testing a 2.58+ billion-digit number? Which will require more CPU time assuming an "average" number of factors and difficulty for the 1133-digit number? My guess is that the factorization would require more CPU time in the long run assuming that it was "average" with today's knowledge and technology.

BUT...2 factors (pun intended) weigh in favor of doing the factorization:

1. It can be distributed across 1000s of computers. To the best of my knowledge, the primality test cannot. (At least not yet anyway.)

2. We might get lucky and factor it quickly. There would be no equivalent probability of "luckiness" for the primality test.

It would be interesting to see a project set up specifically to fully factor F12. Even with many computers running it, I think it would be unlikely to complete its task in 3 years. It would become the equivalent of a "Riesel Sieve" or 17-or-bust type project where the goal is a finite one but will likely take decades to finish.

Personally, I find huge finite projects to be much more interesting than open-ended ones that have no purpose other than to just find primes until they get tired of searching for them.

Last fiddled with by gd_barnes on 2013-10-03 at 03:03
gd_barnes is offline   Reply With Quote
Old 2013-10-03, 03:33   #31
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

11×853 Posts
Default

third factor: (in favor of factorization)

3. you may finish the primality test and find out that F33 is composite, therefore you are back at the starting point (edit: which would - most probably - be the case, because the general belief/heuristic/probabilistic/etc is that all fermat numbers are composite, except the first 5).

Last fiddled with by LaurV on 2013-10-03 at 03:37
LaurV is offline   Reply With Quote
Old 2013-10-03, 04:27   #32
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×17×109 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
It would be interesting to see a project set up specifically to fully factor F12.
Or make it a simple 3-year challenge: "Save Richard Guy $20" project. Hmm, not catchy. How 'bout the "save Richard Guy from bankruptcy" project.
Prime95 is offline   Reply With Quote
Old 2013-10-03, 04:32   #33
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

11×853 Posts
Default

Quote:
Originally Posted by Prime95 View Post
"Save Richard Guy $20"
What do you mean by that? If I would be the lucky son of the gun to factor some Fm, then I WILL take his $10, and I will expressly ask him to send me a signed check... After 50 years that will worth a fortune! I will make my grandchildren happy and they won't need to work for all their lives...
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Weird freezing error, desperate for a solution. jasong Lounge 5 2016-11-18 00:43
September 2016 Batalov Puzzles 8 2016-10-04 14:10
YAFU Poly Select Deadline amphoria YAFU 22 2016-09-17 09:47
Official Ernst (ewmayer) / Richard (cheesehead) feud thread cheesehead Soap Box 50 2014-06-30 01:06
Appeal for machines dave_dm GMP-ECM 0 2005-06-29 02:23

All times are UTC. The time now is 16:05.

Tue Apr 20 16:05:52 UTC 2021 up 12 days, 10:46, 1 user, load averages: 2.73, 2.76, 2.51

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.