☰

지수가 증가하지 않도록 각 반복에서 지수 값을 감소시키는 지수 함수를 어떻게 스크립트할 수 있습니까?

tag-icon • tag-icon bash shell-script bc math
지수가 증가하지 않도록 각 반복에서 지수 값을 감소시키는 지수 함수를 어떻게 스크립트할 수 있습니까?

Linux를 처음 접하고 이 스크립트를 실행하는 데 문제가 있습니다.

많은 수를 취하고 나머지(모듈로)를 사용하여 결과를 저장하는(메모리 절약을 위해) 몇 가지 방법을 연구해 왔습니다.

bash 쉘을 사용하여 78390^91025(mod 180577)를 계산하려고 하므로 기본 78290을 91025의 거듭제곱으로 사용하고 모듈로 180577을 적용합니다.

나는 다음 논리를 얻고 싶습니다: y=base for i = 1의 지수-1 y := (y*base) mod 'modulus' next i print y

이렇게 하면 올바른 결과를 얻으면서 메모리와 저장 공간을 절약할 수 있기를 바랍니다.

코드를 만지작거리고 있는데 지금은 실행할 수 없습니다. 어디서 엉망이 되었나요?

#!/bin/bash

#   k^x (mod n)
#   with k=78390, x=91025, n=180577 ?
#   Script runs but no output, 
#   pretty sure it is close

powmod() {
 let "a=1"
 let "k=$1"
 let "x=$2"
     let "n=$3"
     while (( x )); do
       if (( x % 2 )); then
            (( a = a*k % n ))
            (( x = x-1 ))
       fi
          (( k = k*k % n ))
            (( x = x/2 ))
     done
     echo $a;
    }

답변1

음, , 을 사용하여 를 k^x (mod n)계산 하려고 합니다 . 가장 간단한 방법은 실제로 의사 코드에 표시된 것처럼 base( )에 누산기를 반복적으로 곱하는 것입니다. 이 작업을 수행하는 Bash 함수는 다음과 같습니다.k=78390x=91025n=180577k

powmod() { 
    local a=1 k=$1 x=$2 n=$3;
    for (( ; x; x-- )) { 
        (( a=a*k % n ));
    };
    echo $a;
}

이제 powmod 78390 91025 180577인쇄하십시오 125. (결과는 다음과 같습니다.Wolfram Alpha가 제공하는 것.)

a0 인덱스는 기본( k^0 = 1, 무엇이든 )이 아닌 1을 반환해야 하기 때문에 기본이 아닌 1로 초기화해야 합니다 k.

대체 구현 bc:

k=78390
x=91025
n=180577
a=1
while (x > 0) {
    a=a*k % n
    x=x-1
}
a

당연히 bcBash보다 빠릅니다.

단순한 루프 대신에 더 똑똑한 방법은 다음과 같습니다.제곱 곱셈 알고리즘. 위와 달리 log2(x)연산 만 사용하기 때문에 훨씬 빠릅니다 x.

배쉬에서:

powmod2() { 
    local a=1 k=$1 x=$2 n=$3;
    while (( x )); do 
        if (( x % 2 )); then
            (( a = a*k % n ))
            (( x = x-1 ))
        fi
        (( k = k*k % n ))
        (( x = x/2 ))
    done
    echo $a;
}

이 크기의 숫자에 대해서는 상당히 빠르지만 임시 값( a*k또는 k*k모듈러스 앞)이 Bash가 처리할 수 있는 것보다 크면 자동 오류가 발생한다는 점에 유의하세요. (여기의 숫자는 180577*18057764비트에 적합하므로 괜찮습니다.)

하드코딩된 제한 없이 오버플로를 감지하는 쉬운 방법이 생각나지 않으므로 bc어떤 경우에도 사용하고 싶을 수 있습니다.

k=78390 
i=91025         
n=180577
a=1     
while (i > 0) {
        if (i % 2) {
                a=a*k % n
                i=i-1
        }
        k=k*k % n
        i=i/2
}    
a

bc(셸 함수 내에서 호출을 유지하는 것은 쉽지 않습니다.)

관련 정보