Katta son faktorlashtirish - O'zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi...

|
O'zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti loyiha ishi Guruh: 13-21 Bajardi: Rahmonaliyev Toirjon Mahmudov Mohirjon Numonov Muxiddin Rustamov Farrux
|
bet | 8/10 | Sana | 16.12.2023 | Hajmi | 363,4 Kb. | | #120246 |
Katta son faktorlashtirish: Algoritm katta sonning faktorlarini aniqlashda foydalaniladi. Bu, kriptografiyada va son teoriyasida muhim bir muammo hisoblanadi.
Tezlik: Pollard algoritmi katta son faktorlarini samarali va tezlikdagi usul bilan topishga yordam beradi. U kriptografiyada katta sonlar bilan ishlashda va RSA kriptosistemalarining xavfsizligini buzishda keng qo'llaniladi.
Optimal variantlar: Pollard algoritmi uchun bir nechta variantlar va optimallashtirishlar mavjud. Ular algoritmda yaxshi samarali natijalarni olish uchun qo'llaniladi.
Qo'shimcha vositalar: Pollard algoritmi uchun qo'shimcha vositalar, masalan, Floyd tortish algoritmi (Floyd's cycle-finding algorithm), kanguru algoritmi (kangaroo algorithm), Brent algoritmi (Brent's cycle detection algorithm) kabi, muammolarni hal qilishda yordam beradi.
Shuningdek, Pollard algoritmi son faktorlashtirishda bo'laklarga, sertifikat orqali faktorlashtirishga, multi-prim faktorlashtirishga va boshqa xususiyatlarga asoslangan turli variantlarga ega bo'lishi mumkin.
Xulosa qilish uchun aytib o'tish kerakki, Pollard algoritmi katta son faktorlashtirish uchun yuqori darajada o'tkazmalarga asoslangan, samarali va keng qo'llaniladigan bir usul hisoblanadi. Uning o'zining qoidalari, boshlang'ich ma'lumotlari va variantlari mavjud bo'lib, xususiyatlari bo'yicha optimallashtirishlar bor. U shu sabablarga ko'ra kriptografiya va son faktorlashtirish sohalarida keng qo'llaniladi.
Dastur kodi:
package pollard;
import java.math.BigDecimal;
import java.util.*;
public class GFG {
static BigDecimal gcd(BigDecimal a, BigDecimal b) {
int son = a.compareTo(BigDecimal.ZERO);
if (son == 0) {
return b;
}
return gcd(b.remainder(a), a);
}
static boolean isPrime(long n) {
if (n <= 1)
return false;
if (n == 2 || n == 3)
return true;
if (n % 2 == 0)
return false;
for (long i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
static BigDecimal pollard(BigDecimal n) {
BigDecimal a = BigDecimal.valueOf(2);
BigDecimal i = BigDecimal.valueOf(2);
while (true) {
a = i.pow(a.intValue()).remainder(n);
a = a.add(n);
a = a.remainder(n);
BigDecimal d = gcd(a.subtract(BigDecimal.ONE), n);
int result = d.compareTo(BigDecimal.ONE);
if (result > 0) {
return d;
}
i = i.add(BigDecimal.ONE);
}
}
public static void main(String[] args) {
BigDecimal n = new BigDecimal("252245074561591631565758777960284564736623697
36904878100933060887887244216" +
"1202602816953288617390562942706430977943173089767599583674375492448088637729066809395210704895826474" +
"9843824491519970546839581757560659781401956291370756230639716876456768678729393339341703162051124451" +
"1892437239390863502308155450078419924080263102978663897532365363981719762081750552627197211945486141" +
"4422745287463223545226519029089034069500600943437226689881293180307292131690597624433577309833774346" + "99924583492845212206319390320703622866477008711013644010886555820367734996512061432529391693421190426715896428082690439073605633199475981032823");
BigDecimal num = n;
ArrayList ans = new ArrayList();
while (true) {
BigDecimal d = pollard(num);
ans.add(d);
long r = Long.valueOf(String.valueOf(num.divide(d)));
if (isPrime(r)) {
ans.add(BigDecimal.valueOf(r));
break;
} else
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
O'zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti loyiha ishi Guruh: 13-21 Bajardi: Rahmonaliyev Toirjon Mahmudov Mohirjon Numonov Muxiddin Rustamov Farrux
|