十進BASIC 第2掲示板 過去ログ

!RSA公開鍵暗号の計算

PRINT modpow(1371,1241,2279) !1371を暗号化する。公開鍵43*53=2279と1241

PRINT eul(2279) !=2184、43と53と2184は秘密
PRINT gcd(43,53) !互いに素
PRINT gcd(2184,1241) !互いに素

PRINT modinv(1241,2184) !秘密鍵1649

PRINT modpow(2003,1649,2279) !2003を複合化する


!ｎの１より大きな最小の約数
PRINT prmdiv(1234567) !127
PRINT prmdiv(23456789) !23456789
!PRINT prmdiv(11111111111111111) !2071723


!素数の生成
PRINT prm(100) !541
PRINT nxtprm(999) !prm(1000)=7919
!PRINT nxtprm(9999) !prm(10000)=104729


!オイラー関数（１からｎまでの自然数のうちｎと互いに素なものの個数）
FOR N=2 TO 100
   LET S=0
   FOR i=1 TO N-1
      IF GCD(N,i)=1 THEN LET S=S+1
   NEXT i
   PRINT N;S, eul(N)
NEXT N


FOR i=2 TO 100
   PRINT USING "#### #### #### ####": i,fnSigma(i),eul(i),moeb(i)
NEXT i


END



!整数論関連　※ubasicより

EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数
IF MOD(n,2)=0 THEN !２の倍数
   LET prmdiv=2
ELSEIF MOD(n,3)=0 THEN !３の倍数
   LET prmdiv=3
ELSE
   FOR i=5 TO SQR(n) STEP 6
   !!!FOR i=5 TO INTSQR(n) STEP 6 !<----- ※有理数モード
      IF MOD(n,i)=0 THEN !5,11,17,23,29,…
         LET prmdiv=i
         EXIT FUNCTION
      ELSEIF MOD(n,i+2)=0 THEN !7,13,19,25,31,…
         LET prmdiv=i+2
         EXIT FUNCTION
      END IF
   NEXT i
   LET prmdiv=n !その数自身
END IF
END FUNCTION

EXTERNAL FUNCTION eul(n) !オイラー関数 φ(n)（１からｎまでの自然数のうちｎと互いに素なものの個数）
LET t=n
IF MOD(n,2)=0 THEN
   LET t=t/2
   DO
      LET n=n/2
   LOOP WHILE MOD(n,2)=0
END IF
LET d=3
DO WHILE n/d>=d
   IF MOD(n,d)=0 THEN
      LET t=t/d*(d-1)
      DO
         LET n=n/d
      LOOP WHILE MOD(n,d)=0
   END IF
   LET d=d+2
LOOP
IF n>1 THEN LET t=t/n*(n-1)
LET eul=t
END FUNCTION

EXTERNAL FUNCTION moeb(n) !メビウス関数 μ(n)
LET W=1
DO WHILE n>1
   LET P=prmdiv(n)
   IF MOD(n,P^2)=0 THEN
      LET W=0
      EXIT DO
   END IF
   LET W=-W
   LET n=INT(n/P)
LOOP
LET moeb=W
END FUNCTION

EXTERNAL FUNCTION modpow(a,b,n) !a^b≡x mod n のxを返す
IF b=0 THEN
   LET modpow=1
ELSE
   LET S=1
   DO WHILE b>0
      IF MOD(b,2)=1 THEN LET S=MOD(S*a,n) !ビットが１なら計算する
      LET b=INT(b/2) !べき乗bを２進展開する
      LET a=MOD(a*a,n)
   LOOP
END IF
LET modpow=S
END FUNCTION

EXTERNAL FUNCTION modinv(a,n) !nを法としたaの逆元　a*x (mod n)=1
LET M=n
LET Sa=1
LET Ta=0
DO WHILE M<>0
   LET Q=INT(a/M)
   LET U=a-Q*M
   LET Ua=Sa-Q*Ta
   LET a=M
   LET Sa=Ta
   LET M=U
   LET Ta=Ua
LOOP
IF a<>1 THEN
   LET modinv=0
ELSE
   IF Sa<0 THEN LET Sa=Sa+n
   LET modinv=Sa
END IF
END FUNCTION

EXTERNAL FUNCTION prm(n) !n番目の素数　※nは１以上
DIM prime(n) !素数列
LET prime(1)=2 !１番目は２
LET k=2 !k番目
LET x=1 !検証する自然数
DO WHILE k<=n !N番目まで
   LET x=x+2 !奇数が対象
   LET j=1 !見つかった素数の倍数かどうか確認する
   DO WHILE j<k AND MOD(x,prime(j))<>0 !倍数なら途中で終了
      LET j=j+1
   LOOP
   IF j=k THEN !新しく見つかった素数を記録する
      LET prime(k)=x
      LET k=k+1
   END IF
LOOP
LET prm=prime(n)
END FUNCTION

EXTERNAL FUNCTION nxtprm(n) !n+1番目の素数
LET nxtprm=prm(n+1)
END FUNCTION

EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION

EXTERNAL FUNCTION lcm(a,b) !最小公倍数
LET lcm=a*b/gcd(a,b)
END FUNCTION


!ユーザー定義

EXTERNAL FUNCTION fnSigma(n) !約数の和 σ(n)
LET S=1
DO WHILE n>1
   LET W=1
   LET P=prmdiv(n)
   DO
      LET W=W*P+1
      LET n=INT(n/P)
   LOOP WHILE MOD(n,P)=0
   LET S=S*W
LOOP
LET fnSigma=S
END FUNCTION

EXTERNAL FUNCTION nxtprm(x) !xより大きい素数の最小のもの
   DIM prime(x)

   FOR i=1 TO 10 !最初の10個
      READ prime(i)
      IF x<prime(i) THEN
         LET nxtprm=prime(i)
         EXIT FUNCTION
      END IF
   NEXT i
   DATA 2,3,5,7,11,13,17,19,23,29

   FOR i=11 TO INT(x) !11個目以降
      LET m30=MOD(prime(i-1),30)
      IF m30=1 OR m30=23 THEN LET a=prime(i-1)+6 ELSE LET a=prime(i-1)-2*MOD(m30,3)+6
      DO
         LET sqra=SQR(a)
         !!!LET sqra=INTSQR(a) !<----- ※有理数モード
         FOR j=4 TO i-1
            IF MOD(a,prime(j))=0 THEN EXIT FOR
            IF prime(j)>=sqra THEN
               LET prime(i)=a
               EXIT DO
            END IF
         NEXT j
         LET m30=MOD(a,30)
         IF m30=1 OR m30=23 THEN LET a=a+6 ELSE LET a=a-2*MOD(m30,3)+6
      LOOP

      IF x<prime(i) THEN
         LET nxtprm=prime(i)
         EXIT FUNCTION
      END IF
   NEXT i

   PRINT "見つかりません。"
   STOP
END FUNCTION

!素数の個数
!PRINT fnPrimePi(77777)


!原始根 genshi3
FOR LP=1 TO 100
   LET P=prm(LP) !最初の100個の素数に対して

   PRINT USING "##### ### |": P,fnGenshi(P);
   IF MOD(LP,5)=0 THEN PRINT
NEXT LP
PRINT


!原始根 genshi2
FOR LP=1 TO 100
   LET P=prm(LP) !最初の100個の素数に対して

   LET G=1
   IF P<>2 THEN
50       LET G=G+1
         LET W=1
         FOR i=1 TO P-2
            LET W=MOD(W*G,P)
            IF W=1 THEN GOTO 50
         NEXT i
      END IF

      PRINT USING "##### ### |": P,G;
      IF MOD(LP,5)=0 THEN PRINT
   NEXT LP
   PRINT


END


EXTERNAL FUNCTION fnPrimePi(X) !実数xに対しx以下の素数の個数
   LET S=1
   LET E=10000 !100,000以下の素数は10,000個未満だから　※
   DO WHILE E>S+1
      LET K=INT((S+E)/2) !２分探索
      IF prm(K)<=X THEN LET S=K ELSE LET E=K
   LOOP
   LET fnPrimePi=S
END FUNCTION

EXTERNAL FUNCTION fnGenshi(P) !原始根
   LET G=1
   LET N=P-1
   IF P<>2 THEN
180    LET G=G+1
       LET Nw=N
       DO
          LET Div=prmdiv(Nw)
          DO WHILE MOD(Nw,Div)=0
             LET Nw=INT(Nw/Div)
          LOOP
          IF modpow(G,INT(N/Div),P)=1 THEN GOTO 180
       LOOP UNTIL Nw=1
    END IF
    LET fnGenshi=G
 END FUNCTION