I try to calculate by using discrete_log() but not work for large number

asked 2023-04-19 19:04:14 +0100

nym
1

updated 2023-04-26 06:03:20 +0100

Max Alekseyev

6488 ●9 ●47 ●153

.

t = discrete_log(4606815884838096377785347111721334332459567989754605435844553924611757427069, Mod(97016818800896472150918065086250305521582061568558917554562390770912719895221401642022327235442504255165455324230541561317542276008106728590510249294231213455088465804512445976666355341857163701366354017006156391714683091049337810349792952918394597561886848000536740995848307859909170152759863496892968987231467561357586221114673227133800245184712226234621456455055786160754075383416875161259574092211341255393749410533119623826022492550461865106935976459567575039483207880962220201808514572855267625449697560220455487500630057056345784705084220984258795128046351522036351167622945734117491830725821551997905856388097998709013799516296255410153025209661687012871382956250022352094543531376473023885009728693916552500738520889410618602032797484750688036815302369359485137135837765742210512442884404829684504513832855643449269497374643683169162268135642045354863586480102333829311525506559975842373513467258443822413596446917980763567520633434489460617319283227852373961939739720136100557229670703791162232608762953316138358641479844379559693650788986725716764183578522801765063225561679015968963874983645936232418844248759448460194794538908830428864623572575789445910870181422652249016571805995234565152065996757057264254174752086868, 617287018455808291809828381396728963438857532378086039582820659484693730680947319796389162560181325828755367322358924996072362055728046389598377834786382499819306983727314365829500259441483724649894796950127083467301377449510548513672290843754754474460477662564925191307272949211058626328330247905804435852861329727486878773160349827133784125602394857849063882526701153670843055473328830310659567683441082359295315475586695277481351571095664526128816504457558257099130271728396770126116948315823045789371730353271064228914634692223191287980316988286311277750868008798756519257847111393116479360711451979857453986868779040788147597049302241908696918207549776441493966195761452548133627398129120915303060891043270738763497525203978356873746577724506651876903792787903505978860347514314292847949386040101538796396558125948956283327893607513279162068698706742054767580230117259873012637253491799995851913560728342384154299618295839126759347347445931235544984475302728937968731291599076267890615751236298580678807361199230603797947385207709017115833960761739849998574057771149558246830629882968096301142307316762881619766992186858655805011590896707769035113658409993817187963475011969965698065891474311987832706316925420095004577127665239))
t

edit retag flag offensive close merge delete

add a comment

0

answered 2023-04-26 22:23:06 +0100

Sylvain
68 ●2 ●7

The current record for prime number modulus discrete logarithm is about 795 bits using about 3100 core-years. You are trying to solve a discrete logarithm with a number which is 4096 bit long. Even though this is not a prime number its seems to have large prime numbers in its factors thus it won't finish on your machine. For smaller examples of the discret_log usage see previous questions.

edit flag offensive delete link

add a comment

0

answered 2023-04-26 15:18:30 +0100

Max Alekseyev

6488 ●9 ●47 ●153

updated 2023-04-26 18:36:24 +0100

No surprise here since it's a hard computational problem. I suggest to start with factoring the modulus (which can also be computationally hard), which will allow to split computing the original discrete logarithm into those modulo smaller prime powers (factors of the modulus), which is typically simpler.

edit flag offensive delete link

add a comment

I try to calculate by using discrete_log() but not work for large number

2 Answers

Your Answer

Question Tools

Stats

I try to calculate by using discrete_log() but not work for large number edit

2 Answers

Your Answer

Question Tools

Stats

I try to calculate by using discrete_log() but not work for large number