Ask Your Question
1

Getting code dumped error in sage code for weil-pairing ?

asked 2016-11-28 22:46:08 -0500

SP Harish gravatar image

I have been trying to run a sage code for doing weil-pairing which gives the following error message: ' /usr/lib/sagemath/local/bin/sage-python: line 2: 15172 Segmentation fault (core dumped) sage -python "$@" '

I tried sage versions 7.2, 7.3, and 7.4 but still getting same error. I am using Ubuntu 14.04. But it works in another system running Ubuntu. Someone please help.

# Weil Pairing Example
# Example 5.43 in IMC

# E: y^2 = x^3 + 30x + 34 mod 631
p = 631
a = 30
b = 34
E = EllipticCurve(GF(p), [a, b])

print E

P = E((36, 60))
Q = E((121, 387))
n = 5
S = E((0, 36))

print "P =", P.xy()
print "Q =", Q.xy()
print "#P = #Q =", n

var('x y')
def g(P, Q):
(x_P, y_P) = P.xy()
(x_Q, y_Q) = Q.xy()
if x_P == x_Q and y_P + y_Q == 0:
    return x - x_P
if P == Q:
    slope = (3 * x_P^2 + a)/(2 * y_P)
else:
    slope = (y_P - y_Q)/(x_P - x_Q)
return (y - y_P - slope * (x - x_P))/(x + x_P + x_Q - slope^2)

def miller(m, P):
m = bin(m)[3:]
n = len(m)
T = P
f = 1
for i in range(n):
    f = f^2 * g(T, T)
    T = T + T
    if int(m[i]) == 1:
        f = f * g(T, P)
        T = T + P
return f

def eval_miller(P, Q):
f = miller(n, P)
(x1, y1) = Q.xy()
return f(x = x1, y = y1)

def weil_pairing(P, Q, S):
num = eval_miller(P, Q+S)/eval_miller(P,  S)
den = eval_miller(Q, P-S)/eval_miller(Q, -S)
return (num/den)

e = weil_pairing(P, Q, S)
print "e(P, Q) =", e

# e^n = 1
print "e(P, Q)^n =", e^n

P3 = P * 3
Q4 = Q * 4
e12 = weil_pairing(P3, Q4, S)

print "[3]P =", P3.xy()
print "[4]Q =", Q4.xy()
print "e([3]P, [4]Q) =", e12
print "e(P, Q)^12 =", e^12
edit retag flag offensive close merge delete

Comments

@SP Harish, the body of each def function(arguments): block should be indented. Please edit your question.

slelievre gravatar imageslelievre ( 2016-11-29 05:28:09 -0500 )edit

See a minimal example illustrating the segmentation fault at the end of my answer.

slelievre gravatar imageslelievre ( 2016-11-29 08:40:14 -0500 )edit

If you just care about Weil pairing, see John Cremona's answer on sage-support.

If you want to write your own function, see a possible fix in my answer below.

slelievre gravatar imageslelievre ( 2016-11-29 09:25:28 -0500 )edit

@SP Harish, you say "it works in another system running Ubuntu", can you give details?

slelievre gravatar imageslelievre ( 2016-12-03 08:58:29 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-11-29 06:48:39 -0500

updated 2016-11-29 08:00:33 -0500

I can confirm the segmentation fault bug.

Please find below

  • a fix for your code,
  • a minimal example triggering the segmentation fault.

Better working Weil Pairing code

Replace the definition of x, y by the following:

R.<x, y> = GF(p)[]

Then everything will work nicely.

For instance, define the setup as follows.

p = 631

F = GF(p)
R.<x,y> = F[]

a = 30
b = 34

E = EllipticCurve(F, [a, b])

P = E((36, 60))
Q = E((121, 387))
S = E((0, 36))

n = 5

def g(P, Q):
    (x_P, y_P) = P.xy()
    (x_Q, y_Q) = Q.xy()
    if x_P == x_Q and y_P + y_Q == 0:
        return x - x_P
    if P == Q:
        slope = (3 * x_P^2 + a)/(2 * y_P)
    else:
        slope = (y_P - y_Q)/(x_P - x_Q)
    return (y - y_P - slope * (x - x_P))/(x + x_P + x_Q - slope^2)

def miller(m, P):
    m = bin(m)[3:]
    n = len(m)
    T = P
    f = 1
    for i in range(n):
        f = f^2 * g(T, T)
        T = T + T
        if int(m[i]) == 1:
            f = f * g(T, P)
            T = T + P
    return f

def eval_miller(P, Q):
    f = miller(n, P)
    (x1, y1) = Q.xy()
    return f(x = x1, y = y1)

def weil_pairing(P, Q, S):
    num = eval_miller(P, Q+S)/eval_miller(P,  S)
    den = eval_miller(Q, P-S)/eval_miller(Q, -S)
    return (num/den)

Then the following works as expected:

sage: e = weil_pairing(P, Q, S)
sage: print "e(P, Q) =", e
e(P, Q) = 242
sage: print "e(P, Q)^n =", e^n
e(P, Q)^n = 1
sage: P3 = P * 3
sage: Q4 = Q * 4
sage: e12 = weil_pairing(P3, Q4, S)
sage: print "[3]P =", P3.xy()
[3]P = (617, 5)
sage: print "[4]Q =", Q4.xy()
[4]Q = (121, 244)
sage: print "e([3]P, [4]Q) =", e12
e([3]P, [4]Q) = -119
sage: print "e(P, Q)^12 =", e^12
e(P, Q)^12 = -119

Minimal example for the segmentation fault

The following produces a segfault using Sage 7.3 or Sage 7.4 built from source on OS X 10.10.5 "Yosemite".

sage: F = GF(3)
sage: num, den = F(2)*x + F(1), x
sage: num/den
[1]    ... segmentation fault  ...
edit flag offensive delete link more

Comments

Nice MWE - did you report it "upstream"?

kcrisman gravatar imagekcrisman ( 2016-11-29 08:19:11 -0500 )edit

@kcrisman, thanks!

  • I'm still exploring and finding related weird things regarding "finite fields and Sage's symbolic ring",

  • I also want to search sage-devel, sage-support, sage-release and Sage's trac some more on this,

  • I'll report within a day on the appropriate channel, and I'll provide a link here.

slelievre gravatar imageslelievre ( 2016-11-29 08:37:52 -0500 )edit

@slelievre no worries, it was just a reminder :)

kcrisman gravatar imagekcrisman ( 2016-11-29 15:18:16 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-11-28 22:46:08 -0500

Seen: 92 times

Last updated: Nov 29 '16