}
public static
boolean isPrime(int n)
{ boolean r =
true;
for (int i = 2; i <= (int)
Math.sqrt(n); i++)
{ if (n % i == 0)
{ r =
false;
break;
} }
return r; }
public static
void generatePossiblePrimeWithLength(int length)
{ int primeNumber = 2, roundCount = 5;
boolean f =
false;
Random rnd = new Random();
while(!f)
{
primeNumber = 2 + rnd.nextInt((int)
Math.pow(2, length) - 2);
for(int i = 2; i < 7 && isPrime(i); i++)
{ if(primeNumber % i == 0)
{
f =
false;
break;
} else { f =
true;
}
}
if(!isPrimeAccordingToMillerRabin(primeNumber, roundCount))
{ f =
false;
};
}
System.out.println("Number: " + primeNumber);
}
2.4 Lucas tublikka tekshirish testi
Agar
p > 1 ning yagona bo'luvchilari 1 va
p bo'lsa, p son tub hisoblanadi. Birinchi
bir nechta tub sonlar 2, 3, 5, 7, 11, 13, ... Lukas
testi n natural soni uchun birlamchilik
testidir, u har qanday sonning tubligini tekshirishi mumkin.
Bu Fermaning kichik
teoremasidan kelib chiqadi: Agar
p tub va
a butun son bo'lsa,
a^p(mod p) = a ga mos
keladi.
Lukas testi : Agar a (1 < a < n) butun soni mavjud bo'lsa, musbat
n soni tub
hisoblanadi: Va (n-1) ning har bir tub ko’paytuvchisi q uchun,
Misollar :
Kirish: n = 7 Chiqish: 7 tub tushuntirish: a = 3 ni olaylik,
keyin 3^6 % 7 = 729 % 7 = 1 (1- shart bajarilgan). 6 ning tub ko’paytuvchilari 2 va 3,
3^(6/2) % 7 = 3^3 % 7 = 27 % 7 = 6
3^(6/3) % 7 = 3^2 % 7 = 9 % 7 = 2
Demak, 7 tub
kirish : n = 9
Chiqish : 9 murakkab Izoh : a = 2 ni olaylik, keyin 2^8 % 9 = 256 % 9 = 4 Demak,
9 murakkab.
