(20:31) gp > p=nextprime(10^100) %1 = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267 p is probably prime (Rabin-Miller); We want to prove that it really IS prime (21:11) gp > factorr(p-1) 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000266, [2, 1; 3, 1; 334667, 1;4980074721041114500881971233096381378106197105381369142062607507363040475059287789553994468133, 1] not prime Disc=3, 9999999999999999999999999999999999999999999999999807775766934751382135027534546792714285207517367087, [82699, 1; 120920446438288250160219591530731931462290958778217484803527669637869079765590234376646455308013, 1] not prime 10000000000000000000000000000000000000000000000000192224233065248617864972465453207285714792482633449, [3, 1; 61, 1; 139, 1; 19183, 1; 63577, 1; 322342486862501606273959309563465722303008157836543134625342383564401465255382678100747, 1] not prime 10000000000000000000000000000000000000000000000000048285521767183031891098232208632948053268377259028, [2, 2; 7, 1; 13, 1; 1435069, 1; 19143697949386038251451691502309277482457308653819157949899868855392501168152677011739913483, 1] not prime 9999999999999999999999999999999999999999999999999951714478232816968108901767791367051946731622741508, [2, 2; 3, 2; 109, 1; 127, 1; 20066299052068032780306131458338349908096350341528312975025951377286773302527132379485714263171, 1] not prime 10000000000000000000000000000000000000000000000000143938711298065585973874233244574337661524105374689, [367, 1; 27247956403269754768392370572207084468664850136240174219921793094239710828973418458685726223720367, 1] not prime 9999999999999999999999999999999999999999999999999856061288701934414026125766755425662338475894625847, [3, 1; 7, 2; 13, 1; 19, 1; 275413809248395714561128094962681428846842380676963178861678975857611780158273580260055040785883, 1] not prime Disc= 4,7,8, 9999999999999999999999999999999999999999999999999846413802233598356053012388366347872541731911220274, [2, 1; 1697, 1; 45377, 1; 64931043426674002489378287726569246639776297491392035821847823466336565546923245415310198073, 1] PRIME!! 10000000000000000000000000000000000000000000000000153586197766401643946987611633652127458268088780262, [2, 1; 3, 2; 43, 1; 733099, 1; 17623672438274876087694731402772104277028086138293517326654987884807198746435993188788022387, 1] not prime (21:12) gp > p=64931043426674002489378287726569246639776297491392035821847823466336565546923245415310198073 (21:12) gp > factorr(p-1) 64931043426674002489378287726569246639776297491392035821847823466336565546923245415310198072, [2, 3; 79, 1; 102738992763724687483193493238242478860405534005367145287733897889773046751460831353338921, 1] not prime Disc = 3,4, 64931043426674002489378287726569246639776297475315202349730634292316114132187925238365729700, [2, 2; 5, 2; 3181, 1; 16193, 1; 12605538319507036145703836913662700093159953726850159628382866328386820874371536309, 1] not prime 64931043426674002489378287726569246639776297507468869293965012640357016961658565592254666448, [2, 4; 277, 1; 27017, 1; 302857, 1; 1790514702005210308542310371141026329648182105541471985561070973883801178887081, 1] not prime 64931043426674002489378287726569246639776297492514354500525307432323087623528774843030610378, [2, 1; 13, 1; 1709, 1; 1461291880692127706021926626605060238551026184734985697900826111363439879901174209907517, 1] not prime 64931043426674002489378287726569246639776297490269717143170339500350043470317715987589785770, [2, 1; 5, 1; 17, 1; 381947314274552955819872280744524980233978220530998336136296114707941432178339505809351681, 1] not prime Disc = 7, 64931043426674002489378287726569246639776297479407177239778339756146051803924297568085905024, [2, 7; 7639, 1; 66405783056799403645538404616287765332275471142540721584732069556864907673538234683947, 1] not prime 64931043426674002489378287726569246639776297503376894403917307176527079289922193262534491124, [2, 2; 11, 1; 29, 1; 191, 1; 1129, 1; 235979566172200817024153262469450701458163459620496056925560452372380715390749908341, 1] not prime Disc = 8, 64931043426674002489378287726569246639776297489022240684998738544099231528915387725396958124, [2, 2; 3, 2; 15443, 1; 116793375327681730106733521348344173627346977575280854837140773137234474319388481882113, 1] not prime 64931043426674002489378287726569246639776297493761830958696908388573899564931103105223438024, [2, 3; 3, 1; 11, 1; 17, 1; 14467701298278521053783040937292612887650690172406825079923553562516466034966823330040873, 1] PRIME!! (21:12) gp > p=14467701298278521053783040937292612887650690172406825079923553562516466034966823330040873 %4 = 14467701298278521053783040937292612887650690172406825079923553562516466034966823330040873 (21:13) gp > factorr(p-1) 14467701298278521053783040937292612887650690172406825079923553562516466034966823330040872, [2, 3; 3, 1; 13, 1; 272539, 1; 170143860124541585882921871841402572349451212068435384123377326596170828373643529, 1] not prime Disc= 3, 14467701298278521053783040937292612887650689951397268441502818296183891905784515857586159, [7, 2; 295259210168949409260878386475359446686748774518311600846996291758854936852745221583391, 1] not prime 14467701298278521053783040937292612887650690393416381718344288828849040164149130802495589, [3, 1; 4822567099426173684594346979097537629216896797805460572781429609616346721383043600831863, 1] PRIME!! 14467701298278521053783040937292612887650690200636541559582041147806330549662027932452432, [2, 4; 904231331142407565861440058580788305478168137539783847473877571737895659353876745778277, 1] not prime 14467701298278521053783040937292612887650690144177108600265065977226601520271618727629316, [2, 2; 3, 1; 1205641774856543421148586744774384407304224178681425716688755498102216793355968227302443, 1] not prime 14467701298278521053783040937292612887650690365186665238685801243559175649453926200084031, [139, 1; 2053, 1; 50698578666343764534031758883446974904774169280914279642305526720185500248640964793, 1] not prime 14467701298278521053783040937292612887650689979626984921161305881473756420479720459997717, [3, 2; 7, 1; 151, 1; 997, 1; 1525411016849404626555271927133509525491294653394324139364514850287618497295705097, 1] PRIME!! (21:13) gp > p=4822567099426173684594346979097537629216896797805460572781429609616346721383043600831863 (21:29) gp > factorr(p-1) 4822567099426173684594346979097537629216896797805460572781429609616346721383043600831862, [2, 1; 3, 1; 803761183237695614099057829849589604869482799634243428796904934936057786897173933471977, 1] not prime Disc = 3, 4822567099426173684594346979097537629216896659875661640387101960491252140159906819999239, [3, 1; 7, 1; 151, 1; 997, 1; 1525411016849404626555271927133509525491294653394324139364514850287618497295705097, 1] PRIME!! 4822567099426173684594346979097537629216896935735259505175757258741441302606180381664489, [19, 1; 253819321022430193926018262057765138379836680828171552903987224144286384347693704298131, 1] not prime 4822567099426173684594346979097537629216896852655501799149349641533961754647009690042397, [3, 2; 535840788825130409399371886566393069912988539183944644349927737948217972738556632226933, 1] not prime 4822567099426173684594346979097537629216896742955419346413509577698731688119077511621331, [7, 1; 103, 1; 379, 1; 17648337655580140762406167698401654215293537424038803283381369241996536941579518009, 1] not prime 4822567099426173684594346979097537629216896880885218278807837226823826269342214292453956, [2, 2; 3, 1; 13, 1; 31, 1; 997222311709299769353669764081376680979507212755421480315929947647606755447108000921, 1] not prime 4822567099426173684594346979097537629216896714725702866755021992408867173423872909209772, [2, 2; 1205641774856543421148586744774384407304224178681425716688755498102216793355968227302443, 1] not prime (21:29) gp > p=1525411016849404626555271927133509525491294653394324139364514850287618497295705097 %6 = 1525411016849404626555271927133509525491294653394324139364514850287618497295705097 (21:30) gp > factorr(p-1) 1525411016849404626555271927133509525491294653394324139364514850287618497295705096, [2, 3; 3, 1; 129023, 1; 201203, 1; 2448353086458053125214949133627405541711622811307039605231581764365591, 1] PRIME!! (21:30) gp > p=2448353086458053125214949133627405541711622811307039605231581764365591 %7 = 2448353086458053125214949133627405541711622811307039605231581764365591 (21:30) gp > factorr(p-1) 2448353086458053125214949133627405541711622811307039605231581764365590, [2, 1; 3, 1; 5, 1; 7, 1; 397, 1; 557663, 1; 52661401991368270881876111101724384248928785254695075868289, 1] not prime Disc = 3, 2448353086458053125214949133627405443725060911972612158558962527810275, [3, 1; 5, 2; 18121, 1; 1801484897049870776237477058754966020068841610634153493044138497, 1] not prime 2448353086458053125214949133627405639698184710641467051904201000920909, [787, 1; 9769, 1; 3430369, 1; 92834278894283359781358312336656821975627728272050330087, 1] not prime 2448353086458053125214949133627405578703465316559083249240587715357388, [2, 2; 3, 1; 204029423871504427101245761135617131558622109713256937436715642946449, 1] not prime 2448353086458053125214949133627405504719780306054995961222575813373796, [2, 2; 19, 1; 373, 1; 2053, 1; 42069047180334462639842211823178734894008168088737835692352459, 1] not prime 2448353086458053125214949133627405602706342205389423407895195049929113, [3, 2; 43, 1; 439, 1; 14411147524960140354310943556399649206891056167054695648997869541, 1] not prime 2448353086458053125214949133627405480716903417224655802567968478802071, [7, 3; 31, 1; 230259859537106472793656459477796057624085715905638653490827469087, 1] PRIME!! (21:30) gp > p=230259859537106472793656459477796057624085715905638653490827469087 %8 = 230259859537106472793656459477796057624085715905638653490827469087 (21:30) gp > factorr(p-1) 230259859537106472793656459477796057624085715905638653490827469086, [2, 1; 3, 1; 23, 1; 347, 1; 3637, 1; 1322106295281387195202989716042768066827155263993246525173, 1] not prime Disc = 3, 230259859537106472793656459477795155822366001179557388604402575404, [2, 2; 607, 1; 94835197502926883358178113458729471096526359629142252308238293, 1] not prime 230259859537106472793656459477796959425805430631719918377252362772, [2, 2; 3, 2; 6396107209364068688712679429938804428494595295325553288257010077, 1] not prime 230259859537106472793656459477796224192706193012356936506279715393, \[222877, 1; 1033125264325643618649104481295944508373256069546686901323509, 1] not prime 230259859537106472793656459477795891055465238798920370475375222783, [3, 1; 7, 1; 10964755216052689180650307594180756716926916133281922403589296323, 1] PRIME!! 230259859537106472793656459477796792857184953525001635361800116467, [7, 1; 13, 1; 193, 1; 877, 1; 1117, 1; 13383409532700412298469816962571153467924370308280850801, 1] not prime 230259859537106472793656459477795322390986478286275671619854821709, [3, 1; 601, 1; 127709295361678576147341353010424471653348019016237200011012103, 1] not prime (21:31) gp > p=10964755216052689180650307594180756716926916133281922403589296323 %9 = 10964755216052689180650307594180756716926916133281922403589296323 (21:31) gp > factorr(p-1) 10964755216052689180650307594180756716926916133281922403589296322, [2, 1; 3, 1; 13, 1; 140573784821188322828850097361291752781114309401050287225503799, 1] not prime Disc = 3, 10964755216052689180650307594180573729588027314066056100240939981, [3, 1; 7, 1; 409, 1; 468913, 1; 2722476030408577783091597128496945235510150863795878033, 1] PRIME!! 10964755216052689180650307594180939704265804952497788706937652667, [7, 1; 23917, 1; 65492896362137446649724986973885518992861054913108958403393, 1] PRIME!! 10964755216052689180650307594180760000670598475781439061168518332, [2, 2; 3, 1; 181, 1; 26449, 1; 36073, 1; 42061, 1; 60259, 1; 2087594227325954438586208526268953632509247, 1] not prime 10964755216052689180650307594180753433183233790782405746010074316, [2, 2; 19, 1; 43, 1; 3355188254606086040590669398464122837571368969027663936967587, 1] not prime 10964755216052689180650307594180936420522122609998272049358430659, [3, 2; 4027, 1; 9151, 1; 33060258594802140098013983249333033726597951744465590063, 1] not prime 10964755216052689180650307594180577013331709656565572757820161989, Mat([10964755216052689180650307594180577013331709656565572757820161989, 1]) --- (21:31) gp > p=2722476030408577783091597128496945235510150863795878033 %10 = 2722476030408577783091597128496945235510150863795878033 (21:31) gp > factorr(p-1) 2722476030408577783091597128496945235510150863795878032, [2, 4; 3, 1; 7, 1; 11, 1; 1181, 1; 623709278220218801453111570028551184590740215707, 1] not prime Disc = 3, 2722476030408577783091597125449504515763659322626005732, [2, 2; 19, 1; 157, 1; 228165942877017916786087590131537421703290254997151, 1] not prime 2722476030408577783091597131544385955256642404965750336, [2, 6; 3, 2; 277, 1; 997, 1; 1041343, 1; 16435118961512181507083615888452768926583, 1] PRIME!! 2722476030408577783091597128924190841479334988437778921, [31, 1; 61, 1; 103, 1; 2287, 1; 6111800175704359143512590779354213451814898571, 1] not prime 2722476030408577783091597128069699629540966739153977147, [3, 1; 7, 2; 13, 1; 1424634238832327463679538005269335232622169931530077, 1] not prime 2722476030408577783091597131117140349287458280323849449, [139, 1; 19586158492148041604975518928900290282643584750531291, 1] PRIME!! 2722476030408577783091597125876750121732843447267906619, [3, 1; 43, 1; 21104465352004478938694551363385659858394135250138811, 1] not prime (21:32) gp > p=16435118961512181507083615888452768926583 %11 = 16435118961512181507083615888452768926583 (21:32) gp > factorr(p-1) 16435118961512181507083615888452768926582, [2, 1; 3, 1; 9341957, 1; 293213348507744531955556633520021, 1] PRIME!! (21:32) gp > p=293213348507744531955556633520021 %12 = 293213348507744531955556633520021 (21:33) gp > factorr(p-1) 293213348507744531955556633520020, [2, 2; 5, 1; 17, 1; 29, 1; 47, 1; 587, 1; 18229, 1; 59130019002889459997, 1] not prime Disc=3,4, 293213348507744500317773855426600, [2, 3; 5, 2; 61, 1; 24033881025224959042440479953, 1] not prime 293213348507744563593339411613444, [2, 2; 13, 1; 41, 1; 97, 1; 1417832094677784586339429661, 1] not prime 293213348507744545066776825292922, [2, 1; 569, 1; 4397, 1; 13109, 1; 4470081552329963272853, 1] not prime 293213348507744518844336441747122, [2, 1; 146606674253872259422168220873561, 1] PRIME!! (21:33) gp > p=146606674253872259422168220873561 %13 = 146606674253872259422168220873561 (21:33) gp > factorr(p-1) 146606674253872259422168220873560, [2, 3; 5, 1; 7, 1; 523595265192400926507743645977, 1] not prime Disc = 3,4, 146606674253872237047666735940402, [2, 1; 109, 1; 929, 1; 1733, 1; 417717790017767005514777, 1] PRIME!! 146606674253872281796669705806722, [2, 1; 13, 1; 41, 1; 97, 1; 1417832094677784586339429661, 1] not prime 146606674253872268685449514033824, [2, 5; 13, 1; 181, 1; 1947071215653849722235570469, 1] not prime 146606674253872250158886927713300, [2, 2; 5, 2; 61, 1; 24033881025224959042440479953, 1] (21:33) gp > p=417717790017767005514777 %15 = 417717790017767005514777 (21:34) gp > factorr(p-1) 417717790017767005514776, [2, 3; 7, 1; 19, 1; 443, 1; 886211981741388613, 1] PRIME!! (21:34) gp > p=886211981741388613 %16 = 886211981741388613 (21:34) gp > factorr(p-1) 886211981741388612, [2, 2; 3, 1; 73850998478449051, 1] PRIME!! (21:34) gp > p=73850998478449051 %17 = 73850998478449051 (21:34) gp > factorr(p-1) 73850998478449050, [2, 1; 3, 2; 5, 2; 164113329952109, 1] PRIME!! (21:34) gp > p=164113329952109 %18 = 164113329952109 (21:34) gp > factorr(p-1) 164113329952108, [2, 2; 389, 1; 105471291743, 1] PRIME!! (21:34) gp > p=105471291743 %19 = 105471291743 (21:35) gp > factorr(p-1) 105471291742, [2, 1; 19, 1; 607, 1; 617, 1; 7411, 1] PRIME!!