O‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi tоshkеnt aхbоrоt tехnоlоgiyalari univеrsitеti

O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TОSHKЕNT AХBОRОT TЕХNОLОGIYALARI UNIVЕRSITЕTI


«Kiberxavfsizlik» fakulteti
“Kriptografiya 2” fanidan

LOYIHA ISHI

Bajaruvchilar: Qodirov Eldor, Razzoqov Xamidjon,Muxtarov Nizomiddin, Yo’ldashev Shermurod, Matazimov Islomjon.

Qabul qiluvchi: Mardiev U.

TOSHKENT 2023
Topshiriq.
Quyidagi qitmatni “kvadrat elak” usuli yordamida faktorlarga ajrating (to‘rt kishi uchun). 𝑁 = 2799783391122132787082946763872260162107044674070975356536 948079411322889349850197156207726828824297798741533122674663 24664879544163509079879.
"Kvadrat elak" usuli (Square root method) - bu sonni 2 ta tub ko'paytuvchiga ajratish usullaridan biridir.Albatta amaliyotda keng qo’llaniladigan usullardan biri hisoblanadi. Ushbu usul quyidagi algoritma asosida ishlaydi:

1. Berilgan sonning kvadrat ildizini hisoblanadi

2. Kvadrat ildizni yaxlitlash uchun sonni eng yaqin butun kvadrat ildizga yuqori yaxlitlantiramiz
3. Yaxlitlangan kvadrat ildizdan boshlab songa qaragan toq sonlarni tekshirib ko'ramiz
- Agar son toq son bo'lsa va berilgan sonni unga bo'lishi natija 1 ga teng bo'lsa, shu toq sonni birinchi tub ko'paytuvchi bo’ladi
- Agar son toq son bo'lsa va berilgan sonni unga bo'lishi natija 1 dan farqli bo'lsa, shu toq sonni ikkinchi tub ko'paytuvchi bo’ladi
- Agar son toq son bo'lmasa, keyingi toq songa o’tamiz.

Biz kichik sonlar bilan dasturimizni tekshirib ko’ramiz. Masalan, N=91 bo’lsa tub ko’paytuvchilari p=13 va q=7 bo’ladi.

1-rasm

Ikkinchi marta, N=1649 berib ko’ramiz.

2-rasm

Demak, dasturimiz to’g’ri natija bermoqda.

O’zimizni qiymatni berganimizda p va q larning natijasi quyidagicha bo’ldi. Albatta kompilyatsiyaga uzoq vaqt ketdi chunki N katta son bo’lgani uchun.



3-rasm

p= 2049071

q= 136636719329009721336300536383183411512194778710497359854146004672913866300867573508004736137929056523602234042777173814213797152057449
Ilovalar
Dastur kod:
import java.math.BigInteger;

public class MyCipher {

public static void main(String[] args) {

BigInteger N = new BigInteger("279978339112213278708294676387226016210704467407097535653694807941132288934985019715620772682882429779874153312267466324664879544163509079879");

BigInteger[] factors = factorize(N);

System.out.println("p= " + factors[0]);

System.out.println("q= " + factors[1]);
}

public static BigInteger[] factorize(BigInteger n) {

BigInteger[] factors = new BigInteger[2];
BigInteger two = new BigInteger("2");

while (n.mod(two).equals(BigInteger.ZERO)) {

factors[0] = two;
n = n.divide(two);
}

BigInteger i = new BigInteger("3");

BigInteger sqrtN = sqrt(n).add(BigInteger.ONE);

while (i.compareTo(sqrtN) <= 0) {

while (n.mod(i).equals(BigInteger.ZERO)) {
if (factors[0] == null) {
factors[0] = i;
n = n.divide(i);
} else {
factors[1] = n;
return factors;
}
}
i = i.add(two);
}

if (n.compareTo(BigInteger.ONE) > 0) {

if (factors[0] == null)
factors[0] = n;
else
factors[1] = n;
}

return factors;

}

public static BigInteger sqrt(BigInteger x) {

BigInteger div = BigInteger.ZERO.setBit(x.bitLength() / 2);
BigInteger div2 = div;
while (true) {
BigInteger y = div.add(x.divide(div)).shiftRight(1);
if (y.equals(div) || y.equals(div2)) {
return y;
}
div2 = div;
div = y;
}
}
}