|
Patok talabasi temirov amirxonning
|
| bet | 3/3 | | Sana | 05.12.2023 | | Hajmi | 4,57 Mb. | | #111714 |
Bog'liq 3-amaliy ish amir Argos, 1-амалий иш, 34564 qxmt ishchiDasturiy KODI:Java
import java.util.Scanner;
public class Polig_Hellman_algorithm {
public static long calculateModularExponentiation(long a, long e, long n) {
if (n == 1) return 0;
long result = 1;
a = a % n;
while (e > 0) {
if (e % 2 == 1)
result = (result * a) % n;
e /= 2;
a = (a * a) % n;
}
return result;
}
public static long to_divide_p(long n){
long a = 0, b = 1, i = 2;
long f = n - 1;
while (i <= f / 2){
if (f % i == 0) {
b = f / i;
if (b % i != 0 && i % b != 0) {
return i;
}
}
i++; }
return 0;}
public static long to_divide_q(long n){
long a = 0, b = 1, i = 2;
long f = n - 1;
while (i <= f / 2){
if (f % i == 0) {
b = f / i;
if (b % i != 0 && i % b != 0) {
return b;
}
}
i++;}
return 0; }
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
long n, a, b, a0 = 0, b0 = 0, m1 = 0, m2 = 0;
System.out.print("n = "); n = input.nextInt();
System.out.print("a = "); a = input.nextInt();
System.out.print("b = "); b = input.nextInt();
System.out.println("F(n) = n - 1 holatdan kelib chiqadi: F(" + n + ") = " + (n - 1));
System.out.println("41 ni tub kopaytuvchilarga ajratamiz: N = p * q; 41 = " + to_divide_p(n) + " * " + to_divide_q(n));
long A = calculateModularExponentiation(a, to_divide_q(n), n);
if (A == 1){
System.out.println("Yechimga ega emas!");
}else {
long B = calculateModularExponentiation(b, to_divide_q(n), n);
for (int i = 1; i <= n; i++) {
if (Math.pow(A, i) % n == B) {
a0 = i;
System.out.println("a0 = " + a0);
System.out.println("x = a0 mod p formuladan kelib chiqadi: x1 = " + a0 + " mod " + to_divide_p(n));
break;
}
}
long A1 = calculateModularExponentiation(a, to_divide_p(n), n);
if (A1 == 1) {
System.out.println("Yechimga ega emas!");
} else {
long B1 = calculateModularExponentiation(b, to_divide_p(n), n);
for (int i = 1; i <= n; i++) {
if (Math.pow(A1, i) % n == B1) {
b0 = i;
System.out.println("b1 = " + b0);
System.out.println("x = b0 mod q formuladan kelib chiqadi: x2 = " + b0 + " mod " + to_divide_q(n));
break;
}
}
m1 = to_divide_p(n);
m2 = to_divide_q(n);
System.out.println("Bundan kelib chiqadi: m1 = " + m1 + ", m2 = " + m2);
long x, M, M1, M2, M_1 = 0, M_2 = 0;
M = m1 * m2;
System.out.println("M = m1 * m2; M = " + m1 + " * " + m2 + " = " + M);
M1 = M / m1;
System.out.println("M1 = M / m1; M1 = " + M + " / " + m1 + " = " + M1);
M2 = M / m2;
System.out.println("M2 = M / m2; M2 = " + M + " / " + m2 + " = " + M2);
for (int i = 1; i <= n / 2; i++) {
if ((M1 * i) % m1 == 1) {
M_1 = i;
System.out.println("Endi esa M1 ni teskarisini topamiz M_1 = (" + M1 + " * " + i + ") mod " + m1 + " = " + M_1);
break;
}
}
for (int i = 1; i <= n / 2; i++) {
if ((M2 * i) % m2 == 1) {
M_2 = i;
System.out.println("Endi esa M2 ni teskarisini topamiz M_2 = (" + M2 + " * " + i + ") mod " + m2 + " = " + M_2);
break;
}
}
x = ((a0 * M1 * M_1) + (b0 * M2 * M_2)) % M;
System.out.println("x = (a0 * M1 * M_1 + b0 * M2 * M_2) mod M; formulaga asosan x ni topamiz.");
System.out.println("Javob: x = " + x);
}
}
}
}
JAVOBI:
|
| |
