8-amaliy mashg’ulot Mavzu: Faktorlash muammosini bartaraf etuvchi dasturiy vositani ishlab chiqish

Misol-1. n =728 soni tub ko‘paytuvchilari topilsin.
Yechish. Tasodifiy x₀ ZnZ –son sifatida
x₀ = 2 , f(x)=x² +1
deb olinsa, u holda
x_i f(x_i-1) (mod n); i=0,1,2.......
yani x₀ = 2, x₁=5, x₂ =26, x₃ = 677, ………
EKUB (x₁ - x₀ ; n) = EKUB (3; 728)=1
Bu esa 3) shart intervaliga tegishli emas. Shuning uchun boshqa i – qiymatlar uchun hisoblashlarni davom qildiramiz.
EKUB (x₂- x₁; n) = EKUB ( 21; 728) =7;
Yani 3) shart intervaliga tushdi. Demak, 729:7=104. U holda bitta tub ko‘paytuvchisi 7 ekan. Keyingi hisoblashlarni n = 104 uchun bajarish yetarli.
EKUB (x₁ - x₀ ; n) = EKUB (3; 104)=1 , bu hol bajarilmaydi;
EKUB (x₂- x₁ ; n) = EKUB ( 21; 104) =1; bu hol ham bajarmadi;
EKUB (x₃- x₂ ; n) = EKUB ( 651; 104) =1; bu ham bajarmadi;
EKUB (x₄- x₃ ; n) = EKUB ( 457653; 104) =1; bu ham bajarmadi;
Demak, boshqa j, k –nomerlar uchun tekshiramiz:
j = 2, k = 0 ;
U holda
EKUB (x₂ - x₀; n) = EKUB ( 24; 104) = 8
va 1< 8 < 104 shart bajarildi.
Natijada 104: 8 = 13 bo‘lib, bevosita tekshirish mumkinki 13 soni tub son, javob esa 728 = 7*8*13= 7*2³ *13.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Security.Cryptography;
using System.IO;
using System.Numerics;
namespace Pollard
{
class Program
{
static void Main(string[] args)
{
// Method Pollard p-1;
Console.Write("N=");
BigInteger n = BigInteger.Parse(Console.ReadLine());
int b = 8;
BigInteger a = 2;
BigInteger e = 2;
do
{
a=BigInteger.ModPow(a, e, n);
e = e + 1;
}
while (e<=b);
BigInteger p = BigInteger.GreatestCommonDivisor(a - 1, n);
if (p > 1 && p < n)
{
Console.Write("p=" + p);
}
// break;
Console.ReadKey();
} }}