Ask Your Question

Revision history [back]

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,(2r)%(n-1),(2s)%(n-1)] ....: if x%3==1: ....: return [(ax)%n,(r+1)%(n-1),s] ....: if x%3==2: ....: return [(yx)%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.

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> R.<X> = Zmod(n)[]; R.<y> 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,(2r)%(n-1),(2s)%(n-1)]
[(x^2)%n,(2*r)%(n-1),(2*s)%(n-1)]
....: if x%3==1:
....:      return [(ax)%n,(r+1)%(n-1),s]
[(a*x)%n,(r+1)%(n-1),s]
....: if x%3==2:
....:      return [(yx)%n,r,(s+1)%(n-1)]

[(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: error:

ArithmeticError: reduction modulo 3 not defined.

defined.

Any idea? Thank you.