Tính số mũ rất lớn trong python

Question

Hiện tại tôi đang mô phỏng sơ đồ mã hóa của mình để kiểm tra nó. Tôi đã phát triển mã nhưng tôi bị kẹt tại một thời điểm.

Tôi cố gắng để thực hiện: g**x nơi

g = 256 bit number 
x = 256 bit number 

Python treo vào thời điểm này, tôi đã đọc rất nhiều diễn đàn, chủ đề etcc nhưng chỉ đi đến kết luận rằng trăn treo, như khó khăn của mình cho nó để xử lý những con số lớn như vậy.

bất kỳ ý tưởng nào có thể thực hiện được? bất kỳ đoạn mã hai dòng nào, bất kỳ thư viện nào, bất kỳ thứ gì có thể được thực hiện.

Answer 1

Nó không treo, nó chỉ là chế biến. Nó sẽ cuối cùng cung cấp cho bạn câu trả lời, miễn là nó không hết bộ nhớ trước.

Tôi chưa từng nghe về kết quả của quá trình như vậy đang được sử dụng trong mật mã; thường thì đó là mô-đun của quyền lực đã nói. Nếu trường hợp này giống nhau trong trường hợp của bạn thì bạn chỉ có thể sử dụng biểu mẫu 3 đối số là pow().

Answer 2

Tôi không hoàn toàn chắc chắn rằng bạn đánh giá cao tầm quan trọng tuyệt đối của những gì bạn đang yêu cầu Python làm. Nâng thứ gì đó lên sức mạnh x trong đó x dài 256 bit, đang thực hiện tương đương với 2 ** 256 phép nhân hoặc 115792089237316195423570985008687907853269984665640564039457584007913129639936 phép nhân. Như bạn có thể tưởng tượng, điều này có thể mất một thời gian. Và không gian, mà tôi đảm bảo bạn không có đủ.

Answer 3

Bạn không nên tính toán x^y trực tiếp cho các giá trị lớn của y - như đã được chỉ ra, điều này khá khó thực hiện (mất nhiều không gian và sức mạnh xử lý). Bạn cần phải xem xét các thuật toán giải quyết vấn đề cho bạn với ít hoạt động nhân. Hãy xem: http://en.wikipedia.org/wiki/Exponentiation_by_squaring để bắt đầu.

Độ lớn mô đun cũng được hiểu rõ: http://en.wikipedia.org/wiki/Modular_exponentiation.

Bạn sẽ cần sử dụng thư viện python cho số lớn, chẳng hạn như http://gmpy.sourceforge.net/.

Nếu có bất kỳ trợ giúp nào, tôi đã tính lũy thừa mô đun trong C bằng cách sử dụng mpir. Tôi sẽ đính kèm mã đó, bạn sẽ cần phải chuyển đổi nó thành python của khóa học.

int power_modn(mpz_t c, mpz_t b, mpz_t e, mpz_t n) 
{ 
     mpz_t result; 
     mpz_t one; 
     mpz_t r; 

     mpz_t modulus; mpz_t exponent; mpz_t base; 

     mpz_init(modulus); mpz_init(exponent); mpz_init(base); 
     mpz_init(result); mpz_init(one); mpz_init(r); 

     mpz_set_ui(result, 1); 
     mpz_set_ui(one, 1); 

     mpz_set(base, b); 
     mpz_set(exponent, e); 
     mpz_set(modulus, n); 

     while (mpz_cmp_ui(exponent, 0) > 0) 
     { 
       if (mpz_mod_ui(r, exponent, 2) == 1) 
       { 
         mpz_mul(result, result, base); 
         mpz_mod(result, result, modulus); 
       }; 
       mpz_mul(base, base, base); 
       mpz_mod(base, base, modulus); 
       mpz_fdiv_q_ui(exponent, exponent, 2); 
     } 

     mpz_set(c, result); 
    return 0; 
}