\\ To prove that N is a semiprime it suffices
\\ to give S, A, and P = [X,Y] and to show that
\\
\\ 1) N is composite,
\\ 2) Y^2 = X^3 + A*X mod N,
\\ 3) [S]P is at infinity on this pseudocurve,
\\ 4) S > (N^(1/6) + 1)^2,
\\ 5) S is prime.
\\
\\ Here is a 5061-digit semiprime, with proofs of (1,2,3,4).
\\ The primality of S, with 1690 digits, was proven by
\\ Marcel Martin's Primo. The ECPP certificate is lodged here:
\\
\\ http://physics.open.ac.uk/~dbroadhu/cert/S1690.zip
\\
\\ I would be impressed were anyone able to factorize N using the 
\\ data (S,A,X,Y). I have withheld one vital datum, namely a prime 
\\ of size around N^(1/6). While this is not needed to prove the 
\\ semiprimality of N, it enables rapid factorization of N.
\\
\\ I thank Don Reble and Phil Carmody for suggesting this problem.
\\
\\ David Broadhurst, 12 March 2005

\p900

{

N=
180508472604668618398754844253002010960981736846939214340720
032499312356836042771106861983071488987171317893675032978353
975674074530791470813185982901213449789876331223653122012028
948535278901951951805958966584873527699973681514014370965127
072935779690917258873244789364899785046238317712577794463283
982126673451748707334586207665742603889673579772210387064453
072871890697185677815472375879476205102162575742836185301385
838709683950530286230417777132315992725271862024152309490404
654253755593653529282688363354328397644820312813838409926771
744768211048368596157716500151596455543147743263133929918928
216156959170839663307630692852919209090931570673258081779586
813062702856585771125350560956914118910805201369649273609795
682529405544623190275312555495531492915541920090377675558447
374272691033008885779109885910639338593885613954750972188310
250291304064792916529443659929819034651292642950017385454299
934698876549075426579997889189546831867360067151100744458933
472117083127976625408657854419777352183280918163027090467797
800797974278495471013646839832251651378543239761715784418183
567706367015424814871238602122616058268075628630968561548178
890868474501842102284666687391629983621505662136236209365906
245565709310059764291826956786703983785716163157367483404727
876747457868385281405213568280147025581775599815231973620631
437258464458928916157906180626938352677437643023557602636516
049599219657815136732931917132735339430814811766371711178080
945660697086564338789976165648905976969022705122841737269475
562144647105012223659600765755017905040515131230880854041317
018084152752416836606752411167836505504310998050741384236501
094205993966593418904466694025052888429772418877940322937074
980396404533507081514262713758191508829477338842744937897538
909356943677044886246251344128128033193391874820202782034005
399243149518134626511749073107150850595406385065252106168552
237802886649751208412780336385744915450587457456540000550670
541091943405183867542248845343787016436640210482099261197020
904625129670894226560495688556646919113487533400750803650875
186964405557193222518454389425985897477149912542360974125621
684993779904872841178297718287112475275595825780989640379268
028879212790437638123195866573641086470505240167658010530436
658026255178321641450467644034093413920534472047477764312128
253689153690545168454079071896619377588615852000007939335070
492391360516634567220537460841450167577723556747861535661689
636720114297012669766715165274689425164633901525340802999237
991172164871349352603402721016836546622831697018487378007627
468891297774474618845143835529466406240801859414994302705159
397970368103169531303643960068582331095445133314713477574668
304418678652048934981746262223068393027884583906091724671027
840998899326521864271124424153429067256435480890086793903952
492944566552550029090360895691633118772439791630765239720955
091531219122042996010643499985852077118220676142768945201487
972359191702364092505780120275917136408711486258076386891138
598899963037781271741755368827468760696200803182555862401085
855827973617566516398929197864061409601895590841704064479092
386989393571889078502671948944734705338871021765458417263843
249117435866067705907002732620862534844151518999454720856596
226436363905512474247039035390733482909542319743743058251931
372707157757401322678865607134088453854101764329551281257750
969963086720853953939972003895016010841126040273968330203155
975065574549628761482153685319102069498543812952345801757880
612281705516948615750984312325746728504758757698300746301607
241174751998372122170162355473517968747302780068580614901115
844797122890688276506117887542798267332472365146082625964879
898128920118311741981201601425647442862147105703377914795147
241595971830413829104072027693571715800164804046885230244281
704010231835569199867784593078065680009393080974463366939329
052240598947986101108959341676528319302382961497732980874997
651278410815362578270838096304384256312954467472159707300308
321116926632872248243464362596133520823009248071406737658806
269614731750825507935092587882975969451756088648806720342528
433735721561928129463663730527309845844310229739876273937351
864288073658232288297345592228802823224134211240743570964695
579815076855544891274078708886314230283523860763254597261751
328370591434473599159492283262390933527103048867501585038790
337718713395426285322255239980637873972143384440750671592659
227670727792555493410431196562150372373054061806720410888825
245498507168408378447774423214408773502107746343214065587799
126260572417386541395139373668724510520039116383914416874684
774837408760325835963714630387148146349884336789312381894721
853611958684391065161597877133695067038106254153842940074564
927346439602092154637378525633073564224741778254022891474507
385791592881828234089273306431842865701496972040234864811210
653138106065650008517477721475127573558204122824598569562074
633721600913529305181065383614852039752719005013664340392111
039425189047073788703414037767303111493688285333180602862869
460268169125794504853470610114609703931739129999117780066676
222913456036252138776980959082821433373917514504034283513013
863809074861468886601;

S=
726379515624307740477352784170733016534101314167599854437403
287905135802556357338487586001297913580643959460025237580079
736466984375373872365676770146606182659644856339724184196886
355219833989805530588246512468402026416784596511917279310386
315263556923295581602287324841484137541605523176940168962363
392066474364654513484974379611625256652475123089448766892801
721098948715471750022019141593115039748744160748237091912303
601735625310823257054502484874770604810183371407139312019282
097558188855846907126077087724474520512228493826972101145654
875035276656999413599415782564577532226946341855867389031550
786393121424428645597810915663909502294110202426118542463046
041494127633562908902068257447760288369297307220248751741945
203860278641121731959674428976694195987704233967289208485231
420293469978545907510979982528275132494129210579740445231524
962598472757209079849226516152184911829770752544811928145079
438232612177831954452311355573238866570499085063618392531500
696085253333334587540667260701707168539406413641611943202164
653073085498186593104002098472480932050710517429106486993547
500336774123504570721472184574941012087783607200437171132914
190397414249713338309494124767134203980183415248195054358242
882463549167160797291221808191309980356129816524932799625360
838135489748586502633241263886067180789508865948898708218462
290193015443887196377499829854873690656019002818708960712748
934799517865602673963852632137539409502335409409463420033839
317355868025755138783871350883510402129738614015590904810235
303173268099468794004246619523986450877500368422808366686146
640385838172114450068735673287811150929290525997772417726223
526117391550945399898135229021950362524750707954217126902891
1691642037;

A=
837583131051489242930099918707213732749543024958598440966025
252791570195010005286515628704159433059367205873871034367829
327567384422798427192850446453384021727050978978094485590626
219369023990230378754141985586616364314566655758825381861611
475732749184645405909619455346057196950875237994413340655515
004649127777103913816430510362748463782908586919598032292011
384139181224501225661007300671977817396743075659601918866573
547728986606434999329648130078934851580528156802282294837343
020797592681534838923665364122412703527113148366972282003344
812463536174728705391996233896959646314079633538349912800237
801016110796747940695999637239051512046002824412187124480931
954779431690554974100373207957553745876410473747689663019229
838592646678884923516247351825060319191219216180793711887186
338847576864045760910188623345544228974991600776449000067400
038030101512544834156766597687870202319007190795206266030168
153132555951158962105468404656225459580718033433171423209813
267663912748880101927059262119816410189667174528041682640020
586723899052579547500262674627238956746448407229242468241352
065958647159014065709395337076499834910517086369751281241993
945925004041979905221350038235470930676228540124514485487281
203597457251035149645093845262400416135328063399865578238815
447166655141295742248614707047671957561736235853706476283250
752132873606715011190992482560027843568437384134234559363038
452812386564499658195856404987185685515540703820610080230200
783591617896880331475768028782320114985140278555629688230889
407521541580464592082367979910896695717134584884526509674648
179860986986823754791462537593516120544738176150629298691419
959872250374517279661429314020503041362471649112843935753956
992188226591000148480104751234610413452498800604033028760570
759091244231860237769008028809218510778668831337130257993034
816405661360130154437898065926899764123731598863808105869268
070439066460889390848209484894750329378950632857929927889681
599110497431364078110391511101666513902714823659201992118463
852873952048027411253894241621853786142534251769417332127774
077570235798071719492633793275602312829444601754708111448297
507068189551221028125656263581513380406421266451499555982348
373843879218541405961026959699571356199128369947295002208781
538761732094022628547382899314710770078081640845712924373946
736607608602321637782040274849953853548058204535414911047970
242873433557056199766411402642718946044044711575919432559188
350065446794645981633489365359903454334652417194136880781790
997191881308227491780804907088745769668890748876857184288094
520695325536786564908087492594853143960847126162342401529804
712990028682440597558121320934910133694027443849130640074234
040466380397467211500309912392465192080369878365180786217064
989339942321143892927678968403751276894016038503586775899680
520862476752112498264522117428899399864384144423722308536482
489696061414559440852816865690536461281576930945187977590976
984380567177279454494640681593835488391084088555769706256909
390941793470176216895814276236540338926040122908845771132866
843130241893282179906898672367312735559824830204686985986327
241670142137979310160174193643123414314317195458127975860266
263934278566446459699231207493660912911472190667054904640809
885383900574104768985955813589333775154270726818077085789082
560041313724466594858867285614375621202463879321642558885962
451825015840390984461066047221759767391321752422794177318977
266991587333195339706488033901030673051333883844207681074876
220192287875676270013555001448839063116610480266783274369674
024356634230572847658268484276057851757043079352115002669905
068881798307351851726692217502726426086444162757738752968378
965756063950742312348010552385635935867052200472060056560512
335898659544169640764743596561908612214686298297287670415787
838887233833183778307107762877738721908966950832599799887911
709143459275223601468936655833903926486597507037683397098238
907568491268906336310578093759559950970198337462820439306019
900586780214463989421924462429419357864905559014858227164007
093699941344317231217974699799709978109116184927204066998862
328017838075735500352934702128692687925091088132984436461999
903562402142938975868015817802590627067393677334857675618986
903636172165729604271265901230554759045512342895385071441422
024646236464766317973352598007885803676088146595031620660814
113760333748487719348452679212843494865161355503010155199396
369570922991099492700323176142246537501621196533353220595275
828915265431002417961619406478459314844816977035604782562576
187498154801338560652771442599965303789158468910981292290339
540855596869718684820962861974790956940166756084517056796638
826886586208750423555683599701333990069177028106138622354827
496888881714864475367864232728862370175599843275323883687018
716934509484610858051224393687725281296160202334508327708363
264586911563084875782537289152209271474564316559358745148981
272939105578602026652931123837989078850950269575522724288870
014006812486643709018992610922800359172053581421249623276112
029374547528298127821005745584408204870929403308037385629789
242800113857364244437585394545339792169417925695544764787610
91926208878160000004;

X=
916584430045716835998383368300247050823646936773452104467397
263804733550334916822760775553402428460427833781775248314476
630023521060188594817180684469360666245474875441351163376413
434799858565565453479283168064023295913661606605153947223291
203448245705718122534237847060110165696578381827872441016795
154758099918592013865919723778756040199276754654822532150260
198233883653773608583781743117339140051423420198747173016007
960889487108840232522202382495214225741979841224864565946666
672166989290946750829024829080659426350027424699383962701031
281319149373497274745423805537217632297251418171766745181764
779012272010716090598105123445196253390989289438277593803617
280919187868314407366789016540527048293664557071051626817762
373330597749403475502075051824179834517355153962298890843489
112044768519583626812561258933647578368778099171236728804836
725311894613683007530758249492589649013867363498586065327098
688670508752540431811769559445815816036603807954378675161519
822818586488509404901622922008426820558149874655000969610191
037317401275559401169572976963341208814987644378077153683177
600466117725238659791144187501140767550917182938808591629342
478761920658617415161072023130084639896631557259943499001201
342187249780756503072636726347178045876145773771782874611650
359375842121861797376680408351599248454261215963873569376571
246148526794855282016742554483147793512975101665786971525587
418436449264093406124851179089286702505976354277479148049429
515206967736379347539698579408679229929199977781413711220943
518783912325348824320895278911730034402942394824623797778233
702449799534819783106143490301404154927353721740019138984378
938534837676913617904123511728830433837916243918123223137763
530342141801658492111852583362051425258442722966585975839070
609259391182347722505326779981072995189606232088552982611673
082748163343106680920308968486054595223794285004577961082583
511002918764029979272210113991443697759240449246217709156225
936491537393280900823953132589471492388589085148600970227543
253930586828449683865009017442237217231619211969792743319281
268144616839062490051364584587564341984984385007642497320438
196107583090755523801033979741304995581954271369972051563347
122205651872467639576010179070499382016304684182928502221402
882852096415926027958921304582877730101564840941255109611734
806939110914917043773698738361207704848771996699876225138749
604687383971721344495498205327290753179343910214204579878220
783015843032425445859772689623908910349686986233910367587327
757206092768655774331835956746142709326888571159217201412264
522665112225211417657518882005383843473312386325154697342437
573347970766113763240862849661335464413613569943778818853518
685882682071263684032945346895173804982385827844392760791696
254212193228802273552047766171231718088742537971307000443563
680511455601642826799169028472241436874610056158046487354064
342438685002639894380606864687183792437125729253802875581585
823679411705480290844598874244424308525299484903846192191117
295138672172623328943727475422500898532390694334259498289307
514072558784065569006552687715998638194614341007892618774192
360381184096328069853883156132224587974219698258446815904789
521713915827721883559196196673404193270370738351625875134161
013780255010022054029870890806152003049234433247123540342974
431043148719881342467517479172242586624797441662547213585288
501684882833154349017718415668851348443738223303555113768746
605197598972436598559966749322349949247254513727642495232843
178481275124773540192206866567202869369930419942778637852525
127792965709978562190325903274452159173662916915173095738818
085623165227549403193448493004865958623299151942101033095817
106778813641252227874292089116411211863765859428257173899170
072312786958025174107456356139657944295075106262603763023033
761661703071048228989909094824829700202952069581030145846080
624244187581883340097346930196350452017004819857907349559245
315926975977646952618392833145400985225817486008943475319629
318750437097541832910162137578473837245044258341738118388848
950505955704743591542048394347656349034116624829784084909613
719046003454353285093047340939711437281322086435881769173410
346719318571696177925110387804718726377680008981486432052038
990514629182614819825837260378655220560254011006751840170987
727620385463335740814056716122143931995348202567284495357029
835461903716354524211185689740417690603658067406085306163883
138115053434476688800753183687722042591870283177442694373969
065515302845534953881930645764700299647311891207527223218786
736131074801782181043766834401437036904653667158017997020596
813080077632780168897590489793092407370862689695295663050428
602073188854454967508987776129572408776872270981705901412192
225832884282302824761464188976608482769402022220320082626016
294703471069669412825924059926937357534535940017079106914111
242663794809704505070358739567451015302914507785210098688451
229927007350594450049205112387624636114462767943109004259429
327822188087452869445410261010715868754815486167819215643263
392509184713855124774836854808667865033122017070600880412875
773889427947939640856826984688348517953162353669567628692243
39071950106777593182;

Y=
159302718197487080235983621519281606244849593813947033004904
707900315123956214463607625907393837413909507027440208299738
696880784318460813540504032076213970927709162800931053221747
899475975697950511668508535596568878149164045505594052164946
215465167074898955146727254480013055429358926230410237968738
588509367231046705267810032197746440053742933980855753532769
699390736223439728012898201779878471475485119682674403979088
050685373995052465557743488746142747022389965269782001834011
473215734496225891166259686400118725911075325822240398435234
501688035777982162911894929757033598758071948860341214409527
872807721575672100017938593087813674122896108148665202565996
639477115623563150069341099938748724449075965541331528074921
265124354995580712235864309273283664245201692378917727185751
014913300628127145621082605940701383564125327109964934992217
770237431340985590328925018436783196293958014324574936765871
555520720988734046619009402380134821212427149719413250906060
007690745420987586533949161542999031161444061575868534597640
084569724818850082216719580436323725655379378004664527223459
556051287422046380055677414833450139390664792123207290827565
156211413655392104239393429786478981150924667653196733755260
346785432554698525459618788739267208040388729518669825305860
108285915661714586831049364298347819402695069970674180324341
043030127276041446251145965250981297278029928069612966011764
891082661171680231713680566911730428567169524306521553014382
671666339032573435202718485405197408743308696154521261809426
720339190598999622846587819191105587817479089373711625167429
122986111269986665414025678741876821821172744994548082795737
393430458555112129266122581847880925182126690643979067181593
474139036471992749583021508485344762533282264400027161758841
300257649950650601366508284009485306897350604135925456567260
670912035137854129523981819524017026335490540972040285117374
353586704978055462503683983899753199533879447475221008491722
567384263070659144843432541144998752775649871825462960302852
070955926006778611945237249525442346781024152026258694256016
287753578214898372885974708766656014760492216147707409657788
286473286282348560004147550718618631795033431284362409844411
540529391758764608026529098644638489224083083880256769240351
998941933880975459962910668999931521052389578186711312109836
385258107081263612705120563417689914933935487590305374884922
354813211762545288453249429856801673132627775758301893040743
670592571135064169630823254523997869254566287631114988810210
980223153938347631958571822867330809239534071393808067656431
746235633463914785732046212366047361672990900827295483362045
352058845335744355558029312926570473051350688845880442920182
097715986156581569697337963885116125346070936188189761678926
330016906711502487212440663752706958170628485550857726897030
500483582611930315461410628214920468452942234083894784356839
982142132632897280676499262247964833813597385155152401131068
774542850862522822891285096019650186213335815877322796342098
468248655937222677204941763718782255763788565410741640658235
992993005979719160052410913795403886143151438183050576419569
653440451147727376131219030630260605453227514156543471334971
978089134168533562529828582720265824102994081387519912277261
491973171962029810402122823701521194016633762721539574439778
244545054733405985367166379552487915221744781672249875007685
800770114847185996257483954821512833381985494766763709080620
382370335905970134753381122189275559377816695680306705424346
525984535720807243072658084896558820325146434726231019828137
405156429731034789316782677689983758419842628104147659529335
060520536535361558755420677770469417356442637200923945550306
091568089259968490825439919132042747995614617217594744843360
857216554626251803523848594000039552763360561166195348984029
425446492839486374862536511670068112297512931453069425205139
475963523229064788551818640468702749656951122549621428435199
039194830887160945977700588639865617903496777015726070512852
223352959443345356079985110931512043761322473947242907842839
938676738643444756343815421547356914929418723114370126071241
853596196025862763757878357320523675511882190097539223745823
956712926437464976503092533091644316680445516392048264059169
356121905897737365220363432248996436052277034493148562596266
909276216147348897153013836758285889440525072736359625136729
504914124143228671384415218360351358534165371708836578707686
949907720076423285458729746990628336119152103898116826710286
632337121751601043476309923123456473551920938704460532224350
317529932450154551744647503956286590974775506154570290542064
620540310866454707475027055566600068898310321590737763242349
073209427392605182578242923329433724780669431863986367309470
916129554234903912261050690106744961310300937649470128299968
735576746842185780721841700271625138519191631272336633744967
669193733710624208674324953503704563736264084763928744605403
832434212636527186517216536789016504866824833183853090532837
985007581630952785185301457324762320157285071528709879903209
871379160204895608797920950321257604154477464999500510387640
609897855266290540725485243856871090707720851267233525330707
728359134415592244089;

if(
Mod(2,N)^(N-1)!=Mod(1,N)&&
(Y^2-X^3-A*X)%N==0&&
ellpow([0,0,0,Mod(A,N),0],Mod([X,Y],N),S)==[0]&&
S>(ceil(N^(1/6))+1)^2,
print("If S is prime then N is semiprime."))

}

\q

         GP/PARI CALCULATOR Version 2.2.10 (development CHANGES-1.1169)
           i686 running linux (ix86/GMP-4.1.4 kernel) 32-bit version
              compiled: Mar 12 2005, gcc-3.3.5 (Debian 1:3.3.5-8)
              (readline v4.3 enabled, extended help not available)

                       Copyright (C) 2003 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 200000000, primelimit = 2000000
   realprecision = 905 significant digits (900 digits displayed)
If S is prime then N is semiprime.
Goodbye!