Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

asked 2021-03-14 14:58:29 +0100

Miroslaw gravatar image

Infinity point how it defined - Secp256K Curve

I have problem with point infinity. How to solve it? Curve Secp256k 

# A Python3 program to check if a given point  
# lies inside a given polygon 
#  
# for explanation of functions onSegment(), 
# orientation() and doIntersect()  

# Define Infinite (Using INT_MAX  
# caused overflow problems)
INT_MAX = 9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

# Given three colinear points p, q, r,  
# the function checks if point q lies 
# on line segment 'pr' 
def onSegment(p:tuple, q:tuple, r:tuple) -> bool:

    if ((q[0] <= max(p[0], r[0])) &
        (q[0] >= min(p[0], r[0])) &
        (q[1] <= max(p[1], r[1])) &
        (q[1] >= min(p[1], r[1]))):
        return True

    return False

# To find orientation of ordered triplet (p, q, r). 
# The function returns following values 
# 0 --> p, q and r are colinear 
# 1 --> Clockwise 
# 2 --> Counterclockwise 
def orientation(p:tuple, q:tuple, r:tuple) -> int:

    val = (((q[1] - p[1]) *
            (r[0] - q[0])) -
           ((q[0] - p[0]) *
            (r[1] - q[1])))

    if val == 0:
        return 0
    if val > 0:
        return 1 # Collinear
    else:
        return 2 # Clock or counterclock

def doIntersect(p1, q1, p2, q2):

    # Find the four orientations needed for  
    # general and special cases 
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2) and (o3 != o4):
        return True

    # Special Cases 
    # p1, q1 and p2 are colinear and 
    # p2 lies on segment p1q1 
    if (o1 == 0) and (onSegment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and 
    # q2 lies on segment p1q1 
    if (o2 == 0) and (onSegment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and 
    # p1 lies on segment p2q2 
    if (o3 == 0) and (onSegment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and 
    # q1 lies on segment p2q2 
    if (o4 == 0) and (onSegment(p2, q1, q2)):
        return True

    return False

# Returns true if the point p lies  
# inside the polygon[] with n vertices 
def is_inside_polygon(points:list, p:tuple) -> bool:

    n = len(points)

    # There must be at least 3 vertices
    # in polygon
    if n < 3:
        return False

    # Create a point for line segment
    # from p to infinite
    extreme = (INT_MAX, p[1])    # here point infinity - how to solve it? i
    count = i = 0

    while True:
        next = (i + 1) % n

        # Check if the line segment from 'p' to  
        # 'extreme' intersects with the line  
        # segment from 'polygon[i]' to 'polygon[next]' 
        if (doIntersect(points[i],
                        points[next], 
                        p, extreme)):

            # If the point 'p' is colinear with line  
            # segment 'i-next', then check if it lies  
            # on segment. If it lies, return true, otherwise false 
            if orientation(points[i], p, 
                           points[next]) == 0:
                return onSegment(points[i], p, 
                                 points[next])

            count += 1

        i = next

        if (i == 0):
            break

    # Return true if count is odd, false otherwise 
    return (count % 2 == 1)

# Driver code
if __name__ == '__main__':
#i: 1    
    x= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
#i:  2
    x2= 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
    y2= 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
#i:  3
    x3= 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
    y3= 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
#i:  4
    x4= 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
    y4= 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922
#i:  5
    x5= 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
    y5= 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
#i:  6
    x6= 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556
    y6= 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297


    polygon1 = [ (x,y), (x2,y2), (x4, y4), (x5, x5),(x6,y6) ]

    p = (x3, y3)
    if (is_inside_polygon(points = polygon1, p = p)):
      print ('Yes')
    else:
      print ('No')

Infinity point how it defined - Secp256K Curve

I have problem with point infinity. How to solve it? Curve Secp256k 

# A Python3 program to check if a given point  
# lies inside a given polygon 
#  
# for explanation of functions onSegment(), 
# orientation() and doIntersect()  

# Define Infinite (Using INT_MAX  
# caused overflow problems)
INT_MAX = 9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

# Given three colinear points p, q, r,  
# the function checks if point q lies 
# on line segment 'pr' 
def onSegment(p:tuple, q:tuple, r:tuple) -> bool:

    if ((q[0] <= max(p[0], r[0])) &
        (q[0] >= min(p[0], r[0])) &
        (q[1] <= max(p[1], r[1])) &
        (q[1] >= min(p[1], r[1]))):
        return True

    return False

# To find orientation of ordered triplet (p, q, r). 
# The function returns following values 
# 0 --> p, q and r are colinear 
# 1 --> Clockwise 
# 2 --> Counterclockwise 
def orientation(p:tuple, q:tuple, r:tuple) -> int:

    val = (((q[1] - p[1]) *
            (r[0] - q[0])) -
           ((q[0] - p[0]) *
            (r[1] - q[1])))

    if val == 0:
        return 0
    if val > 0:
        return 1 # Collinear
    else:
        return 2 # Clock or counterclock

def doIntersect(p1, q1, p2, q2):

    # Find the four orientations needed for  
    # general and special cases 
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2) and (o3 != o4):
        return True

    # Special Cases 
    # p1, q1 and p2 are colinear and 
    # p2 lies on segment p1q1 
    if (o1 == 0) and (onSegment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and 
    # q2 lies on segment p1q1 
    if (o2 == 0) and (onSegment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and 
    # p1 lies on segment p2q2 
    if (o3 == 0) and (onSegment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and 
    # q1 lies on segment p2q2 
    if (o4 == 0) and (onSegment(p2, q1, q2)):
        return True

    return False

# Returns true if the point p lies  
# inside the polygon[] with n vertices 
def is_inside_polygon(points:list, p:tuple) -> bool:

    n = len(points)

    # There must be at least 3 vertices
    # in polygon
    if n < 3:
        return False

    # Create a point for line segment
    # from p to infinite
    extreme = (INT_MAX, p[1])    # **

here point infinity - how to solve it? it?

** i count = i = 0 0

    while True:
        next = (i + 1) % n

        # Check if the line segment from 'p' to  
        # 'extreme' intersects with the line  
        # segment from 'polygon[i]' to 'polygon[next]' 
        if (doIntersect(points[i],
                        points[next], 
                        p, extreme)):

            # If the point 'p' is colinear with line  
            # segment 'i-next', then check if it lies  
            # on segment. If it lies, return true, otherwise false 
            if orientation(points[i], p, 
                           points[next]) == 0:
                return onSegment(points[i], p, 
                                 points[next])

            count += 1

        i = next

        if (i == 0):
            break

    # Return true if count is odd, false otherwise 
    return (count % 2 == 1)

# Driver code
if __name__ == '__main__':
#i: 1    
    x= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
#i:  2
    x2= 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
    y2= 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
#i:  3
    x3= 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
    y3= 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
#i:  4
    x4= 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
    y4= 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922
#i:  5
    x5= 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
    y5= 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
#i:  6
    x6= 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556
    y6= 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297


    polygon1 = [ (x,y), (x2,y2), (x4, y4), (x5, x5),(x6,y6) ]

    p = (x3, y3)
    if (is_inside_polygon(points = polygon1, p = p)):
      print ('Yes')
    else:
      print ('No')

Infinity point how it defined - Secp256K Curve

I have problem with point infinity. How to solve it? Curve Secp256k 

# A Python3 program to check if a given point  
# lies inside a given polygon 
#  
# for explanation of functions onSegment(), 
# orientation() and doIntersect()  

# Define Infinite (Using INT_MAX  
# caused overflow problems)
INT_MAX = 9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

# Given three colinear points p, q, r,  
# the function checks if point q lies 
# on line segment 'pr' 
def onSegment(p:tuple, q:tuple, r:tuple) -> bool:

    if ((q[0] <= max(p[0], r[0])) &
        (q[0] >= min(p[0], r[0])) &
        (q[1] <= max(p[1], r[1])) &
        (q[1] >= min(p[1], r[1]))):
        return True

    return False

# To find orientation of ordered triplet (p, q, r). 
# The function returns following values 
# 0 --> p, q and r are colinear 
# 1 --> Clockwise 
# 2 --> Counterclockwise 
def orientation(p:tuple, q:tuple, r:tuple) -> int:

    val = (((q[1] - p[1]) *
            (r[0] - q[0])) -
           ((q[0] - p[0]) *
            (r[1] - q[1])))

    if val == 0:
        return 0
    if val > 0:
        return 1 # Collinear
    else:
        return 2 # Clock or counterclock

def doIntersect(p1, q1, p2, q2):

    # Find the four orientations needed for  
    # general and special cases 
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2) and (o3 != o4):
        return True

    # Special Cases 
    # p1, q1 and p2 are colinear and 
    # p2 lies on segment p1q1 
    if (o1 == 0) and (onSegment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and 
    # q2 lies on segment p1q1 
    if (o2 == 0) and (onSegment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and 
    # p1 lies on segment p2q2 
    if (o3 == 0) and (onSegment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and 
    # q1 lies on segment p2q2 
    if (o4 == 0) and (onSegment(p2, q1, q2)):
        return True

    return False

# Returns true if the point p lies  
# inside the polygon[] with n vertices 
def is_inside_polygon(points:list, p:tuple) -> bool:

    n = len(points)

    # There must be at least 3 vertices
    # in polygon
    if n < 3:
        return False

    # **

Create a point for line segment segment

    # from p to infinite
infinite - hot defined this point?

** extreme = (INT_MAX, p[1]) **

here point infinity - how to solve it?

** i
count = i = 0

    while True:
        next = (i + 1) % n

        # Check if the line segment from 'p' to  
        # 'extreme' intersects with the line  
        # segment from 'polygon[i]' to 'polygon[next]' 
        if (doIntersect(points[i],
                        points[next], 
                        p, extreme)):

            # If the point 'p' is colinear with line  
            # segment 'i-next', then check if it lies  
            # on segment. If it lies, return true, otherwise false 
            if orientation(points[i], p, 
                           points[next]) == 0:
                return onSegment(points[i], p, 
                                 points[next])

            count += 1

        i = next

        if (i == 0):
            break

    # Return true if count is odd, false otherwise 
    return (count % 2 == 1)

# Driver code
if __name__ == '__main__':
#i: 1    
    x= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
#i:  2
    x2= 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
    y2= 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
#i:  3
    x3= 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
    y3= 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
#i:  4
    x4= 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
    y4= 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922
#i:  5
    x5= 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
    y5= 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
#i:  6
    x6= 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556
    y6= 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297


    polygon1 = [ (x,y), (x2,y2), (x4, y4), (x5, x5),(x6,y6) ]

    p = (x3, y3)
    if (is_inside_polygon(points = polygon1, p = p)):
      print ('Yes')
    else:
      print ('No')
click to hide/show revision 4
None

updated 2021-03-14 17:49:11 +0100

slelievre gravatar image

Infinity point how it defined - Secp256K Curve

I have problem with point infinity. How to solve it? it?

Curve Secp256k Secp256k

# A Python3 program to check if a given point  
point
# lies inside a given polygon 
polygon
#  
# for explanation of functions onSegment(), 
onSegment(),
# orientation() and doIntersect()  
doIntersect()

# Define Infinite Infinity (Using INT_MAX  
INT_MAX
# caused overflow problems)
INT_MAX = 9000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

# Given three colinear points p, q, r,  
# the function checks if def onSegment(p: tuple, q: tuple, r: tuple) -> bool:
    r"""
    Check whether point q lies 
# on line segment 'pr' 
def onSegment(p:tuple, q:tuple, r:tuple) -> bool:

    if ((q[0] 'pr'
    """
    if (q[0] <= max(p[0], r[0])) &
        (q[0] r[0]) and
        q[0] >= min(p[0], r[0])) &
        (q[1] r[0]) and
        q[1] <= max(p[1], r[1])) &
        (q[1] r[1]) and
        q[1] >= min(p[1], r[1]))):
r[1])):
        return True
     return False

# To find def orientation(p: tuple, q: tuple, r: tuple) -> int:
    r"""
    Return the orientation of the ordered triplet triple (p, q, r). 
# r).

    The function returns following values 
# orientation is encoded as:

    - 0 --> if p, q and r are colinear 
# collinear
    - 1 --> Clockwise 
# if they turn clockwise
    - 2 --> Counterclockwise 
def orientation(p:tuple, q:tuple, r:tuple) -> int:

if they turn counterclockwise
    """
    val = (((q[1] ((q[1] - p[1]) *
            * (r[0] - q[0])) -
           ((q[0] q[0])
           - (q[0] - p[0]) *
            * (r[1] - q[1])))

q[1]))
    if val == 0:
        return 0
    if val > 0:
        return 1 # Collinear
    else:
        return 2 # Clock or counterclock
1
    return 2

def doIntersect(p1, q1, p2, q2):
     # Find the four orientations needed for  
for
    # general and special cases 
cases
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 o1 != o2) o2 and (o3 o3 != o4):
o4:
        return True

    # Special Cases 
cases
    # p1, q1 and p2 are colinear and 
collinear and
    # p2 lies on segment p1q1 
    if (o1 p1q1
    if o1 == 0) 0 and (onSegment(p1, onSegment(p1, p2, q1)):
q1):
        return True

    # p1, q1 and p2 are colinear and 
collinear and
    # q2 lies on segment p1q1 
    if (o2 p1q1
    if o2 == 0) 0 and (onSegment(p1, onSegment(p1, q2, q1)):
q1):
        return True

    # p2, q2 and p1 are colinear and 
collinear and
    # p1 lies on segment p2q2 
    if (o3 p2q2
    if o3 == 0) 0 and (onSegment(p2, onSegment(p2, p1, q2)):
q2):
        return True

    # p2, q2 and q1 are colinear and 
collinear and
    # q1 lies on segment p2q2 
    if (o4 p2q2
    if o4 == 0) 0 and (onSegment(p2, onSegment(p2, q1, q2)):
q2):
        return True

    return False

# Returns true if def is_inside_polygon(points: list, p: tuple) -> bool:
    r"""
    Check whether the point p ``p`` lies  
# inside inside
    the polygon[] with n vertices 
def is_inside_polygon(points:list, p:tuple) -> bool:

polygon defined by ``points``.
    """
    n = len(points)

    # There must be at least 3 vertices
    # in polygon
    if n < 3:
        return False

    **

# Create a point for line segment

segment
    # from p to infinite infinity - hot defined how to define this point?

** extreme = (INT_MAX, p[1])
p[1]) count = i = 0

0

    while True:
        next = (i + 1) % n

        # Check if the line segment from 'p' to  
to
        # 'extreme' intersects with the line  
line
        # segment from 'polygon[i]' to 'polygon[next]' 
        if (doIntersect(points[i],
                        points[next], 
 'polygon[next]'
        if doIntersect(points[i],
                       points[next],
                       p, extreme)):
extreme):

            # If the point 'p' is colinear collinear with line  
line
            # segment 'i-next', then check if it lies  
lies
            # on segment. If it lies, return true, otherwise false 
false
            if orientation(points[i], p, 
p,
                           points[next]) == 0:
                return onSegment(points[i], p, 
p,
                                 points[next])

            count += 1

        i = next

        if (i i == 0):
0:
            break

    # Return true True if count is odd, false otherwise 
    return (count False otherwise
    return count % 2 == 1)
1

# Driver code
if __name__ == '__main__':
#i: 1    
    x=     # i: 1
    x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
    y= y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
#i:      # i: 2
    x2= x2 = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
    y2= y2 = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
#i:      # i: 3
    x3= x3 = 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
    y3= y3 = 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
#i:      # i: 4
    x4= x4 = 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
    y4= y4 = 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922
#i:      # i: 5
    x5= x5 = 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
    y5= y5 = 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6
#i:      # i: 6
    x6= x6 = 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556
    y6= y6 = 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297

     polygon1 = [ (x,y), (x2,y2), [(x, y), (x2, y2), (x4, y4), (x5, x5),(x6,y6) ]
x5), (x6, y6)]

    p = (x3, y3)
    if (is_inside_polygon(points = polygon1, p = p)):
is_inside_polygon(points=polygon1, p=p):
        print ('Yes')
    else:
       print ('No')
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59