ãã©ã€ã ãã³ããŒïŒç§ãã¡ã®ããžã¿ã«ã®äžçã圢äœãæ°åŠã®æ§æèŠçŽ

Yên Chi
Creator

ç®æ¬¡
- çŽ æ°ãšã¯äœã§ããïŒæç¢ºãªå®çŸ©
- äž»èŠãªæ°ã®çºèŠã®æŽå²çãªæ
- ãã©ã€ã ãã³ããŒããããã£ã®çè§£
- çŽ æ°ãèŠã€ããæ¹æ³
- çŸä»£ã®æå·åã®çŽ æ°
- ã°ã¬ãŒããã©ã€ã ãã³ããŒãã³ã
- ä»ã®åéã®çŽ æ°
- ãã©ã€ã ãã³ããŒãæãããšåŠç¿
- ãã©ã€ã ãã³ããŒç ç©¶ã®æªæ¥
- çµè«ïŒæ°žç¶çãªãã©ã€ã ã®è¬
ãã©ã€ã ãã³ããŒã¯ã2ã000幎以äžã«ããã£ãŠæ°åŠè ãé äºããŠããŸãããããã®éèŠæ§ã¯åŠåçãªå¥œå¥å¿ãã¯ããã«è¶ ããŠããŸãããããã®åºæ¬çãªæ°åŠçãšã³ãã£ãã£ã¯çŸåšãææ°ã®ããžã¿ã«ã»ãã¥ãªãã£ã®ããã¯ããŒã³ã圢æããå®å šãªãªã³ã©ã€ã³ãã³ãã³ã°ããæå·åãããã¡ãã»ãŒãžã³ã°ãŸã§ãã¹ãŠãå¯èœã«ããŸããçŽ æ°ãçè§£ããããšã¯ãæ°åŠçè«ã ãã§ã¯ãªããããžã¿ã«ã®ç掻ãä¿è·ããç®ã«èŠããªãåãææ¡ããããšã§ãã
çŽ æ°ãšã¯äœã§ããïŒæç¢ºãªå®çŸ©
ãã©ã€ã ãã³ããŒã¯ã1ãã倧ãã2ã€ã®ç°ãªã逿°ãæã€1ãã倧ããèªç¶æ°ã§ãïŒ1ãšããèªäœããã®äžèŠåçŽãªå®çŸ©ã«ã¯ãæ°åŠã®æãæ·±ãæŠå¿µã®1ã€ãå«ãŸããŸããããšãã°ã7ã¯1ãš7ã§åçã«åå²ã§ããããããã©ã€ã ã§ããã8ã¯1ã2ã4ãããã³8ã§å²ãããšãã§ããããããã©ã€ã ã§ã¯ãããŸããã
æåã®ããã€ãã®äž»èŠãªæ°åã¯2ã3ã5ã7ã11ã13ã17ã19ã23ãããã³29ã§ãã2ãå¯äžã®å¶æ°ã®çŽ æ°ã§ããããšã«æ³šæããŠãã ããã
äž»èŠãªæ°ã®çºèŠã®æŽå²çãªæ
å€ä»£ã®ãªã·ã£äººã¯ãçŽå å300幎ããã«äœç³»çã«çŽ æ°ãç ç©¶ããŸããããŠãŒã¯ãªããã¯ãæ°åŠã®åæã®æããšã¬ã¬ã³ããªèšŒæ ã®1ã€ã確ç«ããç¡éã«å€ãã®çŽ æ°ãããããšã蚌æããŸããã圌ã®äœåã¯ãæçµçã«çŸä»£ã®æè¡ã«é©åœãããããåéã§ããæ°ã®çè«ã®åºç€ãç¯ããŸããã
ã®ãªã·ã£ã®æ°åŠè ã®ãšã©ãã¹ããã¹ã¯ãçŽå å240幎é ã«æåãªããšã©ãã¹ããã¹ã®ãµãããã¢ã«ãŽãªãºã ãéçºããŸãããããã¯ãç¹å®ã®å¶éãŸã§ãã¹ãŠã®çŽ æ°ãèŠã€ããããã®æãå¹ççãªæ¹æ³ã®1ã€ã§ãããã®ã¢ã«ãŽãªãºã ã¯ãåçŽ æ°ã®åæ°ãäœç³»çã«æé€ãããã©ã€ã èªäœã®ã¿ãæ®ãããšã§æ©èœããŸãã
ãã©ã€ã ãã³ããŒããããã£ã®çè§£
ãã©ã€ã ãã³ããŒã¯ãæ°åŠã§ãŠããŒã¯ãªãã®ã«ããããã€ãã®é¡èãªç¹æ§ãæã£ãŠããŸãã
ç®è¡ã®åºæ¬å®ç
1ãè¶ ãããã¹ãŠã®æ£ã®æŽæ°ã¯ãçŽ æ°ã®ãŠããŒã¯ãªç£ç©ãšããŠè¡šçŸã§ããŸããããã¯ãååãç©è³ªã®æ§æèŠçŽ ã§ããããã«ããã©ã€ã ã¯æåéããã¹ãŠã®èªç¶æ°ã®ããã«ãã£ã³ã°ãããã¯ãã§ããããšãæå³ããŸãã
ãã©ã€ã ã®ã£ãã
é£ç¶ããçŽ æ°éã®ã¹ããŒã¹ã¯ãæ°åã倧ãããªãã«ã€ããŠãŸããŸãäžèŠåã«ãªããŸãã2ã3ã®ãããªå°ããªçŽ æ°ã¯1ã€ã®æ°åã§åºåãããŠããŸããã倧ããªçŽ æ°ã¯æ°çŸãŸãã¯æ°åã®è€åæ°ã§åºåãããšãã§ããŸãã
ãã€ã³ãã©ã€ã
ããã€ãã®äž»èŠãªæ°åã¯ãïŒ3,5ïŒãïŒ5,7ïŒãïŒ11,13ïŒãïŒ17,19ïŒãªã©ããã£ã1ã€ã®å¶æ°æ°ã§åºåããããã¢ã§æäŸãããŸãããã€ã³ãã©ã€ã ã®æšæž¬ã¯ããã®ãããªãã¢ãç¡éã«ããããšã瀺åããŠããŸãããããã¯èšŒæãããŠããªããŸãŸã§ãã
Mersenne Primes
ãããã®ç¹å¥ãªçŽ æ°ã¯ããã©ãŒã 2^nã1ãåããŸããããã§ã¯ãnããã©ã€ã ã§ããäŸã«ã¯ã3ïŒ2^2 - 1ïŒã7ïŒ2^3 - 1ïŒãããã³31ïŒ2^5 - 1ïŒãå«ãŸããŸããæå€§ã®æ¢ç¥ã®çŽ æ°ã¯éåžžãMersenne Primesã§ãããçŸåšã®ã¬ã³ãŒããã«ããŒã«ã¯2,400äžæ¡ä»¥äžãå«ãŸããŠããŸãã
çŽ æ°ãèŠã€ããæ¹æ³
ãšã©ãã¹ããã¹ã®ãµãã
ãã®å€ä»£ã®ã¢ã«ãŽãªãºã ã¯ãç¹å®ã®æ°å€ãŸã§ã®ãã¹ãŠã®çŽ æ°ãèŠã€ããã®ã«éåžžã«å¹æçãªãŸãŸã§ããããã»ã¹ã«ã¯æ¬¡ã®ãã®ãå«ãŸããŸãã
- ãã¹ãŠã®çªå·ã2ããã¿ãŒã²ããçªå·ã«ãªã¹ãããŸã
- 2ïŒæåã®ãã©ã€ã ïŒããå§ããŠããã®ãã¹ãŠã®åæ°ãè€åãšããŠããŒã¯ããŸã
- 次ã®ããŒã¯ã®ãªãçªå·ã«ç§»åããç¹°ãè¿ããŸã
- ã¿ãŒã²ããã®å¹³æ¹æ ¹ãŸã§ãã¹ãŠã®æ°å€ãåŠçãããŸã§ç¶è¡ããŸã
詊éšåž«å£æ¹æ³
ç¹å®ã®æ°å€ããã©ã€ã ãã©ããããã¹ãããããã«ã詊çšéšéã§ã¯ããã®æ°å€ããã®å¹³æ¹æ ¹ãŸã§ä»»æã®ãã©ã€ã ã§åçã«åå²ã§ãããã©ããã確èªããããšãå«ãŸããŸãã逿°ãèŠã€ãããªãå Žåãæ°ã¯ãã©ã€ã ã§ãã
ææ°ã®èšç®æ¹æ³
仿¥ã®ã³ã³ãã¥ãŒã¿ãŒã¯ã倿°ã®Miller-Rabin Primalityãã¹ããªã©ã®æŽç·Žãããã¢ã«ãŽãªãºã ã䜿çšããŠããŸãããããã®ç¢ºççãã¹ãã¯ã絶察çãªç¢ºå®æ§ãæäŸããªããã®ã®ãéåžžã«å€ãã®æ°åããã©ã€ã ã§ããå¯èœæ§ãé«ããã©ãããè¿ éã«å€æã§ããŸãã
çŸä»£ã®æå·åã®çŽ æ°
çŽ æ°ã®æãéèŠãªå®çšçãªå¿çšã¯ãç¹ã«ããžã¿ã«éä¿¡ã®å€ããä¿è·ããRSAæå·åã·ã¹ãã ã«ããæå·åã«ãããŸãã
RSAæå·åã®åºç€
RSAã»ãã¥ãªãã£ã¯ã2ã€ã®å·šå€§ãªçŽ æ°ã®è£œåã§ãã倿°ãèæ ®ããããšã®æ°åŠçãªé£ããã«äŸåããŸãã2ã€ã®å€§èŠæš¡ãªãã©ã€ã ãå¢ããããšã¯èšç®çã«ç°¡åã§ãããããã»ã¹ãé転ãããããšïŒè£œåã®äž»èŠãªèŠå ãèŠã€ããïŒã¯ãç¹å¥ãªç¥èããªããã°éåžžã«å°é£ã§ãã
RSAãå®éã«ã©ã®ããã«æ©èœãããã¯æ¬¡ã®ãšããã§ãã
- ããŒçæïŒ2ã€ã®å€§ããªçŽ æ°ãéžæããŸãïŒéåžžã¯1024ããã以äžïŒ
- å ¬éããŒã®äœæïŒãããã®çŽ æ°ãæããŠå ¬éããŒãäœæãã
- æå·åïŒå ¬éããŒã䜿çšããŠã¡ãã»ãŒãžãæå·åããŸã
- 埩å·åïŒå ã®ãã©ã€ã ãã¡ã¯ã¿ãŒã®ç¥èãæã£ãŠãã人ã ããã¡ãã»ãŒãžãè§£èªã§ãã
å®äžçã®ã»ãã¥ãªãã£ã¢ããªã±ãŒã·ã§ã³
ãã©ã€ã ãã³ããŒããŒã¹ã®æå·åã¯ä¿è·ããŸãïŒ
- ãªã³ã©ã€ã³ãã³ãã³ã°ãã©ã³ã¶ã¯ã·ã§ã³
- ã¯ã¬ãžããã«ãŒãã®æ¯æã
- ã»ãã¥ã¢ãªã¡ãã»ãŒãžã³ã°ã¢ããªã±ãŒã·ã§ã³
- ããžã¿ã«çœ²åãšèšŒææž
- ãããã¯ãã§ãŒã³ããã³æå·é貚ã·ã¹ãã
ãããã®ã·ã¹ãã ã®ã»ãã¥ãªãã£ã¯ã倧éãäž»èŠãªã³ã³ããŒãã³ãã«èæ ®ãããšããèšç®äžã®é£ããã«å®å šã«äŸåããŸãã
ã°ã¬ãŒããã©ã€ã ãã³ããŒãã³ã
åŠåç远æ±ãšå®çšçãªå¿ èŠæ§ã®äž¡æ¹ãšããŠãåžžã«å€§èŠæš¡ãªçŽ æ°ã®æ€çŽ¢ã¯ç¶ããŠããŸããã³ã³ãã¥ãŒãã£ã³ã°ãã¯ãŒãå¢å ããã«ã€ããŠãã»ãã¥ãªãã£åºæºãç¶æããã«ã¯ããã倧ããªçŽ æ°ãå¿ èŠã§ãã
èšé²çãªçºèŠ
å倧ãªã€ã³ã¿ãŒãããMersenne Prime SearchïŒGimpsïŒã¯ã忣ã³ã³ãã¥ãŒãã£ã³ã°ãéããŠæå€§ã®æ¢ç¥ã®ãã©ã€ã ã®ã»ãšãã©ãçºèŠããŸãããäžçäžã®ãã©ã³ãã£ã¢ã¯ãæœåšçãªMersenne Primesããã¹ãããããã«ãã³ã³ãã¥ãŒã¿ãŒã®ã¢ã€ãã«æéãè²¢ç®ããŠããŸãã
2018幎ã«çºèŠãããçŸåšã®æå€§ã®ãã©ã€ã ã¯ã24,862,048æ¡ãå«ã2^82,589,933 - 1ã§ããæšæºã®ãã©ã³ãã§å°å·ãããšããã®çªå·ã¯çŽ9,000ããŒãžã«åã³ãŸãã
å°æ¥ã®èª²é¡
éåã³ã³ãã¥ãŒãã£ã³ã°ãé²ãã«ã€ããŠãæçµçã«ã¯å€ãã®å æ°åè§£ãå®è¡å¯èœã«ããããšã«ãããçŸåšã®æå·åã·ã¹ãã ãè ããå¯èœæ§ããããŸããããã«ãããéåèæ§ã®æå·åãšããžã¿ã«ã»ãã¥ãªãã£ã®ããã®æ°ããæ°åŠçåºç€ã®ç ç©¶ãçãŸããŸããã
ä»ã®åéã®çŽ æ°
æå·åãè¶ ããŠãçŽ æ°ãé©ãã¹ãæèã§è¡šç€ºãããŸãïŒ
çç©åŠãšèªç¶
CICADAçš®ã¯ãäžæµã®ãµã€ã¯ã«ïŒ13ãŸãã¯17幎ïŒã§å°äžããåºçŸããŸããããã¯ã寿åœãçãæé£è ãé¿ããããã®é²åçæŠç¥ã§ããããã¯ããã©ã€ã ãã³ããŒãèªç¶ã®äžã§çåäžã®å©ç¹ãæäŸããæ¹æ³ã瀺ããŠããŸãã
ã³ã³ãã¥ãŒã¿ãµã€ãšã³ã¹
ããã·ã¥é¢æ°ãä¹±æ°çæãããã³ããŒã¿æ§é ã®èšèšã¯ãå€ãã®å Žåãåçãªååžã確ä¿ããè¡çªãæå°éã«æããããã«çŽ æ°ã«äŸåããŠããŸãã
ç©çåŠãšååŠ
äžçŽ æ°ã¯ãéåååŠãçµæ¶æ§é ãããã³ããŸããŸãªç©ççŸè±¡ã«çŸããæ°åŠãšèªç¶çã®éã®æ·±ãã€ãªããã瀺åããŠããŸãã
ãã©ã€ã ãã³ããŒãæãããšåŠç¿
çŽ æ°ãçè§£ããããšã¯ãéèŠãªæ°åŠçæèã¹ãã«ã®éçºã«åœ¹ç«ã¡ãŸãïŒ
åŠçåã
å°ããªäŸãšèŠèŠç衚çŸããå§ããŸããå åããªãŒã䜿çšããŠãè€åæ°ãäž»èŠãªèŠå ã«åé¡ãããæ¹æ³ã瀺ããŸãããã©ã€ã ããŸããŸãäºæž¬äžå¯èœã«ãªãããšãèªèããªããããã¿ãŒã³ãèå¥ããããšãç·Žç¿ããŸãã
æè²è åã
ãã¯ãããžãŒã«ãããçŽ æ°ã®å®çšçãªã¢ããªã±ãŒã·ã§ã³ã匷調ããŸããæŽå²çãªæ°åŠççºèŠãææ°ã®ããžã¿ã«ã»ãã¥ãªãã£ã®ããŒãºã«çµã³ä»ããŸããEratosthenesã®ãµãããªã©ã®å®è·µçãªã¢ã¯ãã£ããã£ã䜿çšããŠãæœè±¡çãªæŠå¿µãå ·äœåããŸãã
ãã©ã€ã ãã³ããŒç ç©¶ã®æªæ¥
ãã©ã€ã ãã³ããŒã«é¢ããæ°åŠã»ã³ã¿ãŒã«ãããããã€ãã®äž»èŠãªæªè§£æ±ºã®åé¡ïŒ
ãªãŒãã³ä»®èª¬
ãã¬ãã¢ã è³ã®åé¡ã®1ã€ã§ãããã®æåãªæšæž¬ã¯ãçŽ æ°ã®ååžãäºæž¬ããŠããŸãããã®è§£æ±ºã¯ãæ°çè«ã®çè§£ã«é©åœããããããæå·åã«å®éçãªæå³ãæã¡ãŸãã
èšç®ã®é²æ©
æ©æ¢°åŠç¿ãšäººå·¥ç¥èœã¯ããã©ã€ã ãã³ããŒã®ç ç©¶ã«é©çšãããŠããã人éã®æ°åŠè ãèŠéããããããªãæ°ãããã¿ãŒã³ãšé¢ä¿ãæœåšçã«æããã«ããŠããŸãã
éåãžã®åœ±é¿
éåã³ã³ãã¥ãŒã¿ãŒãéçºããããšãçŸåšã®ãã©ã€ã ããŒã¹ã®æå·åãè ãããå€å žçãªã³ã³ãã¥ãŒã¿ãŒã§ã¯æ°ãã圢åŒã®æ°åŠçæ¢æ»ãäžå¯èœã«ãªãå¯èœæ§ããããŸãã
çµè«ïŒæ°žç¶çãªãã©ã€ã ã®è¬
ãã©ã€ã ãã³ããŒã¯ãæ°åŠã®æãçŸãããã©ããã¯ã¹ã®1ã€ã衚ããŠããŸãããã®è¡åã«ãããŠãç°¡åã«å®çŸ©ããããšãç¡éã«è€éã§ããå€ä»£ã®ãªã·ã£ã®å®çããçŸä»£ã®ããžã¿ã«ã»ãã¥ãªãã£ãŸã§ããã©ã€ã ã¯ç§ãã¡ãé©ãããææŠãç¶ããŠããŸãã
ãŸããŸãããžã¿ã«ã®æªæ¥ã«é²ãã«ã€ããŠãçŽ æ°ãçè§£ããããšã¯ãåŠåçã«è峿·±ãã ãã§ãªããå®è³ªçã«äžå¯æ¬ ã«ãªããŸãããããã®æ°åŠçãªæ§æèŠçŽ ã¯ãéä¿¡ã確ä¿ãããã©ã€ãã·ãŒãä¿è·ããå°æ¥ã®æè¡çãã¬ãŒã¯ã¹ã«ãŒã®éµãä¿æããå¯èœæ§ããããŸãã
ããªããåããŠçŽ æ°ã«ééããåŠçã§ããããšãæå·åã·ã¹ãã ã§åãå°éå®¶ã§ããããšãããªãã¯äœå幎ãã®é人é¡ãé äºããããããä»åŸã®äžä»£ã®ããã«ããããããšãç¶ããæŠå¿µã«åŸäºããŠããããšãå¿ããªãã§ãã ããã
çŽ æ°ã®ãã¿ãŒã³ã®æ€çŽ¢ã¯ç¶ãã匷åãªã³ã³ãã¥ãŒã¿ãŒã人工ç¥èœã®æä»£ã§ãããå°ãªããšãä»ã®ãšããã¯ãç§ãã¡ã®ææ¡ãè¶ ããŠè¬ã«é¥ã£ãŠããããšãæãåºãããŠãããŸãã