# 
# Elliptic curve point addition in projective coordinates
# 
# Copyright (c) 2021 Project Nayuki. (MIT License)
# https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy of
# this software and associated documentation files (the "Software"), to deal in
# the Software without restriction, including without limitation the rights to
# use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
# the Software, and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
# - The above copyright notice and this permission notice shall be included in
#   all copies or substantial portions of the Software.
# - The Software is provided "as is", without warranty of any kind, express or
#   implied, including but not limited to the warranties of merchantability,
#   fitness for a particular purpose and noninfringement. In no event shall the
#   authors or copyright holders be liable for any claim, damages or other
#   liability, whether in an action of contract, tort or otherwise, arising from,
#   out of or in connection with the Software or the use or other dealings in the
#   Software.
# 

import random, unittest
from typing import List
from ellipticcurve import AffineCurvePoint, ProjectiveCurvePoint, FieldInt


class EllipticCurveTest(unittest.TestCase):
	
	def test_basic_affine(self) -> None:
		Z = AffineCurvePoint(None, GA.a, GA.b, MOD)
		self.assertTrue(Z.is_zero())
		self.assertFalse(Z.is_on_curve())
		self.assertEqual(Z.double(), Z)
		self.assertEqual(Z + Z, Z)
		self.assertEqual(Z + GA, GA)
		self.assertEqual(GA + Z, GA)
		self.assertTrue((GA - GA).is_zero())
		self.assertTrue((GA * ORDER).is_zero())
		
		p: AffineCurvePoint = GA
		for i in range(1, 100):
			self.assertTrue(p.is_on_curve())
			self.assertEqual(p, GA * i)
			self.assertTrue((p + -p).is_zero())
			p += GA
		
		p = -GA
		for i in range(1, 100):
			self.assertTrue(p.is_on_curve())
			self.assertEqual(p, GA * -i)
			self.assertTrue((p + -p).is_zero())
			p -= GA
	
	
	def test_basic_projective(self) -> None:
		Z = ProjectiveCurvePoint(None, GP.a, GP.b, MOD)
		self.assertTrue(Z.is_zero())
		self.assertFalse(Z.is_on_curve())
		self.assertEqual(Z.double(), Z)
		self.assertEqual(Z + Z, Z)
		self.assertEqual(Z + GP, GP)
		self.assertEqual(GP + Z, GP)
		self.assertTrue((GP - GP).is_zero())
		self.assertTrue((GP * ORDER).is_zero())
		
		p: ProjectiveCurvePoint = GP
		for i in range(1, 100):
			self.assertTrue(p.is_on_curve())
			self.assertEqual(p, GP * i)
			self.assertTrue((p + -p).is_zero())
			p += GP
		
		p = -GP
		for i in range(1, 100):
			self.assertTrue(p.is_on_curve())
			self.assertEqual(p, GP * -i)
			self.assertTrue((p + -p).is_zero())
			p -= GP
	
	
	def test_affine_vs_projective(self) -> None:
		for i in range(-100, 100):
			self.assertEqual(GA * i, (GP * i).to_affine_point())
		for _ in range(100):
			bits: int = random.randrange(300)
			n: int = random.randrange(2**bits)
			p: AffineCurvePoint = GA * n
			q: ProjectiveCurvePoint = GP * n
			self.assertTrue(p.is_zero() or p.is_on_curve())
			self.assertTrue(q.is_zero() or q.is_on_curve())
			self.assertEqual(p, q.to_affine_point())
			self.assertEqual(p.double(), p + p)
			self.assertEqual(q.double(), q + q)
			if n >= ORDER:
				self.assertEqual(p, GA * (n % ORDER))
				self.assertEqual(q, GP * (n % ORDER))



class FieldIntTest(unittest.TestCase):
	
	def test_reciprocal(self) -> None:
		CASES: List[List[int]] = [
			[0x0000000000000000000000000000000000000000000000000000000000000001, 0x0000000000000000000000000000000000000000000000000000000000000001],
			[0x0000000000000000000000000000000000000000000000000000000000000002, 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFE18],
			[0x0000000000000000000000000000000000000000000000000000000000000003, 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA9FFFFFD75],
			[0x0000000000000000000000000000000000000000000000000000000000000004, 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBFFFFF0C],
			[0x000000000000000000000000000000000000000000000000000000000000000B, 0x45D1745D1745D1745D1745D1745D1745D1745D1745D1745D1745D1741745D06A],
			[0x8000000000000000000000000000000000000000000000000000000000000000, 0x937A320A2AA70733388D85852BE56EC3796447FDB84940B3B070123B10D03625],
			[0xFF00000000000000000000000000000000000000000000000000000000000000, 0xC6839CA1B70A8E27C40ACD902618D031EEA0C4C39FC464BE96CED7F5016982BC],
			[0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2C, 0x55555555555555555555555555555555555555555555555555555554FFFFFEBA],
			[0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2D, 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFE17],
			[0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2E, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2E],
			[0x0000000040000000002000000010000000000000000000000000010000000000, 0xECB197B0AF02BA21F11DC46E5176C9768DABD04632ED312A0179307A61D8651F],
			[0x0000000000000000010000000000020000000000000000000000000000000000, 0xCE9F88395251C47DA1B15A389BA516758397E687F84A29D032F00F6ADDC00ED2],
			[0x0100000000000000000000000002000000000000000000008002001200000000, 0xE7BB6E5A4665CDDD8048383E758A2BC392B318A7D9E475BF9DE1832EA11E45B1],
			[0x0000000000000000000100000000000000000000000000000000000080000000, 0x0BE4C6479A2C9CD9B5A3FC1B2FB6037557C5CC32D20D32E9B193252DF60DA1B0],
			[0x0000000000000000000000000000000000000000000000000000000800000000, 0xBA44A6A61FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF45BB5693],
			[0x0000000000800200000000000000000000000000080000000000000000000000, 0x86C2A63AFF967FC3296B4C0326F8C22CD462FE747CD84C10837393FEB9B4331A],
			[0x0000010000000000000000000000000000000000000002000000050080000000, 0xB20BA22045BA27232C6D8E73E6130E53FFE86192312336A7994AA67BB9539D8D],
			[0x0000000000000000000000200000000000002000008000000000000000000020, 0x3DFE456451645A345F2C283F4C23370CD91E920685CD7D35B3D63ACB4D3E4486],
			[0x2000000000100000000002080000000020000000000000000020001000000000, 0xC5B46C7779772C9841ABD475ACCF25FA0C655AA1252C8D3DD370B918BF0BEE42],
			[0x0002000000000000004000000000000000000040011000004200000000000100, 0x35FA2B66B444A2646E8EB584CF074D364C8DE82B3F9C3F4BB484871840222B87],
			[0xC000010001008000000000400040420000800000200004000002000000000000, 0x691762BB9927D1FDE37C393CA61A47266799D10D02384F11CEC66D471233DD76],
			[0x0000000000000000000000200001000040000000000000000000000004000000, 0x2F5D91FA0379199695F85ABEC690EB7BC6623DED3F436266D79B8372CEFECC3A],
			[0x002000440008840000020190000000010131060000020110400A200000020200, 0x72370C13808001FBDAA830FCE93D107116ECD5C4B55ACA10E17034390D8E2C32],
			[0x0000509000110410A00220028004020000020000200840404000000200000200, 0xA9E40B54B7FB071239FD53CA5570EEDAF3F5CFA71357FAA1AE6D80E36FEF5671],
			[0x02002000000080500010040300A0003400200000000100000200000600001000, 0x2731D77E65EF210F658E01903BFE82476D71C6769008B8E9B7C22235B1B950B2],
			[0x0000008020000000028101042002000090028010010000601200220001102004, 0x8A7C67E47823CCAC705D024189CC151E08DA9C3D437679C6DE988966D2E0737F],
			[0x580ABFE333C14A172B4EE30A6E3414B1793B5A1B7E044512F03762437316485B, 0x19303494171D57D45A42D7847CAEF83DDDCBB15EE09B89A22846C447234E3C9C],
			[0x5DBD48D823FC1CE863124C73536C19D4D367D1C0CF93AF3B4A9C5C042CF04127, 0x12AC8FBC16BCBD123504C03E64CACC63221C5DEC490A55D423EDC164D671AC8A],
			[0x7B1ACF5305BCEF21EE8262CB3501F7DFA9F4757B125EE2689B139559AB737E94, 0xD48B8C7717158E6A880EE7A15A6DEE751B6ECE610099BEAC041B005D9811552C],
			[0x88F92281D8B79F249434EE365A77C8331DD15960F17A2285FCBF62913DAE638E, 0x7FB174E4018D369FA85891F1D3B4A5C9DE9D27C89C5C6B82989DFDE444E9FDEA],
			[0xFC5CA7167DF8A7F5AC2A4B326D9EF89510C157D466160702C6EB136CD7877C0B, 0xCDB8FA655DD940589EE9ACED17A3E345071C950E812D3BBDCB1F83D73E898955],
			[0x7BDBDD9EBA49A09DC328AC060378AAA90149BB97877AA27EE2C0F49E78093B4A, 0x02A68DD563AD0FC338D7F8C7D139B2B1D6A4F6B666406377C9EC362A211347BD],
			[0x72B6E00D159EFB4E46346B6D9541CB81A0337013A3569D54A80CEEA5A03BD408, 0x28C8403EEF7D2642674AE68F0CD58991B69EF41F4186A8329C023CDE4D0120D2],
			[0x109CC7044F9F1EDBEE64AA8D33EA4325116183E9EB1574A600B04589C045048B, 0xE93CFF3C41D12B3C303DE828929B29BFFD0D1DBFC4384323A7B754E29C321442],
			[0x084F1DEF6553CF294586DCB74BA804019ADD34D2343ABBBFF19A2EA9A453CB6D, 0xA70CC5B12FC2DCDB8650C2616D15474460D97B8E20C0B562C8C0D278AA79F0AE],
			[0x570229D6F3C7354805CE394505BF04B653075F7B05BBB754697C88AC1BD7207E, 0x4DDA6708B65BD91B91403B0F84A4983DC239FA789F8FD9A533859C34A01702CF],
			[0x44A266D4F06D2376A466B7B4CD56E9C1D8A13FD15D6064CA6DA7F82F44BFA984, 0xF92FD6E20E9DBA93EFBCEFF5D4670BDE15AF1A6AB91E17AD1DC877192C5701AE],
			[0x1FF4707865A5C29CBD08EC6EC97ABB9C4B8ABD8D4074B2C1DD49144234E00DE7, 0xB3FCAA1B76C5A609169AC5026C385AAF3BEB37CBE2C34EBFD1C49F02474ECC5D],
			[0xFFFFFBF7FF7FFFFFFFFBFF7FFFFFFFFF7FFFFFFFEE7DFDBFFFFFFFBFDEFFFFFF, 0x10176DA98CF511E10CB469DE3C21B32F725D8CD4E5D3D1C7EF2807A46EE83919],
			[0xFBF7FF7FFFFFFFFFFFEDFFFFFFFF7FFF3FFFFFF7FFD7FFFFDFFEF9FFFF7F7FFF, 0xF35A05C33E845843B90941B4D9887BC338A58ACC209AA384288484D00A103E7D],
			[0xFCD9FFFFFFFDFFFFFB7BDFF7FFFFFFFFB7FBFDFFFDE7FFFFFFF5DF7FBBFFFBFF, 0x5872BA2F65D0258A43B9655C71CEBF2DCCB776D0E312B82F511FE018FCBC90CC],
			[0xF5DFFFDCBFFFFEFFFFFFFFFFFFCFCF7FFDFFFFFBED7FE2FFEFDF7FFFFFFFFEFE, 0xE0B08D6C7C1B2C06BFAE1EE52687F40F476AEB06C55B97CAE73619F19390A1F1],
			[0xFFFFFFFFFFFFFFFEFFBEEFF7FFFFFFFFFFFBFFFFFFFFFFFDFFBFFFFFFFFFFFFF, 0xCB316B57BB720F5F4107B2F015BAC4E448D4A8FB454C04E3D1E3D3A40417467E],
			[0xFFFFFF7FFFFFFFFFFFFFFDFFFFFFFFFFFFFFBFBFEFFFFDFFFFFFFFFBFFFFFFFF, 0xE93C93E84B6FBAADAF9375B370338A3FFB40548E580DF43E86B790FCCE9A1EB2],
			[0xFCFFFFFFBDFFFB7FFFFFFBFFFFFFFFFFFFFFFFF7FFFF7FFFFFFFFBFFFFEFFFEF, 0x4B11C164854D94DD8506E49E6F63415F84D4E87D4AEAA556DA49B1B8755C988F],
			[0xFFFFFFFFFFF7FFFFBFFFFFFFFFDFFFFFFFFFEBFFFFFFFFF7FBFFFFDFFFFFFFF7, 0xE92ABD8E79C2A960431ED5186B773B28150634B4348E53260BD45CDCA10007C8],
			[0xFFFFFFFFFFFD7FFFFFFFFFFFFFFFFFFFFDFFFFFFFFFFFFFFFF7FFDFFFFFFFFFF, 0xA4B4BC0C127D58ACF38611F6B342B7987D8ED3ECC478FBA4ED39008DC6897B40],
			[0xFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFDFFFFF7FFFFFFFFFFFFFFFDFFFFFFFFFFF, 0x936E477CB1370054EDEDF2B53D94A76CA43634CB5E7D0164004E7CE7C2F39D7B],
			[0xFFFBFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFBFFFFFF, 0x8C4DCE37E34C5D5440586B9B85905C9132D219E34C476B8C40C2787A23FF6AC9],
			[0xFFFFBFFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, 0x7263040B5EEE4822288B6A963B256FF428820BAC9240E07B08CA6DDBF1908888],
		]
		for (x, y) in CASES:
			self.assertEqual(FieldInt(x, MOD).reciprocal(), FieldInt(y, MOD))



# Parameters for secp256k1 curve
A: int = 0
B: int = 7
MOD: int = 2**256 - 2**32 - 977
GA = AffineCurvePoint(
	(FieldInt(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, MOD),
	 FieldInt(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8, MOD)),
	FieldInt(A, MOD), FieldInt(B, MOD), MOD)
GP = GA.to_projective_point()
ORDER: int = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141


if __name__ == "__main__":
	unittest.main()