Phép toán Modular Arithmetic trong Java

[Quang.Andrei]

Chào mọi người, trong quá trình giải toán thì em có phải tính phép tính 36^35 mod 65, em có giải tay và sử dụng Java để tính kết quả của phép tính. Java cho kết quả là 7.0 còn em tính ra 56.

Được biết kết quả 56 của anh là chính xác, em giải tay bằng cách sau:

36^5 mod 65 = 56 ( mod 65)

36^10 mod 65 = 16 ( mod 65)

36^20 mod 65 = (16*16) mod 65 = 61( mod 65)

vậy nên 36^35=36^5 mod 65 *36^10 mod 65* 36^20 mod 65

=> 36^35 mod 65 : 16*16*16*56 mod 65 = 56;

Em không tin Java có thể tính sai vì vậy em muốn hỏi mọi người em viết chương trình tính như vậy có điểm gì sai ạ? Cách tính tay của em liệu có tối ưu và nhanh trong trường hợp đi thi không ạ?

Em cảm ơn ạ

[tntxtnt]

kiểu số thực double chỉ lưu chính xác được tối đa 16 chữ số thôi, em bấm 36^35 thế kia thì quá 16 chữ số mất rồi nên chữ số thứ 17 18 v.v… nó bỏ mất thì làm sao chính xác được

[noname00 (HK boy)]

Đi thi còn tính hàng trăm, hàng nghìn phép tính mũ khác, mình không mong bạn if else tay từng cơ số một

Không biết bạn đi thi gì vậy?

[Quang.Andrei]

Em có đang làm bài toán mã hoá RSA ạ, đi thi giấy chỉ có máy casio thôi ạ, em muốn thử kết quả mình tính chay có đúng ko thôi ạ.

[noname00 (HK boy)]

Nếu để mũ lấy mod tính nhanh thì bạn có thể dùng hàm phi Euler (Euler’s Totient Function).

\displaystyle \phi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right) với p là các ước nguyên tố của n và \displaystyle a^{\phi(n)} \equiv 1\ \mod\ n

Tuy nhiên nếu số mũ nhỏ hơn phi(n) thì tính tách mũ còn tiện hơn.

VD: 36^{35} \mod 65

\displaystyle \phi(65)=65\left(1-\frac{1}{5}\right)\left(1-\frac{1}{13}\right)=48>35

36^{35}\\ \equiv\left(36^2\right)^{17}*36\equiv(-4)^{17}*36\\ \equiv\left((-4)^{3}\right)^5*16*36\equiv (-64)^5*(-9)\\ \equiv 1^5*(-9)\equiv -9\equiv 56\ \mod\ 65

Đi thi như vậy nên áp dụng toán học là chủ yếu, không nên phụ thuộc vào máy tính

[rogp10]

Tức là tính lambda(65) hay hàm Carmichael

Hàm Carmichael: cho pttsnt n = pi(p[i]^e[i]), vậy lambda(n) = BCNN(phi(p[i]^e[i])) = BCNN((p[i]-1)*(p[i]^(e[i] - 1)) i=1..n.
Vì chu kì mod 13 là 12 và chu kì mod 5 là 4 nên lấy BCNN của hai chu kì
35 mod 12 = 11 nên có thể tính 36^11 mod 65.
36^{1, 2, 4, 8…}: 36 -4 16 -4 => à 36^6 mod 65 = 1 vậy 36^5 = 36*16 = 576 = 65*9 - 9 = 56 (mod 65)