[ABP: 소수는 소수개인가?]
난수를 향한 모험
소수는 예전부터 많은 수학자들은 물론 일반인들의 관심을 끌어 온 신비의 대상이었습니다. 정의 자체는 '1과 자신만으로 나누어지는 자연수' 로서 매우 간단하지만, 소수를 찾는 것은 생각보다 쉬운 일은 아닙니다. 특정한 소수를 찾는 것만큼이나 재미있는 것은 특정한 무리수 속에 소수가 몇 개나 숨어 있을까에 대한 것입니다.
예를 들어 원주율을 알아봅시다. 원주율 pi는 3.141592... 로 시작되는 무리수라는 것은 잘 알려져 있습니다. 우리의 흥미를 자아내는 것은 이 무리수 안에 소수가 몇 개나 숨어 있느냐는 것입니다. 여기서 소숫점은 제외합니다. 즉, 3으로 시작하는 소수를 찾는 것이고, 자리수가 k라면 pi_k 라고 표시합니다.
예를 들면 이렇습니다.
pi1 = 3
pi2 = 31
그렇다면 이 다음 소수가 무엇이 될지 추측되십니까? 답을 먼저 알려 드리겠습니다.
pi6 = 314159
그런데 이 소수는 좀 재미있습니다. 두 개씩 끊어보겠습니다.
그러면 그 결과물로 나오는 31, 41, 59는 모두 소수가 됩니다. 더구나 이들은 각각 11, 13, 17번째 소수이기도 합니다. 소오름이 돋지 않습니까?
그렇다면 그 다음 소수는 몇 자리수까지 갈까요? 역시 답을 바로 알려 드리겠습니다.
pi38 = 31415926535897932384626433832795028841
그렇습니다 38자리 숫자로 갑자기 겅중 뜁니다.
그렇다면 그 다음은 몇 자리수까지 갈까요? 우리의 상상을 초월합니다. 16028자리로 또 겅중 뜁니다.
pi16028 = 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989380952572010654858632788659361533818279682303019520353018529689957736225994138912497217752834791315155748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035637076601047101819429555961989467678374494482553797747268471040475346462080466842590694912933136770289891521047521620569660240580381501935112533824300355876402474964732639141992726042699227967823547816360093417216412199245863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818347977535663698074265425278625518184175746728909777727938000816470600161452491921732172147723501414419735685481613611573525521334757418494684385233239073941433345477624168625189835694855620992192221842725502542568876717904946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886269456042419652850222106611863067442786220391949450471237137869609563643719172874677646575739624138908658326459958133904780275900994657640789512694683983525957098258226205224894077267194782684826014769909026401363944374553050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382686838689427741559918559252459539594310499725246808459872736446958486538367362226260991246080512438843904512441365497627807977156914359977001296160894416948685558484063534220722258284886481584560285060168427394522674676788952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288797108931456691368672287489405601015033086179286809208747609178249385890097149096759852613655497818931297848216829989487226588048575640142704775551323796414515237462343645428584447952658678210511413547357395231134271661021359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435064302184531910484810053706146806749192781911979399520614196634287544406437451237181921799983910159195618146751426912397489409071864942319615679452080951465502252316038819301420937621378559566389377870830390697920773467221825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539057962685610055081066587969981635747363840525714591028970641401109712062804390397595156771577004203378699360072305587631763594218731251471205329281918261861258673215791984148488291644706095752706957220917567116722910981690915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398315019701651511685171437657618351556508849099898599823873455283316355076479185358932261854896321329330898570642046752590709154814165498594616371802709819943099244889575712828905923233260972997120844335732654893823911932597463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100449293215160842444859637669838952286847831235526582131449576857262433441893039686426243410773226978028073189154411010446823252716201052652272111660396665573092547110557853763466820653109896526918620564769312570586356620185581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318586769751456614068007002378776591344017127494704205622305389945613140711270004078547332699390814546646458807972708266830634328587856983052358089330657574067954571637752542021149557615814002501262285941302164715509792592309907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111790429782856475032031986915140287080859904801094121472213179476477726224142548545403321571853061422881375850430633217518297986622371721591607716692547487389866549494501146540628433663937900397692656721463853067360965712091807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862947265473642523081770367515906735023507283540567040386743513622224771589150495309844489333096340878076932599397805419341447377441842631298608099888687413260472156951623965864573021631598193195167353812974167729478672422924654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001593776471651228935786015881617557829735233446042815126272037343146531977774160319906655418763979293344195215413418994854447345673831624993419131814809277771038638773431772075456545322077709212019051660962804909263601975988281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267945612753181340783303362542327839449753824372058353114771199260638133467768796959703098339130771098704085913374641442822772634659470474587847787201927715280731767907707157213444730605700733492436931138350493163128404251219256517980694113528013147013047816437885185290928545201165839341965621349143415956258658655705526904965209858033850722426482939728584783163057777560688876446248246857926039535277348030480290058760758251047470916439613626760449256274204208320856611906254543372131535958450687724602901618766795240616342522577195429162991930645537799140373404328752628889639958794757291746426357455254079091451357111369410911939325191076020825202618798531887705842972591677813149699009019211697173727847684726860849003377024242916513005005168323364350389517029893922334517220138128069650117844087451960121228599371623130171144484640903890644954440061986907548516026327505298349187407866808818338510228334508504860825039302133219715518430635455007668282949304137765527939751754613953984683393638304746119966538581538420568533862186725233402830871123282789212507712629463229563989898935821167456270102183564622013496715188190973038119800497340723961036854066431939509790190699639552453005450580685501956730229219139339185680344903982059551002263535361920419947455385938102343955449597783779023742161727111723643435439478221818528624085140066604433258885698670543154706965747458550332323342107301545940516553790686627333799585115625784322988273723198987571415957811196358330059408730681216028764962867446047746491599505497374256269010490377819868359381465741268049256487985561453723478673303904688383436346553794986419270563872931748723320837601123029911367938627089438799362016295154133714248928307220126901475466847653576164773794675200490757155527819653621323926406160136358155907422020203187277605277219005561484255518792530343513984425322341576233610642506390497500865627109535919465897514131034822769306247435363256916078154781811528436679570611086153315044521274739245449454236828860613408414863776700961207151249140430272538607648236341433462351897576645216413767969031495019108575984423919862916421939949072362346468441173940326591840443780513338945257423995082965912285085558215725031071257012668302402929525220118726767562204154205161841634847565169998116141010029960783869092916030288400269104140792886215078424516709087000699282120660418371806535567252532567532861291042487761825829765157959847035622262934860034158722980534989650226291748788202734209222245339856264766914905562842503912757710284027998066365825488926488025456610172967026640765590429099456815065265305371829412703369313785178609040708667114965583434347693385781711386455873678123014587687126603489139095620099393610310291616152881384379099042317473363948045759314931405297634757481193567091101377517210080315590248530906692037671922033229094334676851422144773793937517034436619910403375111735471918550464490263655128162288244625759163330391072253837421821408835086573917715096828874782656995995744906617583441375223970968340800535598491754173818839994469748676265516582765848358845314277568790029095170283529716344562129640435231176006651012412006597558512761785838292041974844236080071930457618932349229279650198751872127267507981255470958904556357921221033346697499235630254947802490114195212382815309114079073860251522742995818072471625916685451333123948049470791191532673430282441860414263639548000448002670496248201792896476697583183271314251702969234889627668440323260927524960357996469256504936818360900323809293459588970695365349406034021665443755890045632882250545255640564482465151875471196218443965825337543885690941130315095261793780029741207665147939425902989695946995565761218656196733786236256125216320862869222103274889218654364802296780705765615144632046927906821207388377814233562823608963208068222468012248261177185896381409183903673672220888321513755600372798394004152970028783076670944474560134556417254370906979396122571429894671543578468788614445812314593571984922528471605049221242470141214780573455105008019086996033027634787081081754501193071412233908663938339529425786905076431006383519834389341596131854347546495569781038293097164651438407007073604112373599843452251610507027056235266012764848308407611830130527932054274628654036036745328651057065874882256981579367897669742205750596834408697350201410206723585020072452256326513410559240190274216248439140359989535394590944070469120914093870012645600162374288021092764579310657922955249887275846101264836999892256959688159205600101655256375678566722796619885782794848855834397518744545512965634434803966420557982936804352202770984294232533022576341807039476994159791594530069752148293366555661567873640053666564165473217043903521329543529169414599041608753201868379370234888689479151071637852902345292440773659495630510074210871426134974595615138498713757047101787957310422969066670214498637464595280824369445789772330048764765241339075920434019634039114732023380715095222010682563427471646024335440051521266932493419673977041595683753555166730273900749729736354964533288869844061196496162773449518273695588220757355176651589855190986665393549481068873206859907540792342402300925900701731960362254756478940647548346647760411463233905651343306844953979070903023460461470961696886885014083470405460742958699138296682468185710318879065287036650832431974404771855678934823089431068287027228097362480939962706074726455399253994428081137369433887294063079261595995462624629707062594845569034711972996409089418059534393251236235508134949004364278527138315912568989295196427287573946914272534366941532361004537304881985517065941217352462589548730167600298865925786628561249665523533829428785425340483083307016537228563559152534784459818313411290019992059813522051173365856407826484942764411376393866924803118364453698589175442647399882284621844900877769776312795722672655562596282542765318300134070922334365779160128093179401718598599933849235495640057099558561134980252499066984233017350358044081168552653117099570899427328709258487894436460050410892266917835258707859512983441729535195378855345737426085902908176515578039059464087350612322611200937310804854852635722825768203416050484662775045003126200800799804925485346941469775164932709504934639382432227188515974054702148289711177792376122578873477188196825462981268685817050740272550263329044976277894423621674119186269439650671515779586756482399391760426017633870454990176143641204692182370764887834196896861181558158736062938603810171215855272668300823834046564758804051380801633638874216371406435495561868964112282140753302655100424104896783528588290243670904887118190909494533144218287661810310073547705498159680772009474696134360928614849417850171807793068108546900094458995279424398139213505586422196483491512639012803832001097738680662877923971801461343244572640097374257007359210031541508936793008169980536520276007277496745840028362405346037263416554259027601834840306811381855105979705664007509426087885735796037324514146786703688098806097164258497595138069309449401515422221943291302173912538355915031003330325111749156969174502714943315155885403922164097229101129035521815762823283182342548326111912800928252561902052630163911477247331485739107775874425387611746578671169414776421441111263583553871361011023267987756410246824032264834641766369806637857681349204530224081972785647198396308781543221166912246415911776732253264335686146186545222681268872684459684424161078540167681420808850280054143613146230821025941737562389942075713627516745731891894562835257044133543758575342698699472547031656613991999682628247270641336222178923903176085428943733935618891651250424404008952719837873864805847268954624388234375178852014395600571048119498842390606136957342315590796703461491434478863604103182350736502778590897578272731305048893989009923913503373250855982655867089242612429473670193907727130706869170926462548423240748550366080136046689511840093668609546325002145852930950000907151058236267293264537382104938724996699339424685516483261134146110680267446637334375340764294026682973865220935701626384648528514903629320199199688285171839536691345222444708045923966028171565515656661113598231122506289058549145097157553900243931535190902107119457300243880176615035270862602537881797519478061013715004489917210022201335013106016391541589578037117792775225978742891917915522417189585361680594741234193398420218745649256443462392531953135103311476394911995072858430658361935369329699289837914941939406085724863968836903265564364216644257607914710869984315733749648835292769328220762947282381537409961545598798259891093717126218283025848112389011968221429457667580718653806506487026133892822994972574530332838963818439447707794022843598834100358385423897354243956475556840952248445541392394100016207693636846776413017819659379971557468541946334893748439129742391433659360410035234377706588867781139498616478747140793263858738624732889645643598774667638479466504074111825658378878454858148962961273998413442726086061872455452360643153710112746809778704464094758280348769758948328241239292960582948619196670918958089833201210318430340128495116203534280144127617285830243559830032042024512072872535581195840149180969253395075778400067465526031446167050827682772223534191102634163157147406123850425845988419907611287258059113935689601431668283176323567325417073420817332230462987992804908514094790368878687894930546955703072619009502076433493359106024545086453628935456862958531315337183868265617862273637169757741830239860065914816164049449650117321313895747062088474802365371031150898427992754426853277974311395143574172219759799359685252285745263796289612691572357986620573408375766873884266405990993505000813375432454635967504844235284874701443545419576258473564216198134073468541117668831186544893776979566517279662326714810338643913751865946730024434500544995399742372328712494834706044063471606325830649829795510109541836235030309453097335834462839476304775645015008507578949548931393944899216125525597701436858943585877526379625597081677643800125436502371412783467926101995585224717220177723700417808419423948725406801556035998390548985723546745642390585850216719031395262944554391316631345308939062046784387785054239390524731362012947691874975191011472315289326772533918146607300089027768963114810902209724520759167297007850580717186381054967973100167870850694207092232908070383263453452038027860990556900134137182368370991949516489600755049341267876436746384902063964019766685592335654639138363185745698147196210841080961884605456039038455343729141446513474940784884423772175154334260306698831768331001133108690421939031080143784334151370924353013677631084913516156422698475074303297167469640666531527035325467112667522460551199581831963763707617991919203579582007595605302346267757943936307
길어도 너무 길군요.
그 다음 소수도 있을까요? 있다면 과연 몇 자리수까지 갈까요?
여백이 없어 표기하기 어렵지만, 자리수만 따진다면 현재까지 발견된 pi 소수는 47577, 78073, 613373 으로 계속 이어집니다. 2023년 5월 현재까지는 613373자리 이후의 pi prime은 발견되지는 않았지만 아마도 있을 것이라 추정되기는 합니다.
로그적분함수 (출처: 권석준)
소수를 다루는 정수론에서는 이른바 소수의 개수를 추정할 수 있는 소수정리 (prime number theorem)이라는 것이 있습니다.이 정리는 독일의 수학자 가우스 (Gauss)가 창안하여 프랑스의 수학자 르장드르 (Legendre)가 정리하여 발표했다고 알려져 있습니다. 이 정리에 따르면 N 이하의 소수의 개수는 대략 N/log(N) 개 정도로 어림됩니다. (어림이라고 한 것은 대략 그 정도 수준이라는 뜻입니다.) 더 정확히는 소수의 개수를 설명하는 어림 함수는 로그적분함수 li(x) (logarithmic integral function)을 따릅니다. 이 정리를 이용하면 N번째 소수는 대략 N*logN 에 근접한다는 것도 알 수 있게 됩니다.
이 정리를 이용하면 알아낼 수 있는 것 중 하나가 바로 D 자리수의 난수가 소수일 확률입니다. 이 확률은 대략 (1/D)/log10 정도 입니다. 그렇다면 D 자리수 이하 모든 난수 중, 소수의 개수는 대략 (1 + (1/2) + (1/3) + ... + (1/D))/log10 가 될 것입니다. 여기서 (1 + (1/2) + (1/3) + ... + (1/D))는 H_D 라고 쓸 수 있는데 이를 조화수 (harmonic number)라고 부릅니다. H_D 는 대략 logD와 비슷하다고 알려져 있습니다. 따라서 D 자리수 이하의 소수 개수는 대략 ~logD/log10 = log10(D)가 될 것입니다.
그렇다면 D = 613373 인 경우는 어떨까요? 위의 공식에 대입해보면 5.79 개 정도로 나옵니다. 즉, 대략 6개 정도라는 뜻이죠. 그런데 실제로 pi에서는 1, 2, 6, 38, 16028, 47577, 78073, 613373 번째 소수가 발견되었으므로, 총 8개의 소수가 나오고, 이는 기대 숫자보다 좀 많습니다. 이는 pi에 들어 있는 숫자들이 완전한 난수로 보기 어렵다는 뜻이기도 합니다.
난수를 생성하는 것은 생각보다 중요하고도 어려운 일입니다. 한 가지 방편으로서 원주율에서 아무 숫자나 떼어나 만드는 방법으로 난수를 생성할 수 있는데, 위에서 알아보았듯, pi 속에 있는 숫자는 완전한 난수가 아니기 때문에 패턴이 파악되면 (즉, pi의 일부라는 것이 파악되면) 그 난수는 깨질 수도 있습니다.
그렇다면 다른 무리수는 어떨까요? pi만큼이나 가장 유명한 무리수인 자연상수 e를 알아봅시다. e = 2.718281828...인 무리수인 자연상수 속에는 몇 개의 소수가 숨어 있을까요?
e1 = 2
e3 = 271
e7 = 2718281
e85 = 2718281828459045235360287471352662497757247093699959574966967627724076630353547594571
이런 식으로 찾아집니다. 그 다음 자리수는 1781, 2780, 112280, 155025 입니다. 현재 155025 자리수 이상의 소수는 아직 찾아지지는 않고 있습니다. 마찬가지로 155025를 기준으로 할 경우, 기대 소수는 위의 소수정리에 따라 6개 정도이지만, 찾아진 소수는 8개입니다. pi에 숨겨진 소수의 개수와 똑같습니다. 이를 통해 자연상수를 이용하여 만드는 난수 역시 완전한 난수는 될 수 없음을 알 수 있습니다.
그렇다면 이런 신비로운 상수들 말고, 그냥 평범한 무리수는 어떨까요? 예를 들면 우리에게 매우 익숙한 무리수2^0.5 = 1.414...는 어떨까요?
굉장히 낯설게도 이 무리수 속에서 소수를 찾는 것은 생각보다 쉽지 않습니다.
S55 = 1414213562373095048801688724209698078569671875376948073
S97 = 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641
S225 = 141421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147010955997160597027453459
등으로 나옵니다. D = 3인 경우, 기대되는 소수 개수는 2개인데 벌써 3개가 나왔고, 앞으로 자리수가 많아질수록 더 많은 소수가 나올 것임을 예상할 수 있습니다. 따라서 square(2) 에서 만드는 난수 역시 완전한 난수가 되기는 어렵다는 것을 알 수 있습니다.
소수는 앞으로는 더더욱 정보의 보호, 양자컴퓨터, 몬테카를로 시뮬레이션 등의 분야에서 더 중요해질 것으로 예상됩니다. 이 응용에서 중요한 것은 얼마나 랜덤한 난수가 만들어질 수 있느냐인데, 결국 난수 생성과 소수의 특징은 밀접한 관련이 있음을 pi prime에서 알 수 있습니다. 완벽에 가까운 난수를 만들기 위해 Random.org 같은 사이트에서 API를 내려 받아 쓸 수는 있습니다. 그렇지만 이마저도 완벽한 방법은 아닙니다. 결국 이상적 난수에 가까운 난수를 생성하기 위해서는 이상에 가까운 노이즈를 만들어야 하고, 이 때문에 hardware 기반의 난수 생성 방법이 최근 들어 더 많은 관심을 받고 있습니다. 그렇지만 숫자만으로 난수를 생성할 때 여러 무리수들에서 생성된 난수를 섞어서 쓰는 방법은 꽤 괜찮은 근사 난수 (pseudo random number) 생성방법이 될 수 있습니다. 인류에게 가장 익숙한 무리수는 여전히 지금도 강력한 툴이 될 수 있다는 것은 매우 흥미로운 부분이자, 극복해야 할 최종 보스처럼 느껴지기도 합니다.
