santoshi's profile - activity

what is the sage command to check A and B belongs to the field F.

timeit() or start time to end time

.

p=(2^3) 
F1.<x>=GF(2)[] 
F.<a>=GF(2^3,'a',modulus=x^3+x+1);F.modulus();
for i,x in enumerate(F):  print("{} {}".format(i, x))

A=a^2+a;A 
B=a+1

E = EllipticCurve(F, (1,A,0,0,B));E

p=(2^3) F1.<x>=GF(2)[] F.=GF(2^3,'a',modulus=x^3+x+1);F.modulus(); for i,x in enumerate(F): print("{} {}".format(i, x))

`p=(2^131) p1=GF(p) F1.<x>=GF(2)[] F.=GF(2^3,'a',modulus=x^3+x+1);F.modulus();F for i,x in enumerate(F): print("{} {}".format(i, x))

p=(3^151) F1.<x>=GF(3)[] F.<a>=GF(3^151,'a',modulus=x^151+2*x^2+1); A=1 B1=(0x1fc4865afe00a9216b0b5fd32c6300c4bed0707ae4072a03e55299f157b);B1 B=F(B1.digits(3));B D=F(B).field_element();D

how to check the element B is Field element, the command which i have written gave me attribute error.

How to generate elliptic curve from the following code as B is in hexadecimal form. The elliptic curve generated from the following code is ... which is not showing B in irreducible polynomial form.

Elliptic Curve defined by $y^2 = x^3 + x^2 + 1$ over Finite Field in $a$ of size $3^{151}$

F1.<x> = GF(3)[]
F.<a> = GF(3^151, 'a', modulus=x^151 + 2*x^2 + 1)
F.modulus()
F
A = 1
A
B = (0x1fc4865afe00a9216b0b5fd32c6300c4bed0707ae4072a03e55299f157b)
B
E = EllipticCurve(F, (0, A, 0, 0, B))
E

Paper: Efficient Arithmetic on Elliptic Curves over Fields of Characteristics three

import time p=(3^151)

F1.<x>=GF(3)[]
F.<a>=GF(3^151,'a',modulus=x^151+2*x^2+1);F.modulus();F

A=1;A
B=(0x1fc4865afe00a9216b0b5fd32c6300c4bed0707ae4072a03e55299f157b);B
E = EllipticCurve(F, (0,A,0,0,B));E
P = E.random_point();#P
Q = E.random_point();#Q
print "\n point1 =",P# P.xy()
print "\n point2 =",Q #Q.xy()
x1 = P[0]
y1 = P[1]
x2 = Q[0]
y2 = Q[1]

#x31=((y1^6)*(A^2*(x1^3+B)^2)^(-1))
#x32=((A*x1^3)*((x1+B)^(-1)))
#X3=(x31-x32);X3
#y31=((y1^9)*((A^3*(x1^3+B)^3))^(-1));y31 
#y32=((y1^3)*((x1^3+B)^(-1)));y32
#Y3=(y31-y32)

X3=F(((x1^3+B)^3-(B*x1^3))*((x1+B)^2)^(-1));X3

Y3=F(((y1^9)-((y1^3)*(x1^3+B)^2)*((x1+B)^3)^(-1)));Y3

R=E(X3,Y3);R
#print "\n H = P + Q has the components:\n

after executing the code the error is point are not on the curve. I have written the equation for x3 and y3 by different ways.

I using timtit command to compute time the result is 625 loops, best of 3: 38.1 ns per loop what is the meaning of 625 loops, best of 3.

roots of polynomial x^3+7x+25 over field F(37)

f= z^3 + (3a + 4)z^2 + 3z + 3a + 2 # z is variable f1=f.roots() [(3a + 1, 1), (2a, 2)]# what is 1 and 2 represent in the bracket

I want to perform scalar multiplication but when i will take some random point and order of that point as scalar it gives me error.

import time
import sys
from sage.all import *
p = (2^113); p

F1.<x, y> = GF(2)[]

F.<a> = GF(2^113, 'a', modulus=x^113+x^9+1); F.modulus(); F
A = F.fetch_int(0x003088250CA6E7C7FE649CE85820F7); A
B = F.fetch_int(0x00E8BEE4D3E2260744188BE0E9C723); B

E = EllipticCurve(F, (1, A, 0, 0, B)); E
G = E.random_point()
n = E.order()
K = randint(1, n - 1)
R = K*G

p=2^224-2^96+1 A=-3#(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFE) B=(0xB4050A850C04B3ABF541325650440B7D7BFD8BA270B39432355FFB4)

F=GF(p) E = EllipticCurve( F, [A,B] );E G=E(0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21,0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34);G

the above domain parameter (p,A,B,G) taken from SEC2(standard for efficient cryptography) Recommended Elliptic curve. But when i run the code the error is the point G coordinate do not define point on elliptic curve.

the below code is performed mod arithmetic of two polynomial fE and fL over prime field P= 5 and the extension is 5^2. the mod of two polynomial is always third degree polynomial. My fE polynomial is always 3p degree and fL polynomial is p degree. my question is whatever p(large p = 112 bit ,128 bit 160 bit) I will take my mod is always third degree. is it because of any polynomial property.

p=5 A=4 B=4 print"\n p=",p print"\n A=",A print"\n B=",B

F = GF(p) E = EllipticCurve( F, [A,B] );E

S. = PolynomialRing( F ) K. = GF( p**2);#K.modulus#, modulus=W^2+W+1 ) print "\n Modulus of K is =", K.modulus()

the below code is performed mod arithmetic of two polynomial fE and fL over prime field P= 5 and the extension is 5^2. the mod of two polynomial is always third degree polynomial. My fE polynomial is always 3p degree and fL polynomial is p degree. my question is whatever p(large p = 112 bit ,128 bit 160 bit) I will take my mod is always third degree. is it because of any polynomial property.

p=5
A=4
B=4
print"\n p=",p
print"\n A=",A
print"\n B=",B

F = GF(p)
E = EllipticCurve( F, [A,B] );E

S.<a> = PolynomialRing( F )
K.<a> = GF( p**2);#K.modulus#, modulus=W^2+W+1 )
print "\n Modulus of K is =", K.modulus()

R.<z> = PolynomialRing( K, sparse=True )

fE=z^15 + (4*a + 4)*z^11 + 2*z^10 + (a + 3)*z^7 + z^6 + (2*a + 2)*z^5 + z^3 + 2*z^2 + (3*a + 4)*z + 1
fL=(4*a*z^5 + (a + 4)*z + 3);fL
f1= (fE%fL).monic;f1
z^3 + (3*a + 4)*z^2 + 3*z + 3*a + 2

why the computation time required in the following way of execution is different.

1.to run the algorithm I am writing the code /algorithm directly on the sage terminal window and execute the code.

1. in this process I am creating a .sage file of code/algorithm and save the file in a document. then load/attach that file with the proper path on sage terminal. the execution/ computation time in both the cases is different why?

how to use NTL library for huge polynomial gcd’s over finite fields very quickly.

the following code for gcd computation for two polynomials . the code for 112-bit elliptic curve but as the polynomials are two large it is difficult to compute gcd. the codes are given below. what is the solution for large polynomials.

p=0xDB7C2ABF62E35E668076BEAD208B  #Secp112r1 Elliptic curve;
F = GF(p);
S.<a> = PolynomialRing( F );
K.<a>=GF(p^2);#K.modulus();
R.<z> = PolynomialRing( K, sparse=True );
print'hi'
fE=(1978526766708317676482043677132634*a + 989263383354158838241021838566317)*z^13355055675281144316253794820645281 + (2967790150062476514723065515698951*a + 1483895075031238257361532757849475)*z^8903370450187429544169196547096855 + 2967790150062476514723065515698951*z^8903370450187429544169196547096854 + (1483895075031238257361532757849476*a + 2967790150062476514723065515698951)*z^4451685225093714772084598273548429 + 2967790150062476514723065515698952*z^4451685225093714772084598273548428 + (a + 2)*z^4451685225093714772084598273548427 + (2473158458385397095602554596415793*a + 3462421841739555933843576434982110)*z^3 + 2967790150062476514723065515698951*z^2 + (4451685225093714772084598273548426*a + 1)*z + 2390566828285061569181602107159913


Phi10=z^2477187667914709744689409953417368724452959475301832810429239271791 + 4451685225093714772084598273548426

x10=gcd(fE,Phi10);print"\n gcd(fE,Phi10) x10=",x10

i am using two platforms to run the code. one is sagemath cloud and second is sagemath terminal. the computational time obtained in both the platform is different. the results obtained are better in sagemath terminal. i am writing paper so please suggest me which result i have to consider for my research paper.

the time required for above compution is 1.96ms and i want 0.19 ms.

.

p =37
print"\n p=",p
F=GF(p)
S.<a> = PolynomialRing( F )
K.<a> = GF( p**2);#K.modulus#, modulus=W^2+W+1 )
print "\n Modulus of K is =", K.modulus()                    
R.<z> = PolynomialRing( K, sparse=True )

fE=(4*a + 5)*z^111 + (5*a + 32)*z^75 + 14*z^74 + (32*a + 15)*z^39 + 9*z^38 + (15*a + 22)*z^37 + (33*a + 21)*z^3 + 14*z^2 + (22*a + 8)*z + 12
fL=(5*a + 8)*z^37 + (32*a + 28)*z + 20
F1=(fE % fL).monic()

the time required for the computation of F1 is very large so please suggest me any other alternative for above computation. The gcd function is also required large amount of time for computation . so please suggest me other altrnative or algorithm for computation of one variable polynomial.

enter code here

The following code i have written for scalar multiplication over elliptic curve for prime field 37 but it gives me error for some of the scalar. the method is LSB first.

import time
import sys
from sage.all import *

# elliptic curve domain parameters, prime192v1

# domain parameters

p = 37
A = 7
B = 25
G = 1
n = 21

print "\n p =", p
print "\n A =", A
print "\n B =", B
F = GF(p)

E = EllipticCurve(F, [A,B])
print "\n Elliptic curve equation:", E

def point_add(P, Q):

    x1 = P[0]
    y1 = P[1]
    x2 = Q[0]
    y2 = Q[1]

    # check P == O
    if P == [0, 0]:
        return Q

    # check Q == O
    if Q == [0, 0]:
        return P

    # check Q == -P
    if x1 == x2 and y1 + y2 == 0:
        return [0, 0]

    # check P == Q
    if P == Q:
        return point_double(P)
    slope = F((y2 - y1)/(x2 - x1))
    x3 = F(slope**2 - x1 - x2)
    y3 = F(slope * (x1 - x3) - y1)

    return[x3, y3]

def point_double(P):

    # if P == [0, 0]:
    #     return [0, 0]

    x1 = P[0]
    y1 = P[1]

    slope = F((3 * x1**2 + A)/(2 * y1))
    x3 = F(slope**2 - 2 * x1)
    y3 = F(slope * (x1 - x3) - y1)
    return [x3, y3]

def scalar_mult(K,P):
    print('hi')
    b_k = ZZ(K).bits(); print(b_k) # ; K.digits(2)
    l = len(b_k); l
    sum1 = 0*P; sum1
    print(b_k[0])
    if b_k[0] == 1:
        sum1 = P; sum1
    else:
        sum1 = 0
    Q = P; print(Q)
    for i in range(1, l):
        Q = point_double(Q); print(Q)
        if b_k[i] == 1: 
            print (b_k[i])
            # sum = point_add(sum, Q)
            sum1 = point_add(sum1, Q)
            print(sum1)
            # Q = point_double(Q)
    return sum1

P = E(20,32); P  #; P.random_point(); P
f1 = P.order(); f1
K = randint(1,f1); K
answer1 = K*P; answer1
start1 = time.time()
answer = scalar_mult(K,P); answer
end1   = time.time()
print "\n Time Required to compute scalar multiplication: %s" % (end1 - start1)
answer2 = E(answer); answer2

Require k=(km-1,km-2,…,k0)2, km=1 Compute Q=kP Q=0, R=P For i=0 to m-1 If ki=1 then Q=Q+R End if R=2R End for kindly provide me sagemath code for above algorithm for prime field 37 and elliptic curve y^2=x^3+7x+25

how to obtain binary of following an integer.as the object is very large 189866136719308462018271159242437168532L

I have implemented the new algorithm for an elliptic curve which will compute 2p,4p,8p,16p,32p........ . i want the flow of code which will use the new algorithm to compute p,2p,4p,8p,16p........... . and store it into array so that i will use it for scalar multiplication.

the above code gives me following error when run it on sagemath cloud Error in lines 13-16 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "<string>", line 4 salvus.execute_with_code_decorators(*_salvus_parsing.dec_args[Integer(3)]) ^ SyntaxError: invalid syntax

what are the standard add and doubling on E

in the above code how the addition and doubling is obtained.

offline computation , how to store precomputed data in array during scalar multiplication of elliptic curve i want the precomputed data 2p,4p,8p,16p,32p..... for further computation so how to generate that array.

left to right double and add scalar multiplication algorithm for above parameter KP=k_0p+k_12p+K_24P+.........+K_l2^l-1*P I/P point P which is on elliptic curve , K=(k_l-1K_l-2.....K_0)_2 (that is binary representation of scalar) output KP uses P and Q

Q= infinity

for i=l-1 to 0 do Q=2Q if k_i=1 then Q=Q+P
return Q

tx for your reply but i want the compution using above algorithm. also by defining function point_mul(k,p) where k is scalar and p is the point.