Tt va kt ” fakulteti 4 – bosqich ax-11-17 guruh talabasining

^log2 ^f(x)

₀ 200

400

x

600

800

1000

5.1-расм. Факторлаш алгоритмлари мураккабликларини таққослаш
Бу усул барча ҳозиргача маълум бўлган бошқа криптотаҳлил усулларини сиқиб чиқарган. NFC усули асосида криптотаҳлил учун зарур амаллар бажариш вақти қуйидаги ифода бўйича аниқланади:

Т = e^c ,
бу ерда
C=((1.923+О(1)*(Ln(n))^1/3*(Ln(Ln(n)))^2/3 .

Ҳисоблашлар тезлиги 10⁶ бўлган компьютердан фойдаланиб амалга оширилганда C ифодасида О(1)=1 учун амаллар бажариш вақти 1 мс га тенг. NFC усулининг истиқболдаги тараққиёти 1.923 доимийсини камайиши йўналишида юз бериши башорат қилинган. Кўпгина махсус тузилмали сонлар, масалан, Ферма сонлари учун доимий 1.5 гача камайиши маълум. Ҳозирги кунда қўлланиладиган факторлаш қийин бўлган модуллар криптоалгоритм яратиш жараёнида аниқ белгилаб қўйилган талабларга жавоб бериши шарт. Бу талаблар жумласига махфий даража кўрсаткичи d нинг катта сон бўлиши, ошкора калит қисми е > 3 шартига жавоб бериши, махфий туб модуллар учун р-1 ва q-1 ларнинг факторлари катта туб сон бўлиши ва шунга ўхшаш. Агар бундай модуллар учун ҳам доимийни 1.5 га камайтириш йўли топилса, унда 1024 битли сонларни ҳам мавжуд ҳисоблаш техникаси даражасида факторлаш мумкин бўлар эди. Доимийни камайтириш усулларидан бири бўлиб кўпҳад кўринишидаги сонларни кичик коэффициентлар орқали ифодалаш усулини топиш ҳисобланади. Ҳозирча адабиётларда бундай усул мавжудлиги ҳақида ахборот берилмаган.

1. 
   Сонли майдон ғалвири усули билан факторланган сонларнинг рекорд қиймати қанча?
   
2. 
   Сонли майдон ғалвири усули билан криптотаҳлиллаш учун зарур амаллар бажариш вақти қандай ифода бўйича аниқланади?