Fermat numbers: Difference between revisions

Content added Content deleted
(→‎factoring via Pollard's rho algorithm: optimized the RHO function.)
Line 1,981: Line 1,981:
F(8): 1238926361552897, 93461639715357977769163558199606896584051237541638188580280321
F(8): 1238926361552897, 93461639715357977769163558199606896584051237541638188580280321
</pre>
</pre>

=={{header|Scala}}==
{{trans|Kotlin}}
<lang scala>import scala.collection.mutable
import scala.collection.mutable.ListBuffer

object FermatNumbers {
def main(args: Array[String]): Unit = {
println("First 10 Fermat numbers:")
for (i <- 0 to 9) {
println(f"F[$i] = ${fermat(i)}")
}
println()
println("First 12 Fermat numbers factored:")
for (i <- 0 to 12) {
println(f"F[$i] = ${getString(getFactors(i, fermat(i)))}")
}
}

private val TWO = BigInt(2)

def fermat(n: Int): BigInt = {
TWO.pow(math.pow(2.0, n).intValue()) + 1
}

def getString(factors: List[BigInt]): String = {
if (factors.size == 1) {
return s"${factors.head} (PRIME)"
}

factors.map(a => a.toString)
.map(a => if (a.startsWith("-")) "(C" + a.replace("-", "") + ")" else a)
.reduce((a, b) => a + " * " + b)
}

val COMPOSITE: mutable.Map[Int, String] = scala.collection.mutable.Map(
9 -> "5529",
10 -> "6078",
11 -> "1037",
12 -> "5488",
13 -> "2884"
)

def getFactors(fermatIndex: Int, n: BigInt): List[BigInt] = {
var n2 = n
var factors = new ListBuffer[BigInt]
var loop = true
while (loop) {
if (n2.isProbablePrime(100)) {
factors += n2
loop = false
} else {
if (COMPOSITE.contains(fermatIndex)) {
val stop = COMPOSITE(fermatIndex)
if (n2.toString.startsWith(stop)) {
factors += -n2.toString().length
loop = false
}
}
if (loop) {
val factor = pollardRhoFast(n2)
if (factor == 0) {
factors += n2
loop = false
} else {
factors += factor
n2 = n2 / factor
}
}
}
}

factors.toList
}

def pollardRhoFast(n: BigInt): BigInt = {
var x = BigInt(2)
var y = BigInt(2)
var z = BigInt(1)
var d = BigInt(1)
var count = 0

var loop = true
while (loop) {
x = pollardRhoG(x, n)
y = pollardRhoG(pollardRhoG(y, n), n)
d = (x - y).abs
z = (z * d) % n
count += 1
if (count == 100) {
d = z.gcd(n)
if (d != 1) {
loop = false
} else {
z = BigInt(1)
count = 0
}
}
}

println(s" Pollard rho try factor $n")
if (d == n) {
return 0
}
d
}

def pollardRhoG(x: BigInt, n: BigInt): BigInt = ((x * x) + 1) % n
}</lang>
{{out}}
<pre>First 10 Fermat numbers:
F[0] = 3
F[1] = 5
F[2] = 17
F[3] = 257
F[4] = 65537
F[5] = 4294967297
F[6] = 18446744073709551617
F[7] = 340282366920938463463374607431768211457
F[8] = 115792089237316195423570985008687907853269984665640564039457584007913129639937
F[9] = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

First 12 Fermat numbers factored:
F[0] = 3 (PRIME)
F[1] = 5 (PRIME)
F[2] = 17 (PRIME)
F[3] = 257 (PRIME)
F[4] = 65537 (PRIME)
Pollard rho try factor 4294967297
F[5] = 641 * 6700417
Pollard rho try factor 18446744073709551617
F[6] = 274177 * 67280421310721
Pollard rho try factor 340282366920938463463374607431768211457
F[7] = 59649589127497217 * 5704689200685129054721
Pollard rho try factor 115792089237316195423570985008687907853269984665640564039457584007913129639937
F[8] = 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321
Pollard rho try factor 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
F[9] = 2424833 * (C148)
Pollard rho try factor 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217
Pollard rho try factor 3942951359960012586542991835686376608231592127249807732373409846031135195659174148737161255930050543559319182152642816343958573976075461198274610155058226350701077796608546283231637018483208223116080561800334422176622099740983337736621316898600121619871377542107047343253864459964167331555646795960321
F[10] = 45592577 * 6487031809 * (C291)
Pollard rho try factor 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230657
Pollard rho try factor 33150781373639412155846573868024639672856106606987835072026893834352453701925006737655987144186344206834820532125383540932102878651453631377873037143648178457002958783669056532601662155256508553423204658756451069116132055982639112479817996775373591674794399801442382402697828988429044712163168243619196804348072710121945390948428910309765481110260333687910970886853046635254307274981520537180895290310783635953818082306553996934497908037349010876970379631341148456045116407475229712217130141926525362871253437794629422541384355185626695660779797862427347553871011957167960991543632376506466281643163047416635393
F[11] = 974849 * 319489 * (C606)
Pollard rho try factor 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006686938976881787785946905630190260940599579453432823469303026696443059025015972399867714215541693835559885291486318237914434496734087811872639496475100189041349008417061675093668333850551032972088269550769983616369411933015213796825837188091833656751221318492846368125550225998300412344784862595674492194617023806505913245610825731835380087608622102834270197698202313169017678006675195485079921636419370285375124784014907159135459982790513399611551794271106831134090584272884279791554849782954323534517065223269061394905987693002122963395687782878948440616007412945674919823050571642377154816321380631045902916136926708342856440730447899971901781465763473223850267253059899795996090799469201774624817718449867455659250178329070473119433165550807568221846571746373296884912819520317457002440926616910874148385078411929804522981857338977648103126085903001302413467189726673216491511131602920781738033436090243804708340403154190337
Pollard rho try factor 9106268965752186405773463110818163752233991481723476361152625650968740750826648212547208641935996986118024454955917854702609434541985662158212523327009262247869952450049350838706079834460006786304075107567909269645531121898331250125751682239313156601738683820643686003638396435055834553570682260579462973839574318172464558815116581626749391315641251152532705571615644886981829338611134458123396450764186936496833100701185274214915961723337127995182593580031119299575446791424418154036863609858251201843852076223383379133238000289598800458955855329052103961332983048473420515918928565951506637819342706575976725030506905683310915700945442329953941604008255667676914945655757474715779252371155778495946746587469464160684843488975918662295274965457887082037460184558511575570318625886351712499453155527762335682281851520733417380809781252979478377941937578568481859702438295520231435016188495646093490407803983345420364088331996467459309353537828143080691834120737157445502646809195267166779721413577366833939771467773331873590129210913628329073978766992198221682739812652450408607796042492802295258713711959073218748776359806123717024800451461326745599716651128725627280643537507664130920416107218492950792456907321580171946770433
Pollard rho try factor 350001591824186871106763863899530746217943677302816436473017740242946077356624684213115564488348300185108877411543625345263121839042445381828217455916005721464151569276047005167043946981206545317048033534893189043572263100806868980998952610596646556521480658280419327021257968923645235918768446677220584153297488306270426504473941414890547838382804073832577020334339845312084285496895699728389585187497914849919557000902623608963141559444997044721763816786117073787751589515083702681348245404913906488680729999788351730419178916889637812821243344085799435845038164784900107242721493170135785069061880328434342030106354742821995535937481028077744396075726164309052460585559946407282864168038994640934638329525854255227752926198464207255983432778402344965903148839661825873175277621985527846249416909718758069997783882773355041329208102046913755441975327368023946523920699020098723785533557579080342841062805878477869513695185309048285123705067072486920463781103076554014502567884803571416673251784936825115787932810954867447447568320403976197134736485611912650805539603318790667901618038578533362100071745480995207732506742832634459994375828162163700807237997808869771569154136465922798310222055287047244647419069003284481
F[12] = 114689 * 26017793 * 63766529 * (C1213)</pre>


=={{header|Sidef}}==
=={{header|Sidef}}==
Retrieved from "https://rosettacode.org/wiki/Fermat_numbers"