ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

­ˤݤ

㤨С35פ­ǽ뤳Ȥͤ롣

  1. 3+3+3+3+335­
  2. 55553­

ꭢΤۤ׻ʤ

CASLξ

㡧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
SMP0311   START     
          LD        GR0,=0
          LD        GR1,=1
          LD        GR3,A
          LD        GR4,B
          CPA       GR3,GR4
          JMI       LOOP
          JZE       LOOP
          LD        GR5,GR3
          LD        GR3,GR4
          LD        GR4,GR5
LOOP      ADDA      GR0,GR4
          JOV       OVF
          SUBA      GR3,GR1
          JPL       LOOP
          ST        GR0,ANS
          RET       
OVF       OUT       OVERFLOW,M8
A         DC        5
B         DC        3
ANS       DS        1
OVERFLOW  DC        'OverFlow'
M8        DC        8
          END       

ǽCPA̿JMI̿JZE̿ΥåȤǡGR3GR4羮Ӥ򤷤Ƥ롣GR4礭褦ˤƳݤѤΥ롼פǷ׻򾯤ʤ뤿Ǥ롣GR4ΤۤGR3꾮ϡGR5ѤΥ쥸ȤƳѤơGR3GR4ȤؤƤ롣ʤ­ΤȤСեȯOverFlowפɽ롣

եȱ黻Ѥˤݤ

ҤȤĺեȤ2ܤ뤬ޤѤ뤳ȤǤդγݤǤ롣

CASLξ

㡧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
SMP0321   START     
          LD        GR0,=0
          LD        GR3,A
          LD        GR4,B
LOOP      LD        GR1,GR3
          AND       GR1,MASK
          JZE       STEP
          ADDA      GR0,GR4
          JOV       OVF
STEP      SLL       GR4,1
          SRL       GR3,1
          JNZ       LOOP
          ST        GR0,ANS
          RET       
OVF       OUT       OVERFLOW,M8
          RET       
A         DC        3
B         DC        20
ANS       DS        1
MASK      DC        #0001
OVERFLOW  DC        'OverFlow'
M8        DC        8
          END       

®٤ˡ

ElGamalŹRSAŹMiler-RabinƥȤɤˤϼιƱΥסˡäƤ뤳ȤաˤΤ٤׻򤹤ɬפ롣

y=a^x~\,~\(mod~\,~n\)

ñx-1ξ軻ԤȤˤʤäƤޤx-12ʤΤǻؿ֤롣Ǥ¿༰֤η׻Ǥʤåpoly-time르ꥺˤϻΩʤ

Υ르ꥺǽ뤳Ȥǡ׻̤򸺤餹ȤǤ롣

p=aka,k,p

[]pФơp1Ƚͤ롣

[]k2ʥӥåȥѥ̥ӥåȤ1ӥåȤĸƤƥӥåȤФƼ롣

(a)ޤp2褹롣
ppp

(b)ΥӥåȤ1ʤ顢a򤫤롣
ppa

⤷ˡnǹͤƤʤ顢ȤˡnŬѤ롣ж̤⸺餹ȤǤ롣

㡧p=320׻a=3,k=20ˡ

[]p=1

[]202ʿ10100ǤΤǡ

[1]ֺΥӥå1Ф
(a)p=pp=11=1
(b)p=pa=13=3=31

[2]2ӥåܤФ
(a)p=pp=33=9=32

[3]3ӥåܤФ
(a)p=pp=99=81=34
(b)p=pa=813=243=35

[4]4ӥåܤФ
(a)p=pp=243243=59,049=310

[5]5ӥåܤФ
(a)p=pp=59,04959,049=3,486,784,401=320

p=320ñ׻19軻뤳Ȥˤʤ3319󤫤ƤˡΥ르ꥺŬƤߤȡ7ξ軻ǺѤϤ

\(~\(~\(~3^{2}~\)^{2}~3~\)^{2}~\)^{2}

Τ褦2ʿη夬5ΤȤϡǰξǤ10ξ軻ǺѤΤǤ롣

ؿNȤȡ̤η׻ǤO(N)Ǥ뤬ˡO(logN)η׻̤ǺѤǤޤ

ɤ줿®٤ˡ

̾ι®٤ˡǻѤѿ򸺤餹ȤǤ롣

ʲxk-1=1Ȳꤹ롣

ޤy=aȤ

i=k-20ޤǰʲ򷫤֤

[Step1]y_{i}=y^{2}~\,~\(~mod~\,~n~\)

[Step2]xi=1ʤ顢y=y~\times~a~\,~\(~mod~\,~n~\)

Τ褦ˤȻѤѿyΤߤǺѤࡣ

Υ르ꥺˤ軻ϡx=(1,,1)ΤȤȤʤ2(k-1)ʿѤ1.5(k-1)Ǥ롣

㡧x=19=(10011)2

y~\overset{2}{\leftarrow}~a^{2}~=~a^{\(~10~\)_{2}}~\,~\(~mod~\,~n~\)

y~\overset{2}{\leftarrow}~y^{2}~=~a^{\(~100~\)_{2}}~\,~\(~mod~\,~n~\)

y~\overset{1}{\leftarrow}~y^{2}~\times~a~=~a^{\(~1000~\)_{2}}~\times~a~=~a^{\(~1001~\)_{2}}~\,~\(~mod~\,~n~\)

y~\overset{1}{\leftarrow}~y^{2}~\times~a~=~a^{\(~10010~\)_{2}}~\times~a~=~a^{\(~10011~\)_{2}}~\,~\(~mod~\,~n~\)

ΤȤ軻Ϸ6Ǥ롣

ʸ

  • ظŹδÿ
  • ؾCASLIICASLIIιֵȼ½[2]