Frobenius Kvadratik testi ( QFT ) bir sonning mumkin bo'lgan tub yoki yo'qligini
tekshirish uchun ehtimollik birlamchi testidir . U Ferdinand Georg Frobenius sharafiga
nomlangan . Sinovda kvadratik polinomlar va Frobenius avtomorfizmi tushunchalari
qo'llaniladi . Buni kvadratik polinom yordamida umumiy Frobenius testi bilan
aralashtirib yubormaslik kerak - QFT kirish asosida ruxsat etilgan ko'phadlarni cheklaydi
va bajarilishi kerak bo'lgan boshqa shartlarga ham ega. Ushbu testdan o'tgan kompozitsion
Frobenius psevdo-tub hisoblanadi , ammo buning aksi to'g'ri bo'lishi shart
emas.
Algoritmni ishlab chiqishda Granthamning ko'zlagan maqsadi tub sonlar har doim
o'tishi va kompozitlar 1/7710 dan kam ehtimollik bilan o'tishini ta'minlash edi.
Test keyinchalik Damgård va Frandsen tomonidan kengaytirilgan kvadratik
Frobenius testi (EQFT) deb nomlangan testga kengaytirildi.
n musbat butun son bo'lsin , n toq bo'lsin va
bu erda (X/n)Yakobi belgisini bildiradi . B=5000 deb olsak . Keyin ( b , c )
parametrli n ustidagi QFT quyidagicha ishlaydi:
(1) tub sonlardan biri ikkita n ga bo’linadigan B va
qiymatning eng kichikidan
kichik yoki teng ekanligini tekshiring. Ha bo'lsa, n murakkab.
(2)
(3) ni hisoblang. Agar bo’lsa u holda n murakkab son.
(4) ni hisoblang. Agar bo’lsa u holda n murakkab son.
(5) s – toq son. Agar bo’lsa, n murakkab son boladi.
Agar QFT shu besh qadamda to’xtamasa, u holda n soni ehtimoliy tub deyiladi.
bu tenglik quyidagicha ifodalanadi:
Bu yerda H va K polinomlardir. n ni tekshiring . Ha bo'lsa, n murakkab
Solаvey-Shtrаssen testi:
import random
def power(a, n, p):
res = 1
a = a % p
while n > 0:
if n & 1:
res = (res * a) % p
n = n >> 1
a = (a * a) % p
return res
def jacobi(a, n):
if n <= 0 or n % 2 == 0:
raise ValueError("n must be a positive odd integer.")
if a == 0:
return 0
if a == 1:
return 1
result = 1
while a != 0:
while a % 2 == 0:
a //= 2
if n % 8 == 3 or n % 8 == 5:
result = -result
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
result = -result
a %= n
if n == 1:
return result
return 0
def solovay_strassen_test(n, k):
if n <= 1:
return False
if n == 2 or n == 3:
return True
for _ in range(k):
a = random.randint(2, n - 2)
x = power(a, (n - 1) // 2, n)
if x != 1 and x != n - 1:
return False
jacobi_val = jacobi(a, n)
if x % n != jacobi_val % n:
return False
return True
number_str = "151617181920212223242526272829303132333435363738394041424
3444546474849505152535455565758596061 "
number = int(number_str)
iterations = 5
if solovay_strassen_test(number, iterations):
print("Berilgan son tub son hisoblanadi.")
else:
print("Berilgan son tub son emas.")
|
