00Luca00's profile - activity

If someone is facing the same problem at a point; using

R.<x> = GF(734443)[]
f = x^5+x^4+x^3+x^2+x+1
print f.roots()

gave me the roots in the form I needed!

I am currently trying to implement the Pollard Rho Algorithm using the speed-up with automorphisms applied to the Bitcoin curve Secp256k1. Hence I have the elliptic curve $y^2= x^3+7$ over a finite field with order $p$ such that $p\equiv 1 (mod) 6$, and with prime cardinality $l$.

Then we have an automorphism $\phi: E \to E$ with $(x,y) \mapsto (\xi_6 x, -y)$. Then there exists an integer $s_\phi$ s.t $\forall P \in E( \mathbb{F_{p}} )$ we have $\phi (P) = s_\phi P$. To find this $s_{\phi}$ we calculate the roots of the characteristic polynomial of $\phi$ modulo $l$.

This is the step is where I am working on. I calculate with this example of an elliptic curve over $p = 733387$ with $l = 734443$:

E = EllipticCurve(GF(733387), [0,0,0,0,7])

$P$ and $Q$ are such that $Q = e * P$

P = E([117331 ,426853,1])         
Q = E([614057 , 176740 , 1])
card = 734443   #(=the order of P)
k = GF(733387)
k2 = GF(734443)
primroot = k.zeta(6)
print primroot

output 164753 which is of order 6 as wanted in $\mathbb{F_{p}}$

print k(primroot^5+primroot^4+primroot^3+primroot^2+primroot+1)

Here I am not sure, but I think from the cyclotomic theory the minimal polynomial is $x^5+x^4+x^3+x^2+x+1$ for the primitve $6^{th}$ root of unity in $\mathbb{F_{p}}$ ?

since $s_{\phi}$ should be found as a root of the polynomial modulo $l$ I created it in the polynomial ring modulo $l$

Pk = PolynomialRing(k2, 'x')    
print Pk
poly = (x^5+x^4+x^3+x^2+x+1)
print poly.roots()
print (poly.roots()[0][0]).parent()

here lies my problem. The root that sage outputs are:

[(-1/2*I*sqrt(3) + 1/2, 1), (1/2*I*sqrt(3) + 1/2, 1), (-1, 1), (-1/2*I*sqrt(3) - 1/2, 1), (1/2*I*sqrt(3) - 1/2, 1)]

I tried to check different questions in the forum and saw that the parent of my root is a Symbolic Ring, but I don't know what to do about it. And I can't continue calculating with my possible $s_{\phi}$. And I need my $s_{\phi}$ to continue the steps in the Pollard Rho algorithm.

My source for this is the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" section 15.2.1.

I would be happy for any advice of maybe different souces that treat this algorithm.

While your computations for y and z are correctly done (I think) in Z/(p-1), your computations with K need to be done in Z/(p) instead. So add another ring:

R = IntegerModRing(8885569518)
S = IntegerModRing(8885569519)
K = 263785120
a = 11
b = 17

Ka = S(K)^a
(etc.)

y = 1/R(a)
(etc.)

Can you tell us which error you got (I did not get one for a long time, then i stopped the loop) ?

Moreover, in the first pass through the loop (x = 1, p = 2), c get the value False, and it will never become True again, because it is not reset in the loop. So, your code will not print anything !

Also, instead of writing:

if c==True:

you can simply write:

if c:

because c is a boolean, which has value True or False.

Also, you can remove:

else:
    pass

I found my mistake. In the end there was no error, only, that the programm did not give any primitive root. That's because the

c=True

Must lie inside the first loop. Otherwise it was all the time False if it did not work out once. So the correct version is:

for x in range(1,p):
  c=True
  for pi in list:
    a = (p-1)/pi
    if a == int(a):
        k = R(x^a)
        if k==1:
            c=False
        else:
            print k
    else:
        pass
 if c==True:
    print 'Lösung:', x
    break
 else:
    print c, x

I am writing a program to find the primitive root. In the lecture we have given that

x is a primitive root in F_p, where p a prime number, if
x^((p-1)/pi) is not 1. (With pi the prime factors of p-1).

So here my programm:

p = 468889
R = IntegerModRing(p)
factor(p-1)
#gives: p-1 =  2^3 * 3 * 7 * 2791

list = [2,3,7,2791]
c=True

(I changed the for loop:)

for x in range(1,p):
  for pi in list:
    a = (p-1)/pi
    if a == int(a):
        k = R(x^a)
        if k==1:
            c=False
        else:
            print k
    else:
        pass
  if c==True:
    print x
  else:
    print c, x

But still there is no result. Can anyone help? I don't see the problem. Thanks a lot!

I found the problem. It was that if I calculated R(Ka^y) it simply should have been K, but it wasn't. So I tried

  'Kaby = R(K^(a*b*y))'

and this way it works and is the same as Kb. And also

   R(K^(a*y))=K.

So I didn't try your suggestion. But thanks a lot for the response!! :)

I am currently trying to make an example for the three pass protocol. Maybe someone can tell me my mistake, because it doesn't work out. There is no error, but the numbers don't fit.

#Prime p = 8885569519.
#Let a = 7 and b = 17.
#Alice knows K = 263785119.

#Over the Ring mod p-1
R = IntegerModRing(8885569518)
K = 263785120
a = 11
b = 17

#Alice calculates K^a:
Ka = R(K)^a

#Bob calculates (K^a)^b:
Kab = R(Ka)^b

#Alice recives Kab and calculates((K^a)^b)^a^(-1).
#first a^(-1)
y = 1/R(a)
#then y*a % p-1 = 1 (p-1 = 8885569518)
Kaby = R(Kab)^y

#Kaby should be the same as K^b:
Kb = R(K)^b
#but it isn't

#The inverse of b:
z = 1/R(b)
KK = R(Kaby)^z

K^a^b^a^(-1) should be the same as K^b, but it doesn't work out. Does someone see my mistake?

Thank you and best, Luca