klx's profile - activity

I'm trying to implement point halving in Secp256K1 from the article;

https://arxiv.org/pdf/0706.4379.pdf

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
q =  115792089237316195423570985008687907852837564279074904382605163141518161494337

R = PolynomialRing(GF(p),'x')

# x-coordinate of Q where Q = [2]P
qx =  Integer(84538659774007663836420160802839342215744092791779235474817172502887599548487)

g = (2 *x + qx)*(4*(x^3+7)) - (3*x^2)^2


fr = g.roots()

print(fr)


#One of the roots
t = 82764486716702815285605477501188164702466527314352175978120539775788537185277


gg = ((2 *t + qx)*(4*(t^3+7)) - (3*t^2)^2 ) % p

print( "Test root =", gg)

print("\np = ", p)

All the roots contain sqrt(1/7). below one of them.

   (-sqrt(1/7)*sqrt(84538659774007663836420160802839342215744092791779235474817172502887599548487*49^(2/3) - 7*49^(1/3) - 1208359250574819481534600080392050605105087726810769820677796001845964969340249259244945328508262182991854365774319030049384798743132808313732414554357442504885087643109348338916273438084667558118997277395074665220381651943716674620*49^(2/3)/sqrt(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409) + 100054989949395901167935252620598405103008960654576195043943116336416882925815572660901111485235900084034002323555728459075582870473207040343912567695848366) - 1/7*sqrt(49^(2/3)*(49^(2/3) + 7146784996385421511995375187185600364500640046755442503138794024029777351843969475778650820373992863145285880253980604219684490748086217167422326263989169*49^(1/3) - 591770618418053646854941125619875395510208649542454648323720207520213196839409)) + 84538659774007663836420160802839342215744092791779235474817172502887599548487, 1)

Normally, I was expecting one root in mod p and an irreducible of degree 3. The expected root is t and it satisfies the equation.

Is this a simplification problem? Or something else?

Great, thanks.

Finding the roots of a quartic in GF(p)[x], roots are not correct I'm trying to implement point halving in Secp256K1 fro

Finding the roots of a quartic in GF(p)[x], roots are not correct I'm trying to implement point halving in Secp255K1 fro

https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_point.html

I want to implement Extended GCD with SageMath so that the internal can be printed. The below is a modification of this. This should be straightforward, however, I might miss something;

def extended_euclides(a,b):

    s = 0; old_s = 1
    t = 1; old_t = 0
    r = b; old_r = a

    while r != 0:
        quotient,rem = old_r.quo_rem(r)

        old_r, r = r, old_r - quotient*r
        old_s, s = s, old_s - quotient*s
        old_t, t = t, old_t - quotient*t
    return [old_r, old_s, old_t]

K.<a> =  GF(2^8, modulus=x^8+x^4+x^3+x+1)
print(K)
print("m = ", K.modulus())

g = a^7 + a^5 + a^4 + a
h = a^4 + a^2 + 1

r,s,t = extended_euclides(g,h)

print("The GCD of \n \t [ {} ] and  \n \t [ {} ]  is \n\t [ {} ]".format(g,h,r))
print("Its Bézout coefficients are {} and {}".format(s,t))
assert r == g.gcd(h), "The gcd should be {}!".format(g.gcd(h))
assert r == s*g + t*h, "The cofactors are wrong!"

In the end, I've got the assertion error AssertionError: The gcd should be 1!

Any idea to solve this?

I see. I rather consider calculating it over the finite field instead of polynomials. Since the polynomials are always l

ExtGCD in Finite Fields I want to implement Extended GCD with SageMath so that the internal can be printed. The below is

ExtGCD in Finite Fields I want to implement Extended GCD with SageMath so that the internal can be printed. The below is

This should be the code. You have forgotten the ** instead of ^ from sage.all import * F = GF(2) R = F['x']; (x,) = R.

This should be the code. You have forgotten the ** instead of ^ from sage.all import * F = GF(2) R = F['x']; (x,) = R.

Yes, I want to the reverse, use the SageMath in Python.

I've seen this on ask.sagemath and stackoverflow

I want to use this in Python

k = GF(2)
R.<x> = k[]
k.extension(x^1000 + x^5 + x^4 + x^3 + 1, 'a')

The python code

from sage.all import *

F = GF(2)
R.<x> = k[]
K = F.extension(x^4 + x + 1, 'a')

print(K)

the R.<x> = k[] fails...

Is there a way to do this in python?

My final aim is finding the multiplicative inverse of an element using python with the sagemath import.

This should be the code. You have forgotten the ** instead of ^ from sage.all import * F = GF(2) R = F['x']; (x,) = R.

Using SageMath Finite Field Extension on Python. Yes, I want to the reverse, use the SageMath in Python. I've seen this

Using SageMath Finite Field Extension on Python. Yes, I want to the reverse, use the SageMath in Python. I've seen this

Also, I've seen this answer of yours and the function is not working, at least for me. Something has changed with Python

Also, I've seen this answer of yours and the function is not working, at least for me.

Also, I've seen this answer of yours and the function is not working, at least for me.

I guess substitute_expression is for something else, however, I couldn't find it in the docs.

I need to change Y into 1/2 *( y - a1 * x - a3) so that I can change variables in Elliptic curves.

var("X,Y,Z,x,y,a1,a2,a3,a4,a5,a6")
F = Y^2  *Z + a1 * X*Y *Z + a3 *Y *Z^2 - X^3 - a2 *X^2 * Z + a4*X*Z^ 2 + a6*Z^3
print(F)
F.substitute_expression(Y == 1/2 *( y - a1 * x - a3))  
print(F)

This produces an error on the 4th line;

AttributeError: 'sage.symbolic.expression.Expression' object has no attribute 'substitute_expression'

What is the proper way to change the variables?

Change of variables in symbolic computation I need to change Y into 1/2 *( y - a1 * x - a3) so that I can change variabl

def probit(p):
    return (sqrt(2)*erfinv(2*p-1)).n()

print(probit(0.025)) #Wikipedia Verification
print(probit(0.975))

P1 = [] 
for n in xsrange(1,100):
    P1.append( ( n , probit(n/100.0)) )

G1 = point2d(P1,color='blue',pointsize=10)
G1.show()

https://doc.sagemath.org/html/en/refe...

I've used the erfinv

def probit(p):
    return e^(sqrt(2)*erfinv(2*p-1)).n()

print(probit(0.025))
print(probit(0.975))

and outputs

0.140863494093217
7.09907138423134

Wikipedia states that

$\operatorname{probit}(0.025) = -1.96 = -\operatorname{probit}(0.975)$

Interestingly

print(e^(sqrt(2)*erfinv(1/2)).n())

outputs

1.96303108415826

Am I missing a point here?

[k_1 + 11x2, k_2 + 11x2, k_3, k_4 + 1, x1 + 23*x2, 2]. I've got this as an experiment, what is the value of k_3 and the last 2?

No automatic way form basis to eq.sub?