Как рассчитать мультипликативный порядок в Python / Sage для большого числа гекса - PullRequest
Новая
       20

Как рассчитать мультипликативный порядок в Python / Sage для большого числа гекса

0 голосов
/ 11 марта 2019

Мне нужно решить DLP, и у меня есть очень большое шестнадцатеричное число, например: 

p = 0x1BF84D6B529FD7B745CB75A04E29BF0F6857494D28644B8F8E52A6A97F43E4AC61024D77479F4249E836E488E7330B4C103335C0A278B8CB0A8D0A2CD2BC20C588BD60115B011BE0C413DF832F792606770309D3

g = 0x3ED63A6B778CF122FA5598C50F0D4E5FB92F0A7D49D986542087117CA48833DDDAAE784F9755BD19F588BFF82DF492132E1E3B24F5B5562BD32BA60D24212BF433EAD43CCD655BC9FC9C54578DFBE11F2D7FC6

h = 0x19F1BC01C5130852C5C1BD8539A3BC9D2911364C4B7E353E24198B9359D8DB4E40635DCCD029678DFB05051CC4DFD4CDBC0A0B1E6692204C715A7FB0444858F7E39A8340684C12F0013DC5502CD2680CC76362A7

Мой код для поиска мультипликативного порядка (находится в Интернете):

def multiplicativeOrder (A, N): если (GCD (A, N)! = 1): вернуть -1 

# result store power of A that rised  
# to the power N-1 
result = 1

K = 1
while (K < N) : 

    # modular arithmetic 
    result = (result * A) % N  

    # return samllest + ve integer 
    if (result == 1) : 
        return K 

    # increment power 
    K = K + 1

return -1

Я не могу использовать функцию мудреца, это задача из исследований :( поэтому я должен использовать Python, иличто-то отличное от sage :thing.multiplicative_order () Моя программа должна вычислить его за 2 секунды. Пожалуйста, помогите

...