Primality Certificate for (5855^6121-1)/5854

This certificate uses a theorem of Coppersmith and Howgrave-Graham to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 27.442143% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 27.442143%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 493 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F⁴>N, N can have no more than three prime factors.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 1490630 5032648932 9062560717 6955702107 5113334806 7016678315 5416822740 3504193716 3190327886 6137541620 4406970313 9557811686 3232348704 8878492688 1392740113 0834927851 1714147950 3554729430 4730726918 3204474618 0273942478 7325934200 6498817946 8508006835 2222802836 0679359826 8697672129 7877869469 9655348346 4687026802 7002021717 9517531256 1908552411 9063175882 9441439737 0264610178 2247155029 6173824514 5995489737 9026628551 2968998911 0399777091 4644909572 1327761514 2206671227 7884512124 2346673341 3274363070 7235036697 9028273854 7136576048 0645324811 8511871598 9910537861 6606380126 5426502765 3052448537 0000476708 0929814303 8801487243 0745151923 8503513261 3835875155 6905951767 4768802283 6639095231 0519932566 4109858856 8795403684 9782760763 8628742953 2161562604 1998034460 5091354842 8979380545 5389903926 3004734620 7071278889 6167083982 3032093977 5499586130 4329115251 4417421774 7688729328 4827499556 4620938370 7453369415 6818776047 7085481775 6509326640 8915962765 5160944375 5829300320 0730044242 4853755225 3920822480 1644509753 1555880191 1028282060 2106943506 1584674763 3039471245 3585978389 3411069569 0704899137 8206282274 6869512624 7251992216 4462047889 3019021165 3746258345 4376020937 4848930687 0357159527 2821466870 1610146627 3996239533 6085947208 0757259192 2962882384 2180030051 0070259948 1187370752 0431105524 1426270794 4915580364 8355911723 1183737639 9177891605 8055617791 9670275625 5725432632 1890534264 2578591796 2547649257 8020465521 3923220039 5644587473 0635830639 3939610970 0329375870 3114208062 1972164808 0201431350 7492827109 1796564355 1219135817 7167261082 2958170166 4693686797 6969395447 0730063511 0232509592 1060000068 3834039004 4023740609 4660489122 8672005951 8324299543 3557155216 5538097249 0899308979 7818061304 7554942057 9335751165 5529621643 1268071459 4350363111 9025446703 4275245877 8557082966 7489684047 5369313324 3510553559 1183869534 1815292919 7156361127 3524926209 2185679573 9262979050 5375212391 3249620374 1252686291 5480272594 0567478124 6906484975 6879650943 2933072265 3442180166 8750412649 4525325965 5374093159 7991168074 9383469531 5704069067 3920460096 7192858076 9090340458 2383208339 8573292479 3027575054 8162948750 5728060663 2933130837 0249443609 7326980240 8407597262 8333336301 2362514443 4000070682 3432401811 3786958544 3614919400 8802021089 5918896272 9581856780 5210807646 8949944937 7701465130 8152002290 5389157851 5031482078 9502066474 9842084805 4279020881 7024844134 1669351888 1673373546 3624808770 9046486356 8897973591 3928709788 2362843351 1287328763 1537187450 7810952552 3258687596 7176534997 0334416227 5253997841 4500210041 4312514649 6395378195 2908168835 1793695562 1353585805 7793694968 4626580421 0244176311 4616261036 0290107130 5920595619 5092463267 1935681948 1594016296 5440421612 4028341341 1440725939 6713051410 6904928316 8910040939 3265256824 4151596957 5633454832 0921065694 5446874152 7155360881 1137920562 3402703150 5957559697 6413904765 3902171334 2721076845 1501357391 4849951336 2201137109 1637772361 9939611581 5348981366 4689658681 0441965944 3358989511 9587532693 0351393397 7174304917 8049808561 3595930573 3325191521 8011748984 2954732136 2964450224 6385523149 8531903830 8771555978 1443247413 8017163577 7989928185 9367027124 8997775745 3601229487 9058817476 3036438501 0477254252 5220221718 7506732462 6895244883 4843715300 2394788633 0699702129 1165850315 4765052484 0535472709 8442461296 8820465011 7906728153 8506928345 2921865928 4073187219 4233099891 1570679368 8801128095 7486373456 2512874602 2512749974 6622893916 6143834708 2722331040 5140445863 5006948054 9416851819 6221303045 3255447660 3985980451 1862628769 3283702473 6214466226 8999026288 5004492718 7684346840 3872325593 2981254299 1701163246 7387158045 8987491139 2312718764 6670798600 5923016554 1475222455 2590655501 9866982373 0083850332 0691588166 7093443753 2666467190 6370909488 0447649106 6797593271 6752788285 3512155717 3874432394 7430865828 9453007444 3701052706 4076541721 2222515766 8735838868 1585030086 3878935315 6955373198 0359898337 5030906722 4369222151 9368914839 9979536126 0520012847 6135082730 2360481237 9581093515 1506434665 8351355961 2914881941 9740791397 1766791839 9922006464 8622335161 2526058334 5036790346 7865682701 5311505392 2862096056 4039134498 3642274096 8827923288 4599602637 5875570535 7668934481 0784761919 1792354674 2101940331 3137815731 9669988648 9708337201 2201039017 0378079153 6960581338 5106416638 2689227738 4451524355 3076918816 4609320466 6771269255 4163669253 6258574192 6869918264 6118565368 4620394556 2372124207 3244743242 1761833799 0764345762 8412134760 2597799683 6193931030 7241973539 9409051491 5452321358 0428676193 5927984803 5312904989 2657987779 7336581228 5529151010 9208085778 7950773060 7702654375 1525757909 0932148048 1464473453 5018468484 8790445096 2279148397 4967643614 3664604623 6543495562 2814646027 1418595762 3173381955 4504175150 0773361944 3886086710 1371758947 4858136592 5178568368 9098850033 4123290797 7436167245 5439038741 1077695655 9187480019 1694394779 9978679038 8784535327 0599939018 9847668222 5304528662 8675163166 5112368036 5022915659 6540966603 4444753802 9000424653 0396968928 4840990794 2690079675 9273082865 1592953274 1424017257 7396663476 9818257780 5456316381 7199726479 1668098637 2380380883 2720189068 3684858963 2581592218 3907339882 8904549468 0638057844 0868816149 5164994269 0134588398 9302066277 2337602486 5413385083 6177189781 8550118592 7683219647 0217001168 2731712865 3085998528 4475918934 6614649117 6770024123 5139999323 9527325315 7955641672 1583158081 5408103341 4328341988 3487260659 5046369065 3961254309 7703408712 4365445914 5837691469 4402079805 1551920016 9941483715 4682670981 4106839514 8508436532 2242536261 8876819778 4583070681 1026255991 1157338291 7469329547 3189010033 6163723083 2593218006 6468567527 0262477230 1728672119 7509801241 7354857000 4301407704 4497681433 8342384435 5585235793 6098353820 5748400790 6056337622 9128986616 0745364386 8276253052 3396024283 8981748048 6442526085 9074383725 2893809488 4299400959 5025055042 7769696322 4165215530 5306949235 6498462089 6784538452 3023433527 2646194844 9584919248 7068999600 9099332102 1804253290 6482845227 3105706730 1040433064 9369237365 8079793935 8671793412 7426292235 4727089761 9939740247 2597829905 0657819644 9354139684 2692881674 4834895937 5025842774 6927896165 9101822395 6616976618 9170740280 8604250320 9230752032 5549706608 3523352015 5046771504 2606951526 1977889046 6334627708 7172183001 8677164805 3004241353 0430808943 0871185400 6192409490 3882803999 1837396294 0088868863 8262606456 8544917763 3091152762 4618906526 2978296339 3942889966 2854652765 7453680600 3919881614 1685623996 5773949343 9336548026 5732485566 0094767128 5725799092 8882920553 0361935517 5626646957 3494843195 7053158931 9882819749 9722598302 4995365946 4064372527 9315857732 0353067010 0993224814 2145972539 4032271017 5012935573 4002230749 9407875235 2710636639
• c₂= 281 6784322128 4808930099 1401450247 9547753513 4870398897 5844447686 0589021761 7813441520 6880209529 3244876988 8977803706 3480266287 9670143862 1190361626 9644716591 9360714730 2222827796 8604540851 8011187057 1384537964 9244898208 5669719600 5533877267 6222342045 7609370898 7519240915 4065154191 2475968844 7139220644 5622496170 8928368824 0111978355 5821727693 6046447288 3614807967 7406053276 9853434069 7787034221 7499109163 2923559178 9070787636 7657377011 6899457144 0229126938 8306987507 8452751369 4008181509 9625722206 2987917601 0570320764 6756424232 0886830265 6109729541 0714420052 0677150484 0334235145 2859731335 6467921285 6152070912 8205972886 5738901665 9123805258 7182939812 4267599453 2697710777 1424751608 5686040780 3124084755 4878053842 9168792511 6405942727 2615893982 2128522780 2827472287 3795343802 2075664096 1543592103 6504547162 1271799638 0730088510 8786800336 6440366664 7150219362 9031902868 3931541305 5739277268 3520661518 8771962457 4812416878 1599717559 5351679057 2444428846 4538711107 8326262530 2620443740 1546627554 7500430683 0950840264 5532937313 5105452675 3055323885 0084461116 4273191457 0593694455 3045618574 8769097595 2121135267 0143778179 3464250954 9192465662 4280974519 8342887556 1789330288 3267111100 1973736425 8977357745 4485908108 8670016316 1837068208 3845909328 1374971499 9161633927 0880297653 5318913683 9060067131 6665544508 2568165852 8938895527 0686500168 5430964273 3472242349 6428458729 5446581871 5704603360 5156347225 4762933374 5179360122 8418183275 1590566576 0272150512 2303692418 9004035391 5611804558 4062019504 0868721288 3219982926 1251263416 7881006344 8394671631 0935349142 1709846080 2066541816 7316981334 4358058830 5787612830 0936600319 5847135250 8798383261 3886234556 9988009037 1180512308 5129127274 4450341080 0664408514 4048631792 6101393809 3692173356 6207184262 2719968525 9353180978 2793667567 0280301137 8812465823 8847702692 0719055664 4854915809 5498098707 9862478933 9848131324 6597468234 8997101792 1128747066 7285486824 2575009822 1342763032 6244666677 0669438719 0618835305 7223215176 7666465274 5789515180 4740209452 2870887363 2410189650 7242338554 4406569164 7279838743 2720631279 8365114661 6620672931 3743740432 3175648348 9680337107 8952749059 8086337415 2815442782 3379102957 2334538871 4351188341 1011210557 5829524766 2040764287 0914351660 6697930464 5179592104 3541060840 1417988618 8918062814 0958717490 0082317132 9176443027 9304816395 1372790226 2574405259 9023644471 1603425815 1240227571 9371714953 5421967476 4559759206 7576660069 3885541083 6051287231 6721312303 0037581872 9975433077 2651126831 0170814262 9832070835 9286421027 9609523628 8809714870 1354069083 8205053453 3675800593 2692212725 0510085792 1055868169 3118220310 2771702495 9538749695 8740815187 4796989573 5428611574 3373401778 4191547134 8348456757 2908483807 3403262856 1967849025 6116184369 6069613249 7373849733 4430249624 5807107989 3691674010 1147777543 0118108336 9591131290 5874959686 1743487532 3384695575 2310251340 8460694729 0125565839 2577695213 7718360228 1324104195 2598647932 8723905627 5186990025 3029194054 8755842808 1542168101 8754353772 2982137344 1334565768 3913007798 7736924308 5257175602 2694271634 5674373573 2798616011 2284806226 9182638725 4629621070 1160534032 5684604573 7688251118 0431504818 0241084492 0245009061 4921815306 5194867345 0307801204 7058530718 5719355103 0637775059 9945872258 4913354527 7405237280 6430725004 9893451040 0494991865 3737431844 4269002671 8237608419 2399738762 0999587216 8391398848 4043157178 3124892852 1951068526 3044598074 2183442073 9798012814 5365834392 5273840841 8474860192 3485055848 7419326692 0611044402 2906650245 2938741206 4381184696 9103088712 1205076556 9511437175 3095713023 3620161331 0554840689 1669440217 4195843418 2297532430 6584330350 0405656920 5192361417 1141194302 3798523062 2091090808 9604056422 9935704629 9127160524 6539310769 4020300830 1715604374 3314542012 5456772043 4042855428 0938192204 6052393757 6479511631 4116818272 3395047827 4792189091 3556154759 8831667076 8527997412 0935070667 6169321899 0370070056 1233114475 8982741483 1553834349 3344254418 6164023456 4427905863 3752642385 5042791654 6113743758 7486768264 3383337088 4720641266 5054105077 2632754974 4221505412 7504965917 6340868015 5895812985 8247321899 6370923573 4332371756 9788697770 8564128917 8006921844 5804536686 3897156732 3859043653 8141238632 6778368220 0352251536 2100876326 7469647992 6157524226 5188052495 8639268502 7589806707 6471471118 8545938746 1648617554 3924281730 2830695571 3174926467 8293428189 6213953829 3535445947 9509804773 3980953169 3288718761 2991017269 3179791354 4181092245 4652284720 7862276639 1356316523 7886028787 5270194118 5892982248 8845628489 6071584914 7609531049 3903816692 1255660882 5298165681 5140552210 5973877212 2059162955 9417118230 4168404009 9712413150 2314515525 0906453446 3203210835 9876115785 9891044509 4065251259 2211057292 0787617078 2876705270 8126122918 1193275617 1577134567 8591408313 4455090067 2978386967 5033557028 3808107386 1035960782 1961114290 4447687688 4978973138 6495478040 9680051958 4949139554 5840558784 5537040789 6900095220 8257067003 3635102519 0138872568 8474255681 5844942488 6928584542 7203582036 6147277175 3220042077 7580653364 3597194882 4913107926 2276455860 0019961047 0516378244 2398277518 2310801460 2427276350 6908110870 5534315006 7370939491 9799456631 6951058893 0428208282 9347510003 8126802714 6172003982 5357984424 5972436502 5622671470 7216669819 1907352544 7054456773 3040699700 1506198187 8766215458 8273451686 9105154192 7875721690 1923335598 7887868901 4181217417 5308573788 2902117712 8968557148 7236458019 1401001987 8383409658 0023674108 8227805347 1840865126 2179527638 9021872556 7424650072 8211005467 4241345396 1956369702 2683376218 0446078807 2156614059 6663266966 5979514013 4757741826 9749544078 3493827511 6273926394 7947383503 5462408541 1066677463 7029178204 9600754071 9294065293 5123612059 7979469780 1339570013 4916503883 8843108906 3379581451 3720497404 2182721815 4433856524 7684437122 1554427451 2749593399 8209789775 8478071795 3289318603 0291714731 4117082653 5566276496 6686465729 3887085136 6588371532 4352622986 6966060108 9271774586 4873594385 9624767875 3497509946 4795566485 5884949506 8190590157 7453900172 1315084776 5854263381 6874045186 2609468583 2821863293 6339030553 5985645603 8395289043 2602597984 7157167165 4347729331 3110280284 1487711058 7422729419 5409174855 9731019317 5705861985 5614302382 1090583974 0342743523 8139001700 3960570138 6760826992 2894569967 7493971539 1843032504 7814828261 6589027192 9224492139 9198987852 8170230008 6275723299 0448614339 2351353124 3129738401 1618134416 7476893379 8150457300 1780725412 6914499016 4394872236 0942243051 4515532160 0194898685 9275347127 2339572222 5961938261 6493517557 2682379300 3791577271 0566509476 4227513351 8679720442 6931119414 4499336385 2694912535 7859925922 0718970902 5861798008 0600304514 4792728665 8205813347 6538051508 7921573442 0163469242 2471970455 8226582916 1522368221 3388245713 0471557303 5769411854 2122120494 3880509129 9809394481 7980616327 9967570781 7919888389 1846595032 3355350882 6071633430 8093070852 3108945468 0052007643 3395813485 4556515276 6053935137 9980877239 3658230163 0277764828 9980757402 9032436437 0872040185 3206880493 6662966617 8470066717 6141114621 1265637840 4314374522 7424327181 8750911080 0138606303 2288916908 1757064765 5948424698 3339633897 2883893590 9237158831 5323839854 7242671329 5029289362 1273870723 0141330198 8962806392 7370304590 1989195069 9262694687 7665549183 0654225476 0760452251 9478331239 6755882714 7436392666 0293047348 2787960460 8726397984 6567588698 0429189462 0910481304 2920877124 7574576810 2267923455 1699812561 7898017967 7188430237 0005876680 1667535221 9766413992 9063469600 1128012730 6223175692 1906502910 4740519638 9351928726 0237449503 1697357075 8956896162 7533144638 6566282279 7625820713 4510130660 3566911011 8616481310 6462470576 6553865309 7414450854 3220418281 6933213608 2020478592 1957163436 6276570957 6575792690 3298766477 6778922658 6845955925 6710079168 4933867340 5860032036 0928371337 2861185564 3305182087 3764634286 8522707398 8483758871 8231777942 2410431261 1173416800 7137913087 2906021450 3476765081 1075646402 1181016496 5612991821 6970517577 3393555146 5823804242 9583604863 3736469933 3026044969 2953516158 0798052530 6467663120 4265572533 3942966556 9088796009 7659592612 5649756110 6134498299 8126145708 3596976469 1253522204 4740019829 8108011920 6915012620 3125846433 3982474362 1925149517 7293413731 0348018418 2280504777 1280833296 5386479457 2491677511 5191712832 3303944775 7416558992 6607874468 3315493855 8518702518 7619716372 3583666127 7118862838 7386855982 2854652723 9052522940 6596508277 4517928236 4877016746 7451012111 3390970238 7884326928 0281161348 0803043243 6371735944 0812219257 7416619237 1809643076 5175492822 7665255832 8191534610 3312761800 8330956144 6152894685 9455739800 2542723600 7113646223 0704255219 8425061788 2195435921 4118763293 4422729565 5612451024 7804211725 7227281149 2469171242 1502030584 6633060415 8391162073 8917444867 4390385439 0872576922 0548596020 2705344726 7560056743 4746310244 7989252989 2313890692 3131149947 6828691809 9275408347 4678526172 1393856639 0463925231 7707520576 1824025446 7230545631 3945791812 4303109679 5122831835 0072124327 1656461222 3161477103 3588329748 4005916198 3735036176 4490980338 8930937282 6888767400 3328000252 8789372495 7291382921 9840923890 6672929200 1191096426 2705963635 3770040366 3382646172 5952858827 3276583584 0661751258 9564751099 7270939145 6710184305 3330445962 6091418004 5339333796 1806063332 8327450583 7419480298 6517340228 7794126941 8896891357 3984878971 9130883624 1079774550 1272998463 1982856813 1679517607 4970727441 0897923117 9327285710 8303044536 2284015894 5465235334 4189328487 8590099613 2318297544 8013134289 5587690872 8791811025 6284686576 9671738468 9670335883 2538577958 2693572644 3790694236 1263714832 6843621988 2772243870 0988727947 0090869602 8703034109 9536527781 9876347646 0748921310 7321215354 3174429636 9847769146 7558572698 9549724263 1193433424 9987361750 1111996722 8794898093 9635480189 6321942178 7756400676 2539757972 7207587340 0033638669 9398398774 9934741619 5421842072 5732189668 9954673575 1084827883 0954597207 3691192867 6372730288 4379427949 7490594386 0342987320 1778966116 5416324578 2426820689 2963466636 6144125843 3929827259 1342825509 4857942846 4488091833 1182283353 8242117232 8762814962 7865931468 0891817208 1838348091 0503208327 1699820777 7475554691 7945166128 0902352975 7742653485 0461158249 1201315276 6963812707 8852988178 2611360619 3956441424 9841539325 3231593675 4507430580 1791969792 8634345765 8794890181 6185187767 8607297992 7110840823 0974944880 3582738914 4880515793 8821601088 1560565900 3190413333 9997308736 0149141275 0544477563 2301891526 9368337854 2203618056 9377971057 1940221492 8010578061 4042031651 0507953981 9448126117 5568945071 2326351461 1659678631 5979767950 1151969735 0663828416 0435689013 7363089569 7462146454 7506073880 1128840862 6661354456 4656959172 7016306264 5314475572 3902651527 4751606377 1160401791 0952991773 8130446273 1923290778 1416120729 5699379878 9429965653 6024023723 7462009237 0786947014 2047465708 8796857681 1065450274 9962048676 1455567525 6798874824 2381387101 8247734695 0737135465 7442444940 9432697520 6411219189 0276204347 9643950056 1945030300 7784838978 7300814227 7036723318

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 51 (mod 63) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. Here is the stdout:

realprecision = 10008 significant digits (10000 digits displayed)

Welcome to the CHG primality prover!
------------------------------------

Found values of n, F and G.
    Number to be tested has 23058 digits.
    Modulus has 6328 digits.
Modulus is 27.44214267% of n.

NOTICE: This program assumes that n has passed
    a BLS PRP-test with F and G as given.  If not,
    then any results will be invalid!

Square test passed for F >> G.  Using modified right endpoint.

Search for factors congruent to 1.
    Running CHG with h = 11, u = 4. Right endpoint has 4076 digits ... done in 7844 sec.
    Running CHG with h = 11, u = 4. Right endpoint has 4008 digits ... done in 8600 sec.
    Running CHG with h = 11, u = 4. Right endpoint has 3923 digits ... done in 9333 sec.
    Running CHG with h = 11, u = 4. Right endpoint has 3816 digits ... done in 10950 sec.
    Running CHG with h = 11, u = 4. Right endpoint has 3683 digits ... done in 29116 sec.
    Running CHG with h = 10, u = 4. Right endpoint has 3516 digits ... done in 23904 sec.
    Running CHG with h = 9, u = 3. Right endpoint has 3393 digits ... done in 6651 sec.
    Running CHG with h = 9, u = 3. Right endpoint has 3320 digits ... done in 7993 sec.
    Running CHG with h = 9, u = 3. Right endpoint has 3224 digits ... done in 13541 sec.
    Running CHG with h = 9, u = 3. Right endpoint has 3095 digits ... done in 4116 sec.
    Running CHG with h = 9, u = 3. Right endpoint has 2922 digits ... done in 6193 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2693 digits ... done in 1041 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2650 digits ... done in 1078 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2589 digits ... done in 1316 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2496 digits ... done in 1538 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2358 digits ... done in 1986 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 2150 digits ... done in 3328 sec.
    Running CHG with h = 7, u = 2. Right endpoint has 1838 digits ... done in 3978 sec.
    Running CHG with h = 5, u = 1. Right endpoint has 1371 digits ... done in 447 sec.
    Running CHG with h = 5, u = 1. Right endpoint has 632 digits ... done in 391 sec.

A certificate has been saved to the file "chg5855out.txt".
\\ Coppersmith--Howgrave-Graham certificate tester, Version 0.6,
\\ David Broadhurst, 25 Nov 2005, with huge help from John Renze

Testing a PRP called "Phi(6121,5855)".

LLL[1, 1] with [h, u]=[5, 1] has norm/bound=7.67508157 E-453 and witness=3.
LLL[2, 1] with [h, u]=[4, 1] has norm/bound=0.894427191 and witness=5.
LLL[3, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=29.
LLL[4, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=7.
LLL[5, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=2.
LLL[6, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=11.
LLL[7, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=7.
LLL[8, 1] with [h, u]=[7, 2] has norm/bound=1.000000000 and witness=23.
LLL[9, 1] with [h, u]=[6, 2] has norm/bound=0.925820100 and witness=2.
LLL[10, 1] with [h, u]=[9, 3] has norm/bound=1.000000000 and witness=11.
LLL[11, 1] with [h, u]=[9, 3] has norm/bound=1.000000000 and witness=11.
LLL[12, 1] with [h, u]=[9, 3] has norm/bound=1.000000000 and witness=7.
LLL[13, 1] with [h, u]=[9, 3] has norm/bound=1.000000000 and witness=17.
LLL[14, 1] with [h, u]=[9, 3] has norm/bound=1.000000000 and witness=19.
LLL[15, 1] with [h, u]=[10, 4] has norm/bound=1.000000000 and witness=11.
LLL[16, 1] with [h, u]=[11, 4] has norm/bound=1.000000000 and witness=41.
LLL[17, 1] with [h, u]=[11, 4] has norm/bound=1.000000000 and witness=41.
LLL[18, 1] with [h, u]=[11, 4] has norm/bound=1.000000000 and witness=97.
LLL[19, 1] with [h, u]=[11, 4] has norm/bound=1.000000000 and witness=31.
LLL[20, 1] with [h, u]=[11, 4] has norm/bound=1.000000000 and witness=23.

Validated in 129 sec.
Congratulations! n is prime!
Goodbye!

The actual input file containing N and F and the output certificate are included in this file.