mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-11-09, 17:42   #12
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·47·103 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
For b^2048+1 I suggest choose b_min, search for primes p_min above it and check if p_min^2048+1 is PRP.
These primes will have to be even.
Batalov is offline   Reply With Quote
Old 2021-11-09, 21:38   #13
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

5×149 Posts
Default

Probably unnecessary, but why not... (after making the screenshot I stopped it)

The number is one of the two composite cofactors you need to factor.
Attached Thumbnails
Click image for larger version

Name:	2021-11-09 - ecm_alpertron.png
Views:	61
Size:	49.2 KB
ID:	26071  

Last fiddled with by Viliam Furik on 2021-11-09 at 21:40
Viliam Furik is offline   Reply With Quote
Old 2021-11-09, 22:00   #14
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·32·5·17 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
An easier way would be to make b_min a power of a known number (eg 10^244 or 10^245 since 999999/4096 is 244.140) and search for PRPs near to it on either side. That way the bases could be factored by SNFS which is relatively easy for a c244.
Much better: sieve and search only
b=k*2^762 for k>10^15 (you can limit to say k<2^64).
This will be good since now b is easily fully factored (you need to factor only k, but that is trivial).
and N=b^4096+1>10^1000000.

ps. maybe the sieve would be somewhat slower, not checked this, but the gain is much larger with a fully factored b.
N is also a Proth number, so you don't need to factor k, and you can use the classical test.

Last fiddled with by R. Gerbicz on 2021-11-09 at 22:06
R. Gerbicz is offline   Reply With Quote
Old 2021-11-09, 22:24   #15
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

24·11 Posts
Plus

Quote:
Originally Posted by chris2be8 View Post
An easier way would be to make b_min a power of a known number (eg 10^244 or 10^245 since 999999/4096 is 244.140) and search for PRPs near to it on either side. That way the bases could be factored by SNFS which is relatively easy for a c244.

Or can the b_min you quote be expressed as a simple formula?

For b^2048+1 I suggest choose b_min, search for primes p_min above it and check if p_min^2048+1 is PRP. That way you don't need to factor the base. Or look for number just above b_min that are easy to factor and check them.
The b such that b^2048+1 is prime, are 1, 150, 2558, 4650, 4772, 11272, 13236, ....

The game here is to skip forward in this sequence to the first values b such that b^2048 > 10^999999 where 10^999999 is the first integer with one million (decimal) digits. You solve b^2048 > 10^999999 for b by extracting the 2048th root on both sides of the inequality symbol, so the criterion becomes:

b > 10^(999999/2048)

So we will start from the first (even) integer after 10^(999999/2048).

Note that some b that make b^2048+1 a megaprime are already known, and they are easy to factor. For example, 24518^262144+1 is a known megaprime, and we can write:

24518^262144 + 1 = (24518^128)^2048 + 1

So all known generalized Fermat numbers can be rewritten as b^N+1 with a smaller N and a higher b, in this way. So I do not think we are interested in your procedure for finding "easy" b values.
JeppeSN is offline   Reply With Quote
Old 2021-11-09, 22:40   #16
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

24·11 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
Probably unnecessary, but why not... (after making the screenshot I stopped it)

The number is one of the two composite cofactors you need to factor.
Thanks. Note that a lot of ECM (elliptic-curve factorization) had already been attempted on these two numbers even before their values were disclosed. For that reason I expect it to be quite difficult to find new factors. /JeppeSN
JeppeSN is offline   Reply With Quote
Old 2021-11-10, 06:54   #17
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

5·149 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
Thanks. Note that a lot of ECM (elliptic-curve factorization) had already been attempted on these two numbers even before their values were disclosed. For that reason I expect it to be quite difficult to find new factors. /JeppeSN
That's why I said it was probably unnecessary.
Viliam Furik is offline   Reply With Quote
Old 2021-11-10, 16:39   #18
chris2be8
 
chris2be8's Avatar
 
Sep 2009

222110 Posts
Default

Quote:
Originally Posted by Batalov View Post
These primes will have to be even.
Doh!

I should have said look for potential bases that are easy to factor, then check if base^2048+1 is PRP. Since a hard number around 490 digits would be impossible to factor without a lot of luck.


For 4096 it would be enough to find the first sixth power above b_min, int(b_min^(1/6))+1 which I'll call b_root, then search each side of b_root^6. Any bases that yield a PRP would be fairly easy to factor with SNFS. Or a fifth or seventh power would be possible options.
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Today's Favorite Mega Number MattcAnderson MattcAnderson 44 2021-10-16 14:10
Since when was 4096 prime? Gordon PrimeNet 6 2015-07-04 17:30
My personal MEGA drive :) pepi37 Riesel Prime Search 5 2014-02-05 21:39
Assuming the goal is mega-primes, is base-3 better jasong jasong 1 2008-12-26 10:19
4096 P4 help wanted Tasuke Hardware 17 2002-08-23 22:06

All times are UTC. The time now is 10:28.


Mon Jan 17 10:28:20 UTC 2022 up 178 days, 4:57, 0 users, load averages: 0.73, 0.85, 0.85

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔