mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2020-10-05, 16:47   #309
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×2,239 Posts
Default

Yeah, We need a "Go Ryan! Go!" icon (a runner or something, haha)
LaurV is offline   Reply With Quote
Old 2020-10-06, 13:59   #310
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

22·53 Posts
Default

Quote:
Originally Posted by Gary View Post
Congrats Ryan!!!!!!!!!! That is one HUGE factor.
Thanks! PFGW is still running. Looks like it divides a few other things too.

Code:
7*2^18233956+1 is a Factor of F18233954!!!! (163569.267086 seconds)

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1                                  

7*2^18233956+1 is a Factor of GF(18233952,7)!!!! (174791.088006 seconds)         

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1                                  

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1

7*2^18233956+1 is a Factor of xGF(18233954,7,2)!!!! (334431.512631 seconds)
ryanp is offline   Reply With Quote
Old 2020-10-06, 20:41   #311
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Thumbs up

Footnote: Btw, periodically I think (and then I postpone thinking about that) that PFGW could use quite a bit of combinatorial acceleration:
when any single base b test has led to a positive result (e.g. in the case, 2 and 7) - their combination will also lead to hit (but m value will need to be found; there is a cool but predictable structure; b^2^(N+delta) (where delta is increasing from a small negative to zero e.g. {-20..0}) can arrive at -1 or directly into 1, and then will remain at 1 during the next squarings -- and only very rarely the two bases might poison each other and not produce a hit).

Illustration: of course still to come out of this xGF computational run is
7*2^18233956+1 is a Factor of xGF(...,7,4), too.
And if another base is hit, e.g. 5, then there will be a constellation of xGF hits that will combine 2 and 5, 2 and 7, 5 and 7.

P.S. C.C. has received the email about Fermat divisor and adjusted official remark, and then the system rearranged top lists.

Congrats!
Batalov is offline   Reply With Quote
Old 2020-10-06, 22:39   #312
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

141910 Posts
Default

As I can remember pfgw is doing this (or something like that, the constant=50 is not that interesting,
we'd catch all known factors if n is not small: n>50): let N=k*2^n+1 and
r(u)=u^(2^(n-50)) mod N
compute it for u=2,3,5,7,11 and store these.

Then you can check very easily all xGFN(n-d,a,b) mod N=a^(2^(n-d))+b^(2^(n-d)) mod N for a,b<=12 and d<=50.

So basically the extra cost of these xGFN divisibility checks is only four times of a single prp test, because u=2 comes for free. Could we check these times?

Last fiddled with by R. Gerbicz on 2020-10-06 at 22:41 Reason: grammar
R. Gerbicz is offline   Reply With Quote
Old 2020-10-10, 20:49   #313
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·34 Posts
Default

Quote:
Originally Posted by ryanp View Post
Thanks! PFGW is still running. Looks like it divides a few other things too.

Code:
7*2^18233956+1 is a Factor of F18233954!!!! (163569.267086 seconds)

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1                                  

7*2^18233956+1 is a Factor of GF(18233952,7)!!!! (174791.088006 seconds)         

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1                                  

Special modular reduction using all-complex AVX-512 FFT length 1008K, Pass1=2304, Pass2=448, clm=1, 8 threads on 7*2^18233956+1

7*2^18233956+1 is a Factor of xGF(18233954,7,2)!!!! (334431.512631 seconds)
Dear rynp,

Congratulations with this remarkable discovery!

Has the above PFGW run completed by now? I see no User comment mentioning the GF(-, 7) divisor on https://primes.utm.edu/primes/page.php?id=131289. I do not see your prime on the specific GF(-, 7) page http://www.prothsearch.com/GFN07.html. Also, on the page http://www.prothsearch.com/GFNfacs.html, your prime does not appear even when it divides GF(-, 7) and xGF(-, 7, 2) (and possibly more, I do not know).

I really think you should inform the world of your discoveries. On several occasions, I (and others) have had to run the test for ((x)G)F divisibility myself. On the last page I linked, you will see that the credit has been awarded to me (I am "Nielsen" there). In other cases it is S. Batalov or L. Joseph who got the credit. See also your primes on GFN12.html etc. Search for "Propper" on those pages.

If you do not "disclose" the information, someone is going to run the PFGW xGF test again, and submit the results, and take the credit.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-10-11, 03:56   #314
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5·11 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Dear rynp,

Congratulations with this remarkable discovery!

Has the above PFGW run completed by now? I see no User comment mentioning the GF(-, 7) divisor on https://primes.utm.edu/primes/page.php?id=131289. I do not see your prime on the specific GF(-, 7) page http://www.prothsearch.com/GFN07.html. Also, on the page http://www.prothsearch.com/GFNfacs.html, your prime does not appear even when it divides GF(-, 7) and xGF(-, 7, 2) (and possibly more, I do not know).

I really think you should inform the world of your discoveries. On several occasions, I (and others) have had to run the test for ((x)G)F divisibility myself. On the last page I linked, you will see that the credit has been awarded to me (I am "Nielsen" there). In other cases it is S. Batalov or L. Joseph who got the credit. See also your primes on GFN12.html etc. Search for "Propper" on those pages.

If you do not "disclose" the information, someone is going to run the PFGW xGF test again, and submit the results, and take the credit.

/JeppeSN
Wilfrid Keller is aware of the new factor and just updated his Fermat factors page. I expect he will update the GFN pages once the pfgw run completes. I am running it through pgfw also, as a double check, but I expect Ryan's run will finish first.
Gary is offline   Reply With Quote
Old 2020-10-11, 12:18   #315
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·34 Posts
Thumbs up

Quote:
Originally Posted by Gary View Post
Wilfrid Keller is aware of the new factor and just updated his Fermat factors page. I expect he will update the GFN pages once the pfgw run completes. I am running it through pgfw also, as a double check, but I expect Ryan's run will finish first.
Very good. Thank you. So in this case the number will be carefully checked and double checked. But I also wrote to Ryan P. to make sure future primes are not forgotten. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-10-12, 07:23   #316
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5·11 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Very good. Thank you. So in this case the number will be carefully checked and double checked. But I also wrote to Ryan P. to make sure future primes are not forgotten. /JeppeSN
Here is a preliminary full list of the xGF(*,a,b) divisibilities where a,b <= 12.

Code:
7 * 2^18233956 + 1 divides GF(18233952,7)
7 * 2^18233956 + 1 divides xGF(18233953,7,4)
7 * 2^18233956 + 1 divides F18233954
7 * 2^18233956 + 1 divides xGF(18233954,7,2)
7 * 2^18233956 + 1 divides xGF(18233954,8,7)
7 * 2^18233956 + 1 divides xGF(18233954,11,9)
7 * 2^18233956 + 1 divides xGF(18233955,9,5)
7 * 2^18233956 + 1 divides xGF(18233955,10,9)
7 * 2^18233956 + 1 divides xGF(18233955,11,5)
7 * 2^18233956 + 1 divides xGF(18233955,11,10)
Gary is offline   Reply With Quote
Old 2020-10-12, 20:10   #317
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·34 Posts
Thumbs up

Quote:
Originally Posted by Gary View Post
Here is a preliminary full list of the xGF(*,a,b) divisibilities where a,b <= 12.

Code:
7 * 2^18233956 + 1 divides GF(18233952,7)
7 * 2^18233956 + 1 divides xGF(18233953,7,4)
7 * 2^18233956 + 1 divides F18233954
7 * 2^18233956 + 1 divides xGF(18233954,7,2)
7 * 2^18233956 + 1 divides xGF(18233954,8,7)
7 * 2^18233956 + 1 divides xGF(18233954,11,9)
7 * 2^18233956 + 1 divides xGF(18233955,9,5)
7 * 2^18233956 + 1 divides xGF(18233955,10,9)
7 * 2^18233956 + 1 divides xGF(18233955,11,5)
7 * 2^18233956 + 1 divides xGF(18233955,11,10)
Cool. It should be added as a User comment on https://primes.utm.edu/primes/page.php?id=131289. If you have at least one prime on primes.utm.edu, you can do it. Ask me if you do not know how to do the trick. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-10-12, 21:34   #318
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·29·67 Posts
Default

Quote:
Originally Posted by Gary View Post
Here is a preliminary full list of the xGF(*,a,b) divisibilities where a,b <= 12.

Code:
7 * 2^18233956 + 1 divides GF(18233952,7)
7 * 2^18233956 + 1 divides xGF(18233953,7,4)
7 * 2^18233956 + 1 divides F18233954
7 * 2^18233956 + 1 divides xGF(18233954,7,2)
7 * 2^18233956 + 1 divides xGF(18233954,8,7)
7 * 2^18233956 + 1 divides xGF(18233954,11,9)
7 * 2^18233956 + 1 divides xGF(18233955,9,5)
7 * 2^18233956 + 1 divides xGF(18233955,10,9)
7 * 2^18233956 + 1 divides xGF(18233955,11,5)
7 * 2^18233956 + 1 divides xGF(18233955,11,10)
Fascinating. With N = 7 * 2^18233956 + 1, and

N | GF(18233952,7)

we obtain N | 7^(2^18233953) - 1. Since also

N | F18233954, we obtain

N | xGF(18233953,7,4).

From N | 7^(2^18233953) - 1 we obtain N | 7^(2^18233954) - 1.

Again applying N | F18233954, we obtain

N | xGF(18233954,7,2)

Since N | F18233954, F18233954 | 8^18233954 + 1, and N | 7^(2^18233954) - 1, we obtain

N | xGF(18233954,8,7).

I haven't figured out an easy path to the other ones.
Dr Sardonicus is offline   Reply With Quote
Old 2020-10-12, 22:20   #319
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

16210 Posts
Lightbulb

Quote:
Originally Posted by Dr Sardonicus View Post
Fascinating. With N = 7 * 2^18233956 + 1, and

N | GF(18233952,7)

we obtain N | 7^(2^18233953) - 1. Since also

N | F18233954, we obtain

N | xGF(18233953,7,4).

From N | 7^(2^18233953) - 1 we obtain N | 7^(2^18233954) - 1.

Again applying N | F18233954, we obtain

N | xGF(18233954,7,2)

Since N | F18233954, F18233954 | 8^18233954 + 1, and N | 7^(2^18233954) - 1, we obtain

N | xGF(18233954,8,7).

I haven't figured out an easy path to the other ones.
But before that, Ravi Fernando showed me:

Let p = k * 2^n + 1 be a prime that divides a Fermat number. From the formula, we can write k = -1/2^n (mod p). But the order of 2 (mod p) is a power of two, and clearly the order of -1 is as well, so this shows that the order of k (mod p) is a power of two. So p divides a GF(-, k).

So we could tell in advance, once we knew 7*2^18233956+1 divided an F(-), that it also divided a GF(-, 7).

/JeppeSN
JeppeSN is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Generalized Fermat factors Batalov Factoring 149 2017-02-20 12:06
Best case Fermat Factors yourskadhir Miscellaneous Math 5 2012-12-12 04:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Weighted Fermat factors Top 20 Merfighters Factoring 0 2010-04-13 14:16
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22

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

Wed Dec 2 16:25:53 UTC 2020 up 83 days, 13:36, 2 users, load averages: 1.62, 1.69, 1.68

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