|
Kiberxavfsizlik” fakulteti 713-21- guruh cry
|
| bet | 1/5 | | Sana | 15.02.2024 | | Hajmi | 3,64 Mb. | | #156960 |
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
“KIBERXAVFSIZLIK” FAKULTETI
713-21- guruh CRY002 - 1 - patok talabasi
OBIDOV BOBIRJONning
“Kriptografiya” fanidan tayyorlagan
4-5-AMALIY ISHI
Topshirdi: Obidov B.
Tekshirdi: Jabborov N.
TOSHKENT - 2023
4-amaliy ish.
Mavzu: Sonlarni tublikka tekshirish algoritmlari va ularning dasturiy ta’minotini ishlab chiqish.
Endi o‘zimga berilgan variantdagi sonni tublikka tekshirish uchun dasturiy kodi tuzaman.
10 - variant.
Dastur kodi:
Dastur kodi:
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
public class RabinMillerTest {
// Rabin-Miller sanoq sinov tizimi
public static boolean isPrime(BigInteger n, int k) {
// Agar n < 2 bo'lsa, u tub emas
if (n.compareTo(BigInteger.valueOf(2)) < 0) {
return false;
}
// n-1 = 2^s * d formatidagi sonni topish
BigInteger d = n.subtract(BigInteger.ONE);
int s = 0;
while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
d = d.divide(BigInteger.valueOf(2));
s++;
}
// k marta sinovdan o'tkazish
for (int i = 0; i < k; i++) {
if (!millerRabinTest(n, d, s)) {
return false; // Son tub emasligini aniqlash
}
}
return true; // Son tubligini aniqlash
}
// Miller-Rabin sinov
private static boolean millerRabinTest(BigInteger n, BigInteger d, int s) {
Random rand = new Random();
BigInteger a = new BigInteger(n.bitLength(), rand);
a = a.mod(n.subtract(BigInteger.valueOf(2))).add(BigInteger.valueOf(2)); // 2 va n-2 orasidagi tasodifiy sonni tanlash
BigInteger x = a.modPow(d, n);
if (x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) {
return true; // Agar x = 1 yoki x = n-1 bo'lsa, sinov muvaffaqiyatli tugadi
}
for (int r = 1; r < s; r++) {
x = x.modPow(BigInteger.valueOf(2), n);
if (x.equals(BigInteger.ONE)) {
return false; // Agar x = 1 bo'lsa, son tub emas
}
if (x.equals(n.subtract(BigInteger.ONE))) {
return true; // Agar x = n-1 bo'lsa, sinov muvaffaqiyatli tugadi
}
}
return false; // Agar yuqoridagi holatlarda bo'lmagan bo'lsa, son tub emas
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// Tekshirilayotgan son
BigInteger number; // Masalan: 104729 soni tub
System.out.print("Sonni kiriting: ");
number = input.nextBigInteger();
int k = 100; // Rabin-Miller sinovlarini qancha marta bajarishni tanlash
if (isPrime(number, k)) {
System.out.println(number + " tub son");
} else {
System.out.println(number + " tub emas");
}
}
}
|
| |
