Sunday, June 16, 2013

[bgvtnpai] Factorization of C158 related to the 10th Fermat number

Brent's "Factorization of the Tenth Fermat Number" published the 40-digit prime cofactor 4659775785220018543264560743076778192897 of F10 discovered by the Elliptic Curve Method, leaving the largest prime cofactor P252.  His initial attempt to prove the primality of P252 by factoring P252-1 found small prime cofactors 2 3 13 23 29 6329 760347109 211898520832851652018708913943317 9409853205696664168149671432955079744397 (this 40-digit cofactor also notably discovered by ECM as published in the paper), but there remained a C158 composite cofactor.  The primality of P252 was later proven by other means (the Cube Root Theorem).

Here is the factorization of that C158 (525 bits) as computed with Yafu using the general number field sieve: C158 = P58 * P101, where P58 = 3035625952640765962086368602839492329385321995258480540549 and P101 = 21014737139156086365509400019795978246705779843330697799891230652189207470396514322958290676782759071 .

The GNFS computation was preceded by GMP ECM with B1 auto-incremented from 1 to about 311000000.

Logs of NFS and ECM.

Initial work on this was previously mentioned in the context of Recursive Prime Predecessor Factorization Notation. Here is the completed F10 in RPPFN:
f(2^2^10+1) = (22222222222(()(2)(())(2(2()))))(2222222222222()()(2(()))(2()())(22(2)))(22222222222()(((222222((2)))))((2)(()(22(222))))(()()(()(2)((2))(22()())))((()()()((2(()))))(2222(2)(()(2())))(2()(2)(())(22()()))(2222()()((2))(2()())(((2)(2()(()()()(2))))))))(222222222222()(2())(((2)))(2(()))(22(())(222(())))(2()()()((())((2(()))))(22222(())(()())))(2(())(()()()()()())(2222()(2(()))(2()()()(2())(()(2()))(()()()(())(()()(())(()))((2())(222(())))(((2(((2)))(2(()((2)))))))(22()(()(222()(2)(2))))))))(2(2(2)(())(2(((2)))((2())(((2))))))((2())(()((222222(())(222))))(22(2)(2()())((22(2)))((2)(2)(222)(2(()))(2(()))))(2222()(2)(()(2))(22(222))(()(2)(2)((2)(())))(((2())((222)(()())))))))(2(())(())(2())(()(2)(()(2())))((()(2))(()()(2)(2)((2(())))((2(()))))(((2()()())((2)(2(()))(2(2)(((2))))))))(222222222(22()()(2222())(2(()(2())))(222222(2)))(()(())(()(2)(()))(22()(())(2()(()(222)))(2()(2)((2))(()())))(()((2()()()()(()))(((22(2)(()(2(2)(2)))))))))))((2)(2(2)(())(())(2())((2)(2(2()))(2222(2)(22()((2))(2()(222)(2()(((2)(()())))))))))(22()()(222(2222()))((())((2(())))((2(2())))((222222(2))))(22()(())(2(22()(222)))(()()()()()(()(2)(2)))))((2()(2)(222))(2()(2())(()())(()(()()(2)(2)(2()()()(()())))))(222(2)(2())((2(())))(()(((2))))(()(2())(()(2)(((2)(()())))))))(2()(()()()(2())(2()))(()(2222()(2)(2(())(()))))(2(2)(2(2()())(()()()((2))(()())))(22()(2)(()())(2(2)(2)(()))(2()(2)((2)(())))(()(222)((22(2

Here are the the large primes seen while computing the RPPFN: 6487031809 4659775785220018543264560743076778192897 211898520832851652018708913943317 9409853205696664168149671432955079744397
87812296841 3035625952640765962086368602839492329385321995258480540549 5661052561487399 1419127849 2606220457 267469547623308941 255900734834578468272217 256472179311495542956445939 16429769149 .

No comments :