95 lines
9.2 KiB
Python
95 lines
9.2 KiB
Python
# Алгоритм Диксона
|
|
from random import randint
|
|
from math import sqrt, exp, log, gcd
|
|
import numpy as np
|
|
import utils
|
|
import time
|
|
import sys
|
|
|
|
sys.set_int_max_str_digits(1000000)
|
|
|
|
def iammain(): return __name__ == "__main__"
|
|
|
|
def dixon(n):
|
|
|
|
# Оптимальное число элементов в базе = корень из субэкспоненциальной сложности алгоритма Диксона
|
|
k = int(sqrt(exp(sqrt(log(n)*log(log(n))))))
|
|
if iammain(): print(f'Размер факторной базы = {k}')
|
|
pk = utils.first_primes(k)
|
|
|
|
while True:
|
|
# step1
|
|
# Оптимальный размер факторной базы =
|
|
# корень из субэкспоненциальной сложности алгоритма Диксона
|
|
xs = []
|
|
y_splits = []
|
|
while len(xs) < k + 1:
|
|
x = randint(1, n - 1)
|
|
if x in xs: continue # без повторений
|
|
y = pow(x, 2, n)
|
|
y_split = utils.is_smooth(y, pk)
|
|
if y_split:
|
|
if iammain(): print(f'Гладких чисел найдено {len(xs)}/{k}')
|
|
xs.append(x)
|
|
y_splits.append(y_split)
|
|
|
|
if iammain(): print('step1 done')
|
|
|
|
# step2
|
|
A = [[e & 1 for e in row] for row in y_splits]
|
|
pose = [set([i]) for i in range(k + 1)]
|
|
pivots = set()
|
|
for col in range(k):
|
|
pivot = None
|
|
for row in range(k + 1):
|
|
if A[row][col] == 1:
|
|
if row in pivots: continue
|
|
pivot = row
|
|
pivots.add(pivot)
|
|
for i in range(k + 1):
|
|
if i == pivot: continue
|
|
if A[i][col] == 1:
|
|
A[i] = [x ^ y for (x, y) in zip(A[i], A[pivot])]
|
|
pose[i] ^= pose[pivot]
|
|
break
|
|
|
|
if iammain(): print('step2 done')
|
|
|
|
# step3, find all zero rows and try to find a valid solution
|
|
zero_rows = [i for i in range(k + 1) if
|
|
all(A[i][j] == 0 for j in range(k))]
|
|
for all_zero in zero_rows:
|
|
a = 1
|
|
be = np.array([0 for _ in range(k)])
|
|
for idx in pose[all_zero]:
|
|
a *= xs[idx]
|
|
be += y_splits[idx]
|
|
be >>= 1
|
|
b = 1
|
|
for i in range(k):
|
|
b *= pow(pk[i], int(be[i]))
|
|
# check if a != +-b mod n
|
|
if a % n != b % n and a % n != -b % n:
|
|
if iammain(): print(f"{a}**2 = {b}**2 (mod {n})")
|
|
return gcd(a + b, n)
|
|
|
|
# Если решение не найдено, продолжаем цикл
|
|
if iammain(): print("No solution found, restarting...")
|
|
|
|
if iammain():
|
|
N_TEST = 100
|
|
N1 = 13611197472111783959 # считает 2-3 минуты
|
|
N2 = 1191515026104746183243378937330489098579 # не считает
|
|
N3 = 74048093444435937986114388960912781233885985702403356033834092312625704192350369 # не считает
|
|
|
|
number = N1
|
|
|
|
start_time = time.time()
|
|
print('d=', dixon(number))
|
|
elapsed_time = time.time() - start_time
|
|
print(f"Общее время работы программы: {elapsed_time} секунд.")
|
|
|
|
# ЧИСЛО 1
|
|
# 1912746014114775470266091159927744809226105122681382081685789864060301815507795749726730414597141734460053469326992250934288660206069760535307279962420602233217115940796321132168537100953148276695590258984672266482891195363180184578781742806963963036525776389142753967802133171144631744579903160649419832988077728727206290481863156248277088622163344209177624584519607744942552828335553136967815675940112543107804228110938412110712699150673411900715307990192229505803630500545349510599506326522316327556803750549050419014259875379048792694565760084763825898266910638312182122354373614145561470013653949106772943643425439135936815691306372331801533703290908605557369966466293985913360062251625392625050361235856660603786154090716338215785812730489570892561186848377217420831763574402279030927669631530098401118643461151096594709304364499916473961167215391003650634234439498406058691067517811031674789377473949035969866577086719860458408198488054079192444246916261687799101876798966634332708689363667236245917838682612448429124491649510154350133353954813190029612306893156423481947229482118393830672446224616761421517498186783398063372576777364413651299414409826031757609743027005880287602949584715352574705011749416855601040272676414766135944967516150029050969242021807985027376040641838212263560556469631341121583149428685360030476477686615250805651438263361639745680948392228031224266921568416052104042039051424277202956363881333480810984199892516538733503115128927391930506014711069380605674959746940875291850923192846545355397089624637050784421601071266537492286747509692231206016909286312660153011894976956921098700317859727981383953691078442520453774492828135731499572248792021816324780033084315751944593554231533607984550112779788437741298521199816248247283013534501043316729352671883385109865402039693090651690605457098252499655379548578305524107891023044613332853939353803643305960843970429523257071969815484360151534625543911799084829393671521721989913741981784876459980039720010276906780489098629007848452094366814007256214034826921527206809880361830928526327083203943624803470183777197421638526140399407261520468903416781278310832647971503330613424359819727080858723341005494152245995541630531320139148452268375668973318449391411407691129097092149809511734867745750422996332162517080255764457927794253973875154138821922338012703733565181129109059542891798263504892744311414244672617270351742532010113958996478251556231037827361774421516810326776173973985742738529891445287881006950546430194259076204764267433679568892018150172101303274256641335778038036741886130765295461763585028998035672650550006474652926957954083533035763211459610504454056061162375588932137997748843941306664320814820976544150268273155328517947493118998679995438514458527727859343213089195887599660091331949612804818042832449841085493385751670216387150020266049457694688688223551698544956047790135875825608579287562351335520946222845374783181121638351462412750954121236225995613910156181931682847933095848410340921624227023653032519442469368396566532703705834038531165075588667770050680378122286674614601994409887047404763251430206056176238073517476918963125880552081090644837690140491707847956247412169510922665563570946039621536090903570478389892788427027750128990630574994344507486163892356400307497300928927110382413050592000766939984342018636491846973598392676051678013235662987203663499685223554689415343083010771601874118151750336697804145374501211188592794021989213366868502727756081184974326652714388249417759296613194091985865500827811190400180487796038215157662799670068993446939644325812032486428289280557416394158625892340578938529430273746428225536565987883006001867784306023619013002699149884266022975525214282430943226215624312730024833241036103668845291076639585812030450690184921297101255732891079027549394971544062168351209931436061111776152724185097260159409813801818567358378086188829411159754133225865216000000000000000000000000000000000000000**2 = 9402924085306271044501912698065630095421488955995011470463686473106787200670572309008894183669135929725257775863685943543740738239500809656653485237764339310400777725731167789898284512314470605504049500665834000275861231647353411916425087592708707339400753756083509255292390390537455819241269037972210504528591377487025712458276233233730928510538259445666461609048368421616109046663562652074584850423591281813426368605773974122102881649615954660838414655106350780823267165434087324902279186172864608309280966825989678713604612713320454434808618647002811041985354864419440867818182007911597187445934752277055032083111824420749149999003627555368815442680193820302540597642797224843334263380473719320735978454918603522668266906780606445751652615049053160500540992591611952212687385616320735157086382899044162177520368708727061014646333518783022621334149291921495073433335807517157416151714417449642870456294302386699680652426270124797859776041206047898710559493641084258133049731311108151696323532618136885971692822856238208077026228232212635514455535002343280412736101985330645510217555071097232704965654644075406716976124962521916490228954538455952134816440109374733756197938943454357672564319127371134977671818701889565346509922260189027872635559299141013053385287431107920130247845043613299631955136484249926540043069628236154490663256777172116957312226105187946696290560373656378146860059516612640324888431685466052332538913207052633295920734189795869858792529350339412785603920707513937363558962472259059027165487803348614531124366452111013367220337606826745633139429162648401908636858672615065747988135704866337368688443086927474493065603586650959867063522816180253671289383113855629834102201401159341747898716871482296530881070169428663851263234461131112035575184743912948230073122870762504107287204838089143124216214286286536116747053203415851295812558775018836917003770408349227189779390880112705536000000000000000000000000000000000000000000000**2 (mod 13611197472111783959)
|
|
# d= 4569882137
|
|
# Общее время работы программы: 127.43578791618347 секунд. |