큰 수의 계수를 계산하는 방법은 무엇입니까?

큰 수의 계수를 계산하는 방법은 무엇입니까?

---

계산기를 많이 사용하지 않고 5 ^ 55 계수 221의 계수를 계산하는 방법은 무엇입니까?

그런 것들을 계산하기위한 암호학의 수 이론에는 몇 가지 간단한 원칙이 있다고 생각합니다.

---

좋습니다 a^b mod m.. 먼저 순진한 접근 방식을 취한 다음이를 개선 할 수있는 방법을 살펴 보겠습니다.

먼저 a mod m. 그 말은 번호를 찾을 수 a1있도록 0 <= a1 < m하고 a = a1 mod m. 그런 다음 반복적으로 루프에서 곱하고 a1다시 줄 mod m입니다. 따라서 의사 코드에서 :

a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
    p *= a1
    p = p reduced mod m
}

이렇게하면보다 큰 숫자를 피할 수 m^2있습니다. 이것이 핵심입니다. 우리가보다 큰 숫자를 피하는 이유는 m^2모든 단계에서 0 <= p < m및 0 <= a1 < m.

예를 들어 5^55 mod 221. 첫째, 5이미 감소 mod 221합니다.

1. 1 * 5 = 5 mod 221
2. 5 * 5 = 25 mod 221
3. 25 * 5 = 125 mod 221
4. 125 * 5 = 183 mod 221
5. 183 * 5 = 31 mod 221
6. 31 * 5 = 155 mod 221
7. 155 * 5 = 112 mod 221
8. 112 * 5 = 118 mod 221
9. 118 * 5 = 148 mod 221
10. 148 * 5 = 77 mod 221
11. 77 * 5 = 164 mod 221
12. 164 * 5 = 157 mod 221
13. 157 * 5 = 122 mod 221
14. 122 * 5 = 168 mod 221
15. 168 * 5 = 177 mod 221
16. 177 * 5 = 1 mod 221
17. 1 * 5 = 5 mod 221
18. 5 * 5 = 25 mod 221
19. 25 * 5 = 125 mod 221
20. 125 * 5 = 183 mod 221
21. 183 * 5 = 31 mod 221
22. 31 * 5 = 155 mod 221
23. 155 * 5 = 112 mod 221
24. 112 * 5 = 118 mod 221
25. 118 * 5 = 148 mod 221
26. 148 * 5 = 77 mod 221
27. 77 * 5 = 164 mod 221
28. 164 * 5 = 157 mod 221
29. 157 * 5 = 122 mod 221
30. 122 * 5 = 168 mod 221
31. 168 * 5 = 177 mod 221
32. 177 * 5 = 1 mod 221
33. 1 * 5 = 5 mod 221
34. 5 * 5 = 25 mod 221
35. 25 * 5 = 125 mod 221
36. 125 * 5 = 183 mod 221
37. 183 * 5 = 31 mod 221
38. 31 * 5 = 155 mod 221
39. 155 * 5 = 112 mod 221
40. 112 * 5 = 118 mod 221
41. 118 * 5 = 148 mod 221
42. 148 * 5 = 77 mod 221
43. 77 * 5 = 164 mod 221
44. 164 * 5 = 157 mod 221
45. 157 * 5 = 122 mod 221
46. 122 * 5 = 168 mod 221
47. 168 * 5 = 177 mod 221
48. 177 * 5 = 1 mod 221
49. 1 * 5 = 5 mod 221
50. 5 * 5 = 25 mod 221
51. 25 * 5 = 125 mod 221
52. 125 * 5 = 183 mod 221
53. 183 * 5 = 31 mod 221
54. 31 * 5 = 155 mod 221
55. 155 * 5 = 112 mod 221

따라서 5^55 = 112 mod 221.

이제 우리는 제곱에 의한 지수를 사용하여 이것을 개선 할 수 있습니다 ; 이것은 우리 log b가 b. 대신 곱셈 만 요구하도록 지수를 줄이는 유명한 트릭 입니다 . 위에서 설명한 알고리즘, 제곱 개선에 의한 지수화를 사용하면 오른쪽에서 왼쪽으로 이진 방법으로 끝납니다 .

a1 = a reduced mod m
p = 1
while (b > 0) {
     if (b is odd) {
         p *= a1
         p = p reduced mod m
     }
     b /= 2
     a1 = (a1 * a1) reduced mod m
}

따라서 이진수로 55 = 110111이므로

1. 1 * (5^1 mod 221) = 5 mod 221
2. 5 * (5^2 mod 221) = 125 mod 221
3. 125 * (5^4 mod 221) = 112 mod 221
4. 112 * (5^16 mod 221) = 112 mod 221
5. 112 * (5^32 mod 221) = 112 mod 221

따라서 대답은 5^55 = 112 mod 221입니다. 이것이 작동하는 이유는

55 = 1 + 2 + 4 + 16 + 32

그래서

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
     = 5 * 25 * 183 * 1 * 1 mod 221
     = 22875 mod 221
     = 112 mod 221

우리가 계산하는 단계에서 5^1 mod 221, 5^2 mod 221등 우리가 유의 5^(2^k)= 5^(2^(k-1)) * 5^(2^(k-1))때문에 2^k = 2^(k-1) + 2^(k-1)우리는 먼저 계산할 수 있도록를 5^1줄일 mod 221후 사각형이 감소하고 mod 221구하는 5^2 mod 221등,

위의 알고리즘은이 아이디어를 공식화합니다.

---

Jason의 답변에 추가하려면 :

지수의 이진 확장을 사용하여 프로세스 속도를 높일 수 있습니다 (매우 큰 지수에 도움이 될 수 있음). 먼저 5, 5 ^ 2, 5 ^ 4, 5 ^ 8 mod 221을 계산합니다.이 작업은 반복 제곱으로 수행합니다.

 5^1 = 5(mod 221)
 5^2 = 5^2 (mod 221) = 25(mod 221)
 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)

이제 우리는 쓸 수 있습니다

55 = 1 + 2 + 4 + 16 + 32

so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 
        = 5   * 25  * 625 * 1    * 1 (mod 221)
        = 125 * 625 (mod 221)
        = 125 * 183 (mod 183) - because 625 = 183 (mod 221)
        = 22875 ( mod 221)
        = 112 (mod 221)

매우 큰 지수의 경우 이것이 훨씬 더 빠르다는 것을 알 수 있습니다 (b의 선형과 반대되는 로그라고 생각하지만 확실하지는 않습니다).

---

/* The algorithm is from the book "Discrete Mathematics and Its
   Applications 5th Edition" by Kenneth H. Rosen.
   (base^exp)%mod
*/

int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int power = base % mod;

    for (int i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}

---

5^55 mod221

= (   5^10         * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221    

= ( ( 5^10) mod221 * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= (   77           * 5^10         * 5^10         * 5^10          * 5^10          * 5^5) mod221   

= ( ( 77           * 5^10) mod221 * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= (   183                         * 5^10         * 5^10          * 5^10          * 5^5) mod221 

= ( ( 183                         * 5^10) mod221 * 5^10          * 5^10          * 5^5) mod221 

= (   168                                        * 5^10          * 5^10          * 5^5) mod221 

= ( ( 168                                        * 5^10) mod 221 * 5^10          * 5^5) mod221 

= (   118                                                        * 5^10          * 5^5) mod221 

= ( ( 118                                                        * 5^10) mod 221 * 5^5) mod221 

= (   25                                                                         * 5^5) mod221 

=     112

---

찾고있는 것은 모듈 식 지수, 특히 모듈 식 이진 지수입니다. 이 wikipedia 링크 에는 의사 코드가 있습니다.

---

Chinese Remainder Theorem 은 221 = 13 * 17과 같은 초기 점으로 떠 오릅니다. 따라서 이것을 마지막에 결합되는 두 부분으로 나누십시오. 하나는 mod 13이고 하나는 mod 17입니다. 둘째, 몇 가지 증거가 있다고 생각합니다. of a ^ (p-1) = 1 mod p for all non zero a 이것은 또한 5 ^ 55가 13 * 4 = 52로 mod 13 케이스에 대해 5 ^ 3이되므로 문제를 줄이는 데 도움이됩니다. "유한 필드"라는 주제를 살펴보면이 문제를 해결하는 방법에 대한 좋은 결과를 찾을 수 있습니다.

편집 : 내가 요소를 언급 한 이유는 13 ^ 2 * 17 ^ 4 mod 221과 같은 것을 시도한 것처럼 0이 아닌 요소로 0을 인수하는 방법을 생성하기 때문입니다 .13 * 17 = 221이기 때문에 대답은 0입니다. 많은 큰 숫자는 소수가되지 않을 것입니다. 그러나 큰 소수는 수학 내의 암호화 및 기타 영역에서 많이 사용되기 때문에 큰 소수를 찾는 방법이 있습니다.

---

This is part of code I made for IBAN validation. Feel free to use.

    static void Main(string[] args)
    {
        int modulo = 97;
        string input = Reverse("100020778788920323232343433");
        int result = 0;
        int lastRowValue = 1;

        for (int i = 0; i < input.Length; i++)
        {
            // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number                                                                        
            if (i > 0)
            {
                lastRowValue = ModuloByDigits(lastRowValue, modulo);
            }
            result += lastRowValue * int.Parse(input[i].ToString());
        }
        result = result % modulo;
        Console.WriteLine(string.Format("Result: {0}", result));            
    }

    public static int ModuloByDigits(int previousValue, int modulo)
    {
        // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number                        
        return ((previousValue * 10) % modulo);
    }
    public static string Reverse(string input)
    {
        char[] arr = input.ToCharArray();
        Array.Reverse(arr);
        return new string(arr);
    }

---

Jason's answer in Java (note i < exp).

private static void testModulus() {
    int bse = 5, exp = 55, mod = 221;

    int a1 = bse % mod;
    int p = 1;

    System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod);

    for (int i = 1; i < exp; i++) {
        p *= a1;
        System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod);
        p = (p % mod);
    }

}

---

This is called modular exponentiation(https://en.wikipedia.org/wiki/Modular_exponentiation).

Let's assume you have the following expression:

19 ^ 3 mod 7

Instead of powering 19 directly you can do the following:

(((19 mod 7) * 19) mod 7) * 19) mod 7

But this can take also a long time due to a lot of sequential multipliations and so you can multiply on squared values:

x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N

Modular exponentiation algorithm makes assumptions that:

x ^ y == (x ^ |y/2|) ^ 2 if y is even
x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd

And so recursive modular exponentiation algorithm will look like this in java:

/**
* Modular exponentiation algorithm
* @param x Assumption: x >= 0
* @param y Assumption: y >= 0
* @param N Assumption: N > 0
* @return x ^ y mod N
*/
public static long modExp(long x, long y, long N) {
    if(y == 0)
        return 1 % N;

    long z = modExp(x, Math.abs(y/2), N);

    if(y % 2 == 0)
        return (long) ((Math.pow(z, 2)) % N);
    return (long) ((x * Math.pow(z, 2)) % N);
}

Special thanks to @chux for found mistake with incorrect return value in case of y and 0 comparison.

---

Just provide another implementation of Jason's answer by C.

After discussing with my classmates, based on Jason's explanation, I like the recursive version more if you don't care about the performance very much:

For example:

#include<stdio.h>

int mypow( int base, int pow, int mod ){
    if( pow == 0 ) return 1;
    if( pow % 2 == 0 ){
        int tmp = mypow( base, pow >> 1, mod );
        return tmp * tmp % mod;
    }
    else{
        return base * mypow( base, pow - 1, mod ) % mod;
    }
}

int main(){
    printf("%d", mypow(5,55,221));
    return 0;
}

참고URL : https://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers