|
Patok talabasi temirov amirxonning
|
| bet | 2/3 | | Sana | 05.12.2023 | | Hajmi | 4,57 Mb. | | #111714 |
Bog'liq 3-amaliy ish amir Argos, 1-амалий иш, 34564 qxmt ishchiJavob: yechimga ega emas;
14-variant:
Java dasturlash tilida bu misolni ishlanishi:
KODI:
public class Practicum3_Diskret {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int a, b, p, x, u = 0, v = 0;
//a = 10, b = 36, p = 41;
System.out.print("a = ");
a = input.nextInt();
System.out.print("b = ");
b = input.nextInt();
System.out.print("p = ");
p = input.nextInt();
int H = (int) (Math.sqrt(p) + 1);
System.out.println("H = " + H);
int C = (int) (Math.pow(a, H) % p);
System.out.println("C = " + C);
System.out.println();
for (int i = 1; i <= H; i++) {
u = (int) (Math.pow(C, i) % p);
System.out.print("u(" + i + ")= " + u + ", ");
}
System.out.println();
for (int j = 0; j <= H; j++) {
v = (int) (b * Math.pow(a, j) % p);
System.out.print("v(" + j + ")= " + v + ", ");
}
System.out.println();
System.out.println();
for (int i = 1; i <= H; i++) {
u = (int) (Math.pow(C, i) % p);
for (int j = 0; j <= H; j++) {
v = (int) (b * Math.pow(a, j) % p);
if (u == v) {
x = H * i - (j % p);
System.out.println("x = " + + H + " * " + i + " - (" + j + " mod " + p + ")= " + x);
}
}
}
}
}
Javobi:
Polig-Xelman algoritmi (Pohlig-Hellman)
Eyler teoremasi:
Agar, 𝑎, 𝑚 o‘zaro tub sonlar bo‘lsa u holda bo‘ladi, bu yerda 𝜑(𝑚) – Eyler funksiyasi. 𝜑 𝑁 = 𝑝𝑞 teng bo‘lsin, EKUB 𝑝, 𝑞 = 1. 𝑎𝑥 ≡ 𝑏 (𝑚𝑜𝑑 𝑝) ni yechish uchun Polig-Xelman algoritmi quyidagi yondashuvga asoslanadi. 𝑥 = 𝑎0 + 𝑎1𝑝 teng bo‘lsin.
Bundan
topulguncha, 𝑎0 ni tanlash yo‘li bilan topamiz va 𝑥 = 𝑎0 + 𝑎1𝑝 topulguncha, keyin 𝑥 ≡ 𝑎0 𝑚𝑜𝑑 𝑝.
Xuddi shu yo‘l oqali 𝑥 ≡ 𝑏0 𝑚𝑜𝑑 𝑞 ni ham topamiz. Shundan so‘ng qoldiqlar haqidagi Xitoy teoremasidan foydalanib 𝑥 ni topamiz.
|
| |
