Ask Your Question

Pollard method for discrete logarithms (sage code)

asked 2023-10-02 18:44:47 +0100

ron_talbot gravatar image

updated 2023-10-02 19:37:33 +0100

tmonteil gravatar image

I'm trying to run the following Sage code from Introduction to Cryptography with Open-Source Software:

sage: a,y,n = 7,12,71
sage: R.<X> = Zmod(n)[]; R.<Y> = Zmod(n)[]
sage: def psi(X):
....: x,r,s=X[0],X[1],X[2]
....: if x%3==0:
....:      return [(x^2)%n,(2*r)%(n-1),(2*s)%(n-1)]
....: if x%3==1:
....:      return [(a*x)%n,(r+1)%(n-1),s]
....: if x%3==2:
....:      return [(y*x)%n,r,(s+1)%(n-1)]

sage: for i in range(1,11):
....:         X = psi(X); Y = psi(psi(Y))
....:         print(i,X,Y,X[0]==Y[0])

And I get the following error:

ArithmeticError: reduction modulo 3 not defined.

Any idea? Thank you.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2023-10-03 13:10:12 +0100

Max Alekseyev gravatar image

Short answer: reduction modulo 3 not defined because you apply it to elements of Zmod(71), where it is indeed not defined.

Overall, the code does not quite make sense. For example, you define X via R.<X> = Zmod(n)[] as a variable in the polynomial ring over $\mathbb{Z}/71\mathbb{Z}$ and then you extract the coefficients of polynomial X via X[0] etc. and redefine X as a list of integers via X = psi(X). If you plan to work with lists integers, why do you even define polynomial rings?

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2023-10-02 18:44:47 +0100

Seen: 59 times

Last updated: Oct 03 '23