Mathfun'ers, Ed Pegg: Long ago, Ed Pegg sought an "interesting semiprime". I pestered him briefly, to explain what he meant by "interesting". He never explained it, but all the while, I believed that I knew what he meant: An Interesting SemiPrime (ISP) is a number which - is the product of two primes; - one has a concise proof that it's the product of two primes; and - there is scant hope of finding a proper factor. (Never mind, that "concise" is subjective and "scant hope" is temporary.) So, I figure this is an ISP: N = 23540246381953690964846159708843398203644561475436 19758078791036601683550549457307734250132091348237 67913836517543105239536719778522630598306091311778 01517018473419551782083685970482736851488324669809 67826424129426918703837554365381987202581644055207 29443928128346598929914838610333311926647139217361 84439296656941684194914458935545083121452111596782 72609636102501230428807501374214287948209489922794 04917456873527789808912332851409855948799577510953 00647425162891558424879373241151669954799924038445 68229440067774588249691771929122269676355283078764 92581854466547687556545067712253324080119169199385 05370692668148114213031389780777114780177004871146 51351601764737051295848373315140397997090803794315 07985695354618849164417252142747095137525007700363 41827038279421445763091223583694564915884274677107 75884280408394754494151594511691983404256638999613 56701472702280347283791566413894879530235341020154 10576819703308415147317937422630718615030793474550 28937566794023056085249684891705541856417002502945 73975291876838792342640256781629122251146575882894 4973345013184363023296235457948241 ---------- Now for a proof. Let Q = 28928434216210803690615246524734063145625591441015 67516298556775655527847475254643269219998751288122 38646067507316936061135994308876064606177963915153 10148615644602695488903472193120478048934544337783 50500993413376794661644857620913328971255920678525 80516161953301500892518877982770524680448030575538 60325613357766189149096689330965055007155182525149 515525889989 (Q is prime: subproof omitted.) S = 2 * Q T = 70323610117989232939059249931645122359843269434492 41327719159587783478237835918161785248366689469809 56468420121071187750024433422438801771087852206517 74692493270514283076583695250654140069374950149856 45561297450677685295272162306321861055508578946764 08778034790938106697782587142237972655979754214171 88175765418254215675629175733660468730308034858905 8320621801 M = S * T A = 54215605853661760575365176565408275413482806064633 15054449398318430183363513621001659876093872231181 16471828178358048136250081057773954633314443563489 14569702071674858855538156212752894234186869653495 01417292764025522504282905939725077989940637806955 23731786743151513819101206776709281022382132576840 49745773977644827206964500816667714296045978871816 26594366222797028206624832656810218030023490532460 19529270333771069495383071716168481021599870245135 18430482442521180768217033043668300078406219820843 08544042382476767429467054237581896316781460722765 26459754971947491683633684669669612703098311922716 95961672667120555322877445589836857374940944134005 53867690822718050450411564283982459498248178309690 66204162023068382112282498719629195618182388184559 05150325636766406657995298287567195324927191929693 11734841900338405934436753313040603988139471080635 95729473805214058250062009527745564044889431474255 87299470252069943347901317278754898664832383833702 71553876588656939010395067827348354880845222975715 37524326993623405570286359414942260683044570070721 448137577484661026699816478612597 X = 59773640071713132385218793655499860404090932275296 66069787342264093295347046551445715562283448628929 64816332920485590083764861330213347055685681357031 55352948851729217601431658303309154819316127705579 00351885354744174909956919526024437010401365128032 73304400582789252630406290418994635800676273980694 86760341875705180041930251284579025783440263715455 97858503493397322740910143064935302638520796615229 22683821862084573711264404212138945738420455545697 22886052002431724914058097400157615546805777632577 47871858124303408957694788395738139410655251601244 51192311827163273140490765357097293212153469932422 02275011554221779391987232912013158927761446219248 42410764367877368538002330997768327909337853837885 57261022078868837193078031936118877760503490262255 18725229321517485348356448129392999832971796637792 14311493549810218269801209476147841968474323052074 90223955140795958942248149865578863074745425894382 08516646940585940960881258874904087026271278860819 21163592684386142364411573813211662262295227558469 89154185594483568231746686035841230209486307409398 394353899179242431054969142666018 Y = 11103763034388752369975529566632484068327580624847 57806739492216457769080323744781467734954715591349 21240983266944974232541957305414865421807061776187 84529322517571932736342554838802388743092348791038 23219629840137597667186563478276689321651678220573 75400805302991846397550931065398130556092906237528 20234862743778319358471256673900052260852232614308 91207095066742472105800993803311222844479081029768 49371741873546392384584397917000162261634538657732 89723616730013579241273418668290966531331499319968 70479327960579249057845668308392339516797339582054 91065305234808160599733477969310732922902547376711 87441367824385287858835918423522880100825144925486 62867450247521858223483972094624007082739207881474 82716225346331759786975860338433058842789329051399 99721992736313516109392544709779620661591447011380 36465241677851317088277620173550700811425419056830 76198413202588493873944025109822867239013187029846 80909229897710066808427946466226435771540135279269 01358266879032627559274963460154704596546964738558 43010903493491775442938335158330957844941106288301 3814867916342894955969678267751970 Let C be the elliptic pseudo-curve y^2 = x^3 + Ax, over N. Let Z be the point (X,Y) on that pseudo-curve. On pseudo-curve C, one can compute [M/Q]*Z, [M/2]*Z, and [M]*Z; only the last is the identity point of the curve. That, and the Goldwasser-Kilian ECPP theorem*, shows that for every prime P dividing N, the order of the (real) elliptic curve over P is a multiple of S. * See Crandall & Pomerance, "Prime Numbers, a Computational Perspective", page 334. S is big enough to ensure that every prime P dividing N is bigger than the cube-root of N. (This is quite like an EC primality-proof, but S is too small.) So N has at most two prime factors. And one can check that N is not a base-two strong-probable-prime. So N is composite, and has at least two prime factors. QED. ---------- What about finding a proper factor of N? It has over 1000 digits, so the usual methods won't work soon. But the semiprime proof might reveal enough about N, that it can be factored. (I expect that a factorization of T, plus some elliptic arithmetic, would do it; that's why the numbers are so big.) What do y'all think: has anyone a hope of factoring N? -- Don Reble djr@nk.ca 2005 February 26 ------------------------------------------------------------------------ 2021 December 10 I am pleased to receive news from Giuseppe Vitto at the University of Luxembourg, who easily factored that ISP, and discovered a more secure way to make certified semiprimes. (And a subtly _insecure_ way!) https://eprint.iacr.org/2021/1610 -- Don Reble