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


Download 21.92 Kb.
Sana17.06.2023
Hajmi21.92 Kb.
#1546391
Bog'liq
kripto loyiha


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;
}
}
}
Download 21.92 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling