Code editing task: elliptic_curves
Topic: Math; change kind: adaptive

Original code:
import random

def is_prime(n):
    """Check if a number is prime."""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

class EllipticCurve:
    def __init__(self, a : int, b : int, p : int):
        self.a = a 
        self.b = b
        assert is_prime(p), "p is not prime"
        self.p = p # prime

    def is_on_curve(self, x : int, y : int) -> bool:
        return (y**2 - x**3 - self.a*x - self.b) % self.p == 0

    def mod_inverse(self, value: int) -> int:
        """ uses fermat's little theorem for modular inverse """
        return pow(value, self.p - 2, self.p)

    def point_addition(self, P: tuple, Q: tuple) -> tuple:
        """ returns the sum of the two points, P, Q 
            uses (None, None) to represent infinity """
        # cases where either point are infinity
        if P == (None, None) : return Q
        if Q == (None, None) : return P

        # P + (-P) = 0 or if the y coordinate is 0, return point at infinity
        if P[0] == Q[0] and (P[1] != Q[1] or P[1] == 0) : return (None, None)

        if P != Q:
            # The lambda (slope) calculation for two distinct points
            m = (Q[1] - P[1]) * self.mod_inverse(Q[0] - P[0] + self.p) % self.p
        else:
            # The lambda (slope) calculation for point doubling
            m = (3 * P[0]**2 + self.a) * self.mod_inverse(2 * P[1]) % self.p

        x_r = (m**2 - P[0] - Q[0]) % self.p
        y_r = (m * (P[0] - x_r) - P[1]) % self.p

        return (x_r, y_r)
    
    def point_double(self, P: tuple) -> tuple:
        """ double the given point """
        return self.point_addition(P, P)

    def point_multiplication(self, k: int, P: tuple) -> tuple:
        """scalar multiplication of P by k."""
        if P == (None, None) or k == 0:
            return (None, None)

        result = (None, None)  # Initialize result as the identity element (infinity point)
        addend = P

        while k:
            if k & 1:
                result = self.point_addition(result, addend)
            addend = self.point_addition(addend, addend)
            k >>= 1

        return result

    def generate_keypair(self, G: tuple, n: int, d : int) -> tuple:
        """ Given an initial point G and an order n, construct a keypair, and d, the private key """
        assert 1 <= d and d <= n-1
        Q = self.point_multiplication(d, G) # public key
        return (d, Q) 

    def validate_keypair(self, d: int, Q: tuple, G: tuple, n: int) -> bool:
        """ Validate the given keypair, given an initial point G,
            a public key Q, a private key d, and a group order n """
        if not (1 <= d < n) : return False
        if not self.is_on_curve(Q[0], Q[1]) : return False
        return self.point_multiplication(d, G) == Q

Instruction (descriptive):
Edit the code to include a new method `windowed_point_multiplication(self, k: int, P: tuple) -> tuple` that computes elliptic curve point multiplication using the windowing method. That is, given a window size w with a default value of 4, precompute all 2^w powers the given point. Then, as you compute the double-and-add procedure similar to in the function `point_multiplication`, use the pre-computed values. Feel free to conver the given scalar `k` to binary for the double-and-add procedure. Ensure `generate_keypair` and `validate_keypair` use `windowed_point_multiplication`.

Instruction (lazy):
Edit the code to include a new method `windowed_point_multiplication` that computes elliptic curve point multiplication using the windowing method. That is, given a window size w, precompute all 2^w powers the given point, and use the precomputed values in the double-and-add procedure. Ensure `generate_keypair` and `validate_keypair` use `windowed_point_multiplication`.

Edited code:
import random

def is_prime(n):
    """Check if a number is prime."""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

class EllipticCurve:
    def __init__(self, a : int, b : int, p : int):
        self.a = a 
        self.b = b
        assert is_prime(p), "p is not prime"
        self.p = p # prime

    def is_on_curve(self, x : int, y : int) -> bool:
        return (y**2 - x**3 - self.a*x - self.b) % self.p == 0

    def mod_inverse(self, value: int) -> int:
        """ uses fermat's little theorem for modular inverse """
        return pow(value, self.p - 2, self.p)

    def point_addition(self, P: tuple, Q: tuple) -> tuple:
        """ returns the sum of the two points, P, Q 
            uses (None, None) to represent infinity """
        # cases where either point are infinity
        if P == (None, None) : return Q
        if Q == (None, None) : return P
        
        # P + (-P) = 0 or if the y coordinate is 0, return point at infinity
        if P[0] == Q[0] and (P[1] != Q[1] or P[1] == 0) : return (None, None)

        if P != Q:
            # the lambda (slope) calculation for two distinct points
            m = (Q[1] - P[1]) * self.mod_inverse(Q[0] - P[0] + self.p) % self.p
        else:
            # the lambda (slope) calculation for point doubling
            m = (3 * P[0]**2 + self.a) * self.mod_inverse(2 * P[1]) % self.p

        x_r = (m**2 - P[0] - Q[0]) % self.p
        y_r = (m * (P[0] - x_r) - P[1]) % self.p

        return (x_r, y_r)

    def point_double(self, P: tuple) -> tuple:
        """ double the given point """
        return self.point_addition(P, P)

    def point_multiplication(self, k: int, P: tuple) -> tuple:
        """scalar multiplication of P by k."""
        if P == (None, None) or k == 0:
            return (None, None)

        result = (None, None) # initialize result as inf,inf
        addend = P

        while k:
            if k & 1:
                result = self.point_addition(result, addend)
            addend = self.point_addition(addend, addend)
            k >>= 1

        return result

    def windowed_point_multiplication(self, k: int, P: tuple, w: int = 4) -> tuple:
        if P == (None, None) or k == 0 : return (None, None)

        # precompute the multiples of P: P, 2P, 3P, ..., (2^w-1)P
        precomputed, current = [(None, None)], P
        for _ in range(1, 2**w):
            precomputed.append(current)
            current = self.point_addition(current, P)

        Q = (None, None)
        k_bin = bin(k)[2:]  # convert k to binary string

        # crocess each bit from left to right (MSB to LSB)
        for bit in k_bin:
            Q = self.point_double(Q)  # always double Q for each bit shift
            if bit == '1':
                Q = self.point_addition(Q, P)

        return Q

    def generate_keypair(self, G: tuple, n: int, d : int) -> tuple:
        """ Given an initial point G and an order n, construct a keypair, and d, the private key """
        assert 1 <= d and d <= n-1
        Q = self.windowed_point_multiplication(d, G) # public key
        return (d, Q)

    def validate_keypair(self, d: int, Q: tuple, G: tuple, n: int) -> bool:
        """ Validate the given keypair, given an initial point G,
            a public key Q, a private key d, and a group order n """
        if not (1 <= d < n) : return False
        if not self.is_on_curve(Q[0], Q[1]) : return False
        return self.windowed_point_multiplication(d, G) == Q

Tests:
### START TESTS ###
if True:
    assert is_prime(5)
    assert not is_prime(16)
    assert not is_prime(1)

    curve1 = EllipticCurve(4,4,5)
    assert curve1.is_on_curve(1,3)
    assert curve1.is_on_curve(0,2)
    assert not curve1.is_on_curve(2,2)
    assert curve1.point_addition((1,3),(1,3)) == (2,0)
    assert curve1.point_addition((1,3),(0,2)) == (0,3)
    assert curve1.point_addition((0,2),(0,-2)) == (None, None)
    assert curve1.point_addition((0,2),(None,None)) == (0,2)
    assert curve1.point_addition((None,None),(None,None)) == (None,None)
    assert curve1.point_addition((None,None),(1,3)) == (1,3)

    assert curve1.point_multiplication(3,(1,3)) == curve1.point_addition(curve1.point_addition((1,3),(1,3)),(1,3))

    curve2 = EllipticCurve(4,4,3)
    assert curve2.point_addition((0,1),(0,1)) == (1,0)
    assert curve2.point_addition((0,1),(1,0)) == (0,2)
    assert curve2.point_addition((0,2),(0,2)) == (1,0)

    assert curve2.point_multiplication(2, (0, 1)) == curve2.point_addition((0, 1), (0, 1))
    assert curve2.point_multiplication(2, (1, 0)) == curve2.point_addition((1, 0), (1, 0))
    assert curve2.point_multiplication(2, (None,None)) == (None, None)
    assert curve2.point_multiplication(0, (None,None)) == (None, None)
    assert curve2.point_multiplication(0, (0,1)) == (None, None)
    assert curve2.point_double((0,1)) == curve2.point_addition((0,1),(0,1))
    assert curve2.point_double((0,2)) == curve2.point_addition((0,2),(0,2))

    curve3 = EllipticCurve(-11,-17,307)
    assert curve3.is_on_curve(2,131)
    assert curve3.mod_inverse(3) == 205
    assert curve3.mod_inverse(45) == 116
    assert curve3.point_multiplication(4,(2,131)) == (81,246)

    points = [(2,131),(10,140),(6,146),(29,148),(16,126)]
    for point in points:
        for i in range(3,20):
            n = i
            rd = 1 + ((i + 5) % (n-1))
            d, Q = curve3.generate_keypair(point,n,rd)
            assert curve3.validate_keypair(d,Q,point,n)

    points = [(2,131),(10,140),(6,146),(29,148),(16,126)]
    for point in points:
        for i in range(3,20):
            assert curve3.point_multiplication(i,point) == curve3.windowed_point_multiplication(i,point)