¡¡Î㤨¤Ð¡¢¡Ö3¡ß5¡×¤ò¤·»»¤Ç½èÍý¤¹¤ë¤³¤È¤ò¹Í¤¨¤ë¡£
¡¡¡¤è¤ê¢¤Î¤Û¤¦¤¬·×»»²ó¿ô¤¬¾¯¤Ê¤¤¡£
Îã¡§M(A)¡ßM(B)¤òµá¤á¤Æ¡¢ANSÈÖÃϤ˳ÊǼ¤¹¤ë¡£¤¿¤À¤·¡¢¿ôÃͤÏÀµ¤È¤¹¤ë¡£
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
¡¡ºÇ½é¤ÎCPAÌ¿Îá¤ÈJMIÌ¿Îá¤ÈJZEÌ¿Îá¤Î¥»¥Ã¥È¤Ç¡¢GR3¤ÈGR4¤ÎÂç¾®Èæ³Ó¤ò¤·¤Æ¤¤¤ë¡£GR4¤¬Â礤¤¤è¤¦¤Ë¤·¤Æ³Ý¤±»»ÍѤΥ롼¥×¤Ç·×»»²ó¿ô¤ò¾¯¤Ê¤¯¤¹¤ë¤¿¤á¤Ç¤¢¤ë¡£²¾¤ËGR4¤Î¤Û¤¦¤¬GR3¤è¤ê¾®¤µ¤¤¾ì¹ç¤Ï¡¢GR5¤òºî¶ÈÍѤΥ쥸¥¹¥¿¤È¤·¤Æ³èÍѤ·¤Æ¡¢GR3¤ÈGR4¤ÎÃæ¿È¤òÆþ¤ìÂØ¤¨¤Æ¤¤¤ë¡£¤Ê¤ª¡¢Â¤·»»¤Î¤È¤¥ª¡¼¥Ð¡¼¥Õ¥í¡¼¤¬È¯À¸¤·¤¿¤é¡ÖOverFlow¡×¤Èɽ¼¨¤¹¤ë¡£
¡¡¤Ò¤È¤Äº¸¥·¥Õ¥È¤¹¤ë¤È2Çܤµ¤ì¤ë¤¬¡¢¤¦¤Þ¤¯ÍøÍѤ¹¤ë¤³¤È¤ÇǤ°Õ¤Î³Ý¤±»»¤ò½èÍý¤Ç¤¤ë¡£
Îã¡§M(A)¡ßM(B)¤òµá¤á¡¢ANSÈÖ¹æ¤Ë³ÊǼ¤¹¤ë¡£
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
¡¡ElGamal°Å¹æ¡¢RSA°Å¹æ¡¢Miler-Rabin¥Æ¥¹¥È¤ò²òÆÉ¤¹¤ë¤Ë¤Ï¼¡¤Î¹çƱÊýÄø¼°¤Î¥¿¥¤¥×¡ÊË¡¤¬¤«¤«¤Ã¤Æ¤¤¤ë¤³¤È¤ËÃí°Õ¡Ë¤Î¤Ù¤¾è·×»»¤ò¤¹¤ëɬÍפ¬¤¢¤ë¡£
¡¡Ã±½ã¤ÊÊý¼°¤À¤Èx-1²ó¤Î¾è»»¤ò¹Ô¤¦¤³¤È¤Ë¤Ê¤Ã¤Æ¤·¤Þ¤¦¡£x-1¢â2¦Ê¤Ê¤Î¤Ç»Ø¿ô»þ´Ö¤¬¤«¤«¤ë¡£¤³¤ì¤Ç¤Ï¿¹à¼°»þ´Ö¤Î·×»»¤·¤«¤Ç¤¤Ê¤¤¥¢¥¿¥Ã¥«¡¼¡Êpoly-time¥¢¥ë¥´¥ê¥º¥à¡Ë¤Ï»õ¤¬Î©¤¿¤Ê¤¤¡£
¡¡¼¡¤Î¥¢¥ë¥´¥ê¥º¥à¤Ç½èÍý¤¹¤ë¤³¤È¤Ç¡¢·×»»Î̤ò¸º¤é¤¹¤³¤È¤¬¤Ç¤¤ë¡£
p=ak¡¡¡Êa,k,p¤ÏÀµ¤ÎÀ°¿ô¡Ë
[µ]p¤ËÂФ·¤Æ¡¢p¢«1¤È½é´üÃͤòÂåÆþ¤¹¤ë¡£
[¶]k¤Î2¿Ê¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤ò¾å°Ì¥Ó¥Ã¥È¤«¤é1¥Ó¥Ã¥È¤º¤Ä¸«¤Æ¤¤¤¡¢³Æ¥Ó¥Ã¥È¤ËÂФ·¤Æ¼¡¤ò½èÍý¤¹¤ë¡£
(a)¤Þ¤ºp¤ò2¾è¤¹¤ë¡£
p¢«p¡ßp
(b)¤½¤Î¥Ó¥Ã¥È¤¬1¤Ê¤é¡¢¤µ¤é¤Ëa¤ò¤«¤±¤ë¡£
p¢«p¡ßa
¡¡¤â¤·¡¢Ë¡n¤Ç¹Í¤¨¤Æ¤¤¤ë¤Ê¤é¡¢½èÍý¤´¤È¤ËË¡n¤òŬÍѤ¹¤ë¡£¤½¤¦¤¹¤ì¤Ð¶õ´ÖÎ̤⸺¤é¤¹¤³¤È¤¬¤Ç¤¤ë¡£
Îã¡§p=320¤ò·×»»¤¹¤ë¡Êa=3,k=20¡Ë¡£
[µ]p=1
[¶]20¤Î2¿Ê¿ô¤Ï10100¤Ç¤¢¤ë¤Î¤Ç¡¢
[1]°ìÈÖº¸¤Î¥Ó¥Ã¥È1¤ËÂФ·¤Æ
(a)p=p¡ßp=1¡ß1=1
(b)p=p¡ßa=1¡ß3=3¡Ê=31¡Ë
[2]º¸¤«¤é2¥Ó¥Ã¥ÈÌܤËÂФ·¤Æ
(a)p=p¡ßp=3¡ß3=9¡Ê=32¡Ë
[3]º¸¤«¤é3¥Ó¥Ã¥ÈÌܤËÂФ·¤Æ
(a)p=p¡ßp=9¡ß9=81¡Ê=34¡Ë
(b)p=p¡ßa=81¡ß3=243¡Ê=35¡Ë
[4]º¸¤«¤é4¥Ó¥Ã¥ÈÌܤËÂФ·¤Æ
(a)p=p¡ßp=243¡ß243=59,049¡Ê=310¡Ë
[5]º¸¤«¤é5¥Ó¥Ã¥ÈÌܤËÂФ·¤Æ
(a)p=p¡ßp=59,049¡ß59,049=3,486,784,401¡Ê=320¡Ë
¡¡p=320¤òñ½ã·×»»¤¹¤ë¤È19²ó¾è»»¤¹¤ë¤³¤È¤Ë¤Ê¤ë¡Ê3¤Ë3¤ò19²ó¤«¤±¤Æ¤¤¤¯¡Ë¡£¤·¤«¤·¡¢¤³¤Î¥¢¥ë¥´¥ê¥º¥à¤ËŬ±þ¤·¤Æ¤ß¤ë¤È¡¢7²ó¤Î¾è»»¤ÇºÑ¤ó¤À¤Ï¤º¤À¡£
¡¡¤³¤ÎÎã¤Î¤è¤¦¤Ë2¿Ê¿ô¤Î·å¤¬5¤Î¤È¤¤Ï¡¢ºÇ°¤Î¾ì¹ç¤Ç¤â10²ó¤Î¾è»»¤ÇºÑ¤à¤Î¤Ç¤¢¤ë¡£
¡¡»Ø¿ô¤òN¤È¤¹¤ë¤È¡¢ÉáÄ̤η׻»¤Ç¤ÏO(N)¤Ç¤¢¤ë¤¬¡¢¤³¤ÎÊýË¡¤À¤ÈO(logN)¤Î·×»»Î̤ǺѤó¤Ç¤·¤Þ¤¦¡£
¡¡Ä̾ï¤Î¹â®¤Ù¤¾èË¡¤Ç»ÈÍѤ¹¤ëÊÑ¿ô¤ò¸º¤é¤¹¤³¤È¤¬¤Ç¤¤ë¡£
¡¡°Ê²¼xk-1=1¤È²¾Äꤹ¤ë¡£
¡¡¤Þ¤ºy=a¤È¤ª¤¯¡£
¡¡¼¡¤Ëi=k-2¤«¤é0¤Þ¤Ç°Ê²¼¤ò·«¤êÊÖ¤¹¡£
[Step1]
[Step2]xi=1¤Ê¤é¡¢
¡¡¤³¤Î¤è¤¦¤Ë¤¹¤ë¤È»ÈÍѤ¹¤ëÊÑ¿ô¤Ïy¤Î¤ß¤ÇºÑ¤à¡£
¡¡¤³¤Î¥¢¥ë¥´¥ê¥º¥à¤Ë¤ª¤±¤ë¾è»»²ó¿ô¤Ï¡¢x=(1,¡Ä,1)¤Î¤È¤ºÇÂç¤È¤Ê¤ê2(k-1)²ó¡¢Ê¿¶Ñ¤Ç1.5(k-1)²ó¤Ç¤¢¤ë¡£
Îã¡§x=19=(10011)2
¡¡¤³¤Î¤È¤¡¢¾è»»²ó¿ô¤Ï·×6²ó¤Ç¤¢¤ë¡£