 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   FermatSearch (https://www.mersenneforum.org/forumdisplay.php?f=133)
-   -   New Fermat factors (https://www.mersenneforum.org/showthread.php?t=15449)

 LaurV 2020-10-05 16:47

:party:Yeah, We need a "Go Ryan! Go!" icon (a runner or something, haha)

 ryanp 2020-10-06 13:59

[QUOTE=Gary;558912]Congrats Ryan!!!!!!!!!! That is one HUGE factor. :w00t:[/QUOTE]

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)[/CODE]

 Batalov 2020-10-06 20:41

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 [I]b[/I] 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(...,[B]7,4[/B]), 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 [URL="https://primes.utm.edu/top20/page.php?id=8"]top lists[/URL].

Congrats!

 R. Gerbicz 2020-10-06 22:39

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?

 JeppeSN 2020-10-10 20:49

[QUOTE=ryanp;559042]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)[/CODE][/QUOTE]

Dear rynp,

Congratulations with this remarkable discovery!

Has the above PFGW run completed by now? I see no [I]User comment[/I] mentioning the GF(-, 7) divisor on [URL="https://primes.utm.edu/primes/page.php?id=131289"]https://primes.utm.edu/primes/page.php?id=131289[/URL]. I do not see your prime on the specific GF(-, 7) page [URL="http://www.prothsearch.com/GFN07.html"]http://www.prothsearch.com/GFN07.html[/URL]. Also, on the page [URL="http://www.prothsearch.com/GFNfacs.html"]http://www.prothsearch.com/GFNfacs.html[/URL], 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 [I]me[/I] (I am "Nielsen" there). In other cases it is S. Batalov or L. Joseph who got the credit. See also your primes on [URL="http://www.prothsearch.com/GFN12.html"]GFN12.html[/URL] 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

 Gary 2020-10-11 03:56

[QUOTE=JeppeSN;559489]Dear rynp,

Congratulations with this remarkable discovery!

Has the above PFGW run completed by now? I see no [I]User comment[/I] mentioning the GF(-, 7) divisor on [URL="https://primes.utm.edu/primes/page.php?id=131289"]https://primes.utm.edu/primes/page.php?id=131289[/URL]. I do not see your prime on the specific GF(-, 7) page [URL="http://www.prothsearch.com/GFN07.html"]http://www.prothsearch.com/GFN07.html[/URL]. Also, on the page [URL="http://www.prothsearch.com/GFNfacs.html"]http://www.prothsearch.com/GFNfacs.html[/URL], 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 [I]me[/I] (I am "Nielsen" there). In other cases it is S. Batalov or L. Joseph who got the credit. See also your primes on [URL="http://www.prothsearch.com/GFN12.html"]GFN12.html[/URL] 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[/QUOTE]

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.

 JeppeSN 2020-10-11 12:18

[QUOTE=Gary;559524]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.[/QUOTE]

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

 Gary 2020-10-12 07:23

[QUOTE=JeppeSN;559559]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[/QUOTE]

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)
[/CODE]

 JeppeSN 2020-10-12 20:10

[QUOTE=Gary;559634]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)
[/CODE][/QUOTE]

Cool. It should be added as a User comment on [url]https://primes.utm.edu/primes/page.php?id=131289[/url]. 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

 Dr Sardonicus 2020-10-12 21:34

[QUOTE=Gary;559634]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)
[/CODE][/QUOTE]
Fascinating. With N = 7 * 2^18233956 + 1, and

N | GF(18233952,7) :w00t:

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.

 JeppeSN 2020-10-12 22:20

[QUOTE=Dr Sardonicus;559683]Fascinating. With N = 7 * 2^18233956 + 1, and

N | GF(18233952,7) :w00t:

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

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

All times are UTC. The time now is 15:46.