# Pollard method for discrete logarithms (sage code)

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 close merge delete

Sort by ยป oldest newest most voted

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?

more