Решение и уравнение по модулю линейного сравнения:
Я могу решить набор уравнений линейного сравнения для степеней 2 намного быстрее, чем прямой алгоритм
Например, с помощью этого кода:
pow(N, 2**N.bit_length()-1, 2**N.bit_length()) - 1
is equivelant to fastlinearcongruencep2(2**N.bit_length(),1,N)[1]
but over 1000x times faster.
Для числа:
sinn=7930219578312874863327254771745497557798348052171421743127507434849393873099528630142162935868998694651313363537371082037339970538772287845061290706309622633503662855419870315548725838781239572591860347535037944021724653332770260753031401698536033511386033743333721347025536277195136437888722209232513120119011361526341874882606890260829526406523297858904355145745624491564187323071981372423509699814241318039467269215956487004198813468071443926518618603292988059573430034473399719966977480164285558112103686176288866128560549811849344518152166267878710879385245007756898232401021489157979673924328710124412192108961077387428711827496108045726178714887507437676510899831644802858402098060477777122007199214756625076019248375770227440076741723994405061045556327214513839768334464480942413511936558295875060071694874346640529437013933806572880427172194005852899377419349643097522563604884985649793543314893506541764521936635055582817064531192570988063383279184315660600440101553790697677027809911922243203705790075478367343493922469001832592147186929743546319243169434103109211940891783920317573137010224227507724337539905061747627087116855128986014373699568724179668262180551701950344531923468615810870199457454890370639785561930945943213626248243040429269755184835134953797136171852311984619466439759788234642556686364639020784711863281507221121143083538153812424750026057715106052632313808507003800376755186230822199618623776469448026677786150333455300640436688706605087827514269402259992833914103226768594343089361592391324348716414692795539921431463438483283344317986117125871989506974006212086744990293480431044032427081842855450016941699145732725314209066687961870048160191906003103637005418039654945991073642237464865888744641315431028685784416845674782275045847287953564771273640323227604812032931404121366086710737198604155159893328888254036699761212024006763925192896870841477517259935430715115157680465097113951374308212510777650390715845586594701208810029012084166971228455240861276533865730693069151306792566308468228749935282847418913140621237416463852674382538532067691403013625830240206572106609202477935586096973085252687638417964530819972923074536353901108972268990684837154237339198427413607453076758984223269386906134376927603144675040347181934690331390734031386348082084920190995484783499144140511978423016936369216737620138647544104318705588944588173162529648277831034012604311882508306931656651704668016773523474313369433693053968093878474332725160439550023079408193461072769636828661550031081503335216800878674640612479519302596209737480405421445443712277729782445701165161011062671559638059381277444405767543458930461509543241158148502018877475647709492194173715654498581462986694191043904696947883981511298784518064222680152347856684944923208618332334859065149247655067862918240017967151492798292844777165791767420823218809408423673068712321404711690246764314527549975422150684982090026111597731642214650660874174618026520875579559736117376962534744210348452270163717842610342986532346251843942392633399065739439809648579075072995610013961805576798560097776031398580251297607088926775072893626917772189399651488579730135290102385490681238714748785640341765604930451864480326089503741528657844344257572349890432052284999892781562825297787841234404832347230681816281527508194771459192340461696596734568773433884888262185884257911840984959849116846272526690425831207494097842329882772279928215963564559675091818357043200418755600893922983890776111382008890011591916669097927055639450634161938483063513347217085532646079998211909121833238322353313553015880885563821853935727037167632982204140991883804347599621838069046483772672100381554635175608526715427463533643931770495963684670388724075436619878569929090416533484960606929113584300698111221983898671574997828641875604310845556300480490676573625669455095767813084270114449811585073920982201739521155741301709400128044045730414530207306596811516603221548866308048537190882127053738037115927196040621105466370040068830908923486010314910741532423854279818680402528254381571561272214866022437503306057019579181684852390257137
Время решения с помощью pow составляет 6,6 секунды, но мгновенно с помощью fastlinearcongruencep2 (). Мой вопрос: знает ли кто-нибудь, как изменить код для решения проблем, не являющихся степенями двойки, с быстрым переходом к последнему ответу, как это происходит для степеней двойки. Я создал этот код и решение, поэтому я думаю, что есть другое решение для них. Вместо того, чтобы искать себя, я подумал, что спрошу у других stackoverflowers, есть ли у них идеи, как решить проблему смещения, чтобы перейти к последнему ответу Pow для не степеней двойки.
Вот код, который решает:
pow(N, 2**N.bit_length()-1, 2**N.bit_length()) - 1
which takes 5 seconds with another way:
fastlinearcongruencep2(2**N.bit_length(),1,N)[1]
in way less than a second
Вот код:
def fastlinearcongruencep2(powx, divmodx, N, withstats=False):
x, y, z = egcditerp2(powx, N, withstats)
if withstats == True:
print(f"powx = {powx}, divmodx = {divmodx}, N = {N}")
if withstats == True:
print(f"x = {x}, y = {y}, z = {z}")
if x > 1:
powx//=x
divmodx//=x
N//=x
if withstats == True:
print(f"powx = {powx}, divmodx = {divmodx}, N = {N}")
x, y, z = egcditerp2(powx, N)
if withstats == True:
print(f"x = {x}, y = {y}, z = {z}")
answer = (y*divmodx)%N
if withstats == True:
print(f"answer = {answer}")
return answer, (z|1)-1
def egcditerp2(a, b, withstats=False):
s = 0
r = b
old_s = 1
old_r = a
quotient = 0
if withstats == True:
print(f"quotient = {quotient}, old_r = {old_r}, r = {r}, old_s = {old_s}, s = {s}")
while r!= 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
if withstats == True:
print(f"quotient = {quotient}, old_r = {old_r}, r = {r}, old_s = {old_s}, s = {s}")
if b != 0:
bezout_t = quotient = (old_r - old_s * a) // b
if withstats == True:
print(f"bezout_t = {bezout_t}")
else:
bezout_t = 0
if withstats == True:
print("Bézout coefficients:", (old_s, bezout_t))
print("greatest common divisor:", old_r)
return old_r, old_s, bezout_t
Вот пример выполнения:
# From above copy sinn:
N=sinn
import time
start = time.time()
a = pow(N, 2**N.bit_length()-1, 2**N.bit_length()) - 1
end = time.time()
print(end-start)
print(f"Operation took {(end-start)/60} minutes")
6.658302068710327
Operation took 0.11097170114517212 minutes
import time
start = time.time()
b = fastlinearcongruencep2(2**N.bit_length(),1,N)[1]
end = time.time()
print(end-start)
print(f"Operation took {(end-start)/60} minutes")
0.027124881744384766
Operation took 0.0004520813624064128 minutes
In [8897]: a == b
Out[8897]: True
Итак, пока я ищу ответ, мой вопрос: знает ли кто-нибудь любых модификаций, которые я могу сделать, чтобы пропустить путь к последнему ответу для чисел, отличных от степени двойки. пример числа, для которого я нашел способ получить последние x и n. Это не работает для всех чисел, но подходит для некоторых, поэтому я думаю, что здесь задействована конструкция мета-уровня, которая может достичь того, что я ищу, способ быстро вычислить последний X и N любого числа , как я делаю для степеней двойки с любым простым числом.
Вот мощное число 1013 с использованием ответа (92), полученного мной из быстрой линейной конгруэнции, которая намного быстрее, чем pow
N=1013
Running fast linear congruence as a I do for the powers of 2 I get the first x of a pow for 1013
fastlinearcongruencep2(2**N.bit_length(),1,N)[1]
92
In [24285]: rpowx2(1013, withlc=0, withx=True, withstats=True, k=False, yoffset=0, offset=0)
253 1 92 1013 92 1009 256 253
126 92 360 1013 92 121 360 253
63 92 949 1013 92 459 949 360
31 190 44 1013 92 990 223 949
15 256 923 1013 190 529 92 44
7 259 1009 1013 256 253 360 923
3 990 16 1013 259 190 949 1009
1 645 256 1013 990 645 44 16
0 1 44 1013 645 (990, False, 1) 121 16
Out[24285]: (1, 44, True, 92)
I took the inverse of 92, and received 586:
In [8970]: fastlinearcongruencex2(92,223,1013)
Out[8970]: 586
Using fastlinear congruence i received (223) as a bezout coefficient using 586,92,1013 as the variables:
In [8984]: fastlinearcongruencep2(586,92,1013,withstats=True)
quotient = 0, old_r = 586, r = 1013, old_s = 1, s = 0
quotient = 0, old_r = 1013, r = 586, old_s = 0, s = 1
quotient = 1, old_r = 586, r = 427, old_s = 1, s = -1
quotient = 1, old_r = 427, r = 159, old_s = -1, s = 2
quotient = 2, old_r = 159, r = 109, old_s = 2, s = -5
quotient = 1, old_r = 109, r = 50, old_s = -5, s = 7
quotient = 2, old_r = 50, r = 9, old_s = 7, s = -19
quotient = 5, old_r = 9, r = 5, old_s = -19, s = 102
quotient = 1, old_r = 5, r = 4, old_s = 102, s = -121
quotient = 1, old_r = 4, r = 1, old_s = -121, s = 223
quotient = 4, old_r = 1, r = 0, old_s = 223, s = -1013
bezout_t = -129
Bézout coefficients: (223, -129)
greatest common divisor: 1
powx = 586, divmodx = 92, N = 1013
x = 1, y = 223, z = -129
answer = 256
Out[8984]: (256, -130)
Confirming the bezout coeffecient here:
In [8972]: fastlinearcongruencex2(223,1,1013)
Out[8972]: 586
I then use the the first number from rpow2x, whixh is 253 (Also the same number
as (1013>>ltrailing(1013-1) which the miller rabin test uses. The answer i received is
645:
In [8478]: fastlinearcongruencep2(253,92,1013)
Out[8478]: (645, 0)
I then perfomed two operations from top two numbers, 92 and received 360 ( the second x, and the
number 1002). So from the top two to lines of the pow, i was able to receive numbers that a fast
linear congruence, gives me the last x and the previous last x as shown here:
In [8477]: (92*92)%1013
Out[8477]: 360
In [8472]: fastlinearcongruencep2(92,1,1013)
Out[8472]: (1002, 0)
In [8479]: fastlinearcongruencep2(360,1002,1013)
Out[8479]: (695, -44)
In [8481]: fastlinearcongruencep2(360,645,1013)
Out[8481]: (44, -44)
In [8492]: fastlinearcongruencep2(695,645,1013)
Out[8492]: (256, 212)
Taking these answers i was able to retrieve the last n with the answer i received from above.
In [8504]: (645*256)%1013
Out[8504]: 1
Не все числа следуют этому прекрасному пути, но 1009 и еще два, и поэтому я думаю, что существует концепция мета-уровня более высокого уровня, которая может позволить нам получить последние N и X оператора pow только из первые несколько шагов. Я уже доказал выше в этом посте, что он работает каждый раз для степеней двойки, так почему бы не не использовать степени двойки, как я продемонстрировал здесь. Я надеюсь, что это заинтересует математиков, и мы сможем найти решение поиска последних X и N оператора pow с формулой мета-уровня и линейной конгруэнтностью. Пожалуйста, не стесняйтесь общаться со мной в чате или пишите мне по электронной почте из моего профиля, если вы хотите обсудить это дальше и исследовать дальше. Итак, я показал, что все степени двойки имеют ярлык к последним X, N, и с правильной формулой так же и не степени двойки, но не все степени двойки следуют одному и тому же шаблону, поэтому я ищу мета формула уровня для достижения того же результата. Обнаружение этого ускорит все операции pow в 100 раз.