In the elliptic cryptography field we use a finite field and use a form of: \(y^2 = x^3 + a.x + b \pmod p\). The Mordell curve does not constrain the computation into a finite field and has the form of: \(y^2 = x^3 + n\). It was analysed by Louis Mordell and who showed that there are only a finite number of integer solutions to this. In this case, we will determine the integer solutions to a Mordell curve, but using a finite field - and using a prime number (\(p\)) of the form of \(y^2=x^3+n \pmod p\) [Mordell Curve].
Mordell curve (with finite field)TheoryIn the elliptic cryptography field we use finite field and use a form of: \(y^2 = x^3 + a.x + b \pmod p\) The Mordell curve does not constrain the computation into a finite field and has the form of: \(y^2= x^3+ n\) The Mordell Curve comes from Louis Mordell and who showed that there are only a finite number of integer solutions to this. With \(y^2=x^3+17\), we 16 possible integer points [1]. If we plot the Mordell curve for \(y^2=x^3+17\), we get this [here]: In this case, we can see that we have six possible points in the range of -2 to 2. In a finite field problem, we would normally be constrained with a prime number, and where we find the quadratic root. But, we are not constrained, so we will have to search manually. With this we will compute the solutions for values up to 100,000: import math import sys r=100000 n=17 if (len(sys.argv)>1): n=int(sys.argv[1]) print(f"y^2=x^3+{n}") print ("Solutions: ") for x in range(-20, r): y_2 = x**3 + n if (y_2>0): y=math.sqrt(y_2) if (y.is_integer()): print ("Found: ",int (x),int(y)) A run of this shows: Found: -2 3 Found: -1 4 Found: 2 5 Found: 4 9 Found: 8 23 Found: 43 282 Found: 52 375 Found: 5234 378661 And we can see we have eight points of (-2,3), (-1,4), (2,5), (4,9), (8,23), (43, 282), (52,375) and (5234,378661). Then we can add the negative values of y to get the rest of the points: (-2,-3), (-1,-4), (2,-5), (4,-9), (8,-23), (43, -282), (52,-375) and (5234,-378661). If we sample a few we get: For (-2,-3) → (-3)² = (-2)³ + 17 -> 9 = 9 For (43,282) -> (282)² = (43)³ + 17 -> 79524 = 79507 + 17 Elliptic curve cryptographyWe do not use Mordell curves for elliptic curve cryptography. For this we use a finite field of the form: \(y^2 = x^3 + ax +b \pmod p\) and where p is a large prime number (normally around 256 bits long). If we try a=0, b=17 and p=2²⁵⁵-19, we have: \(y^2 = x^3 + 17 \pmod {2^{255}-19}\) Now we can use a quadratic residue method to determine the solution of (x,y): import libnum import sys p=2**255-19 r=100 n=17 if (len(sys.argv)>1): n=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) print(f"y^2=x^3+{n} (mod {p})\n") for x in range(0, r): if (x>p): break y_2 = pow(x,3,p) + n if (libnum.has_sqrtmod(y_2,{p:1})): y=next(libnum.sqrtmod(y_2,{p:1})) print (f"Found: ({x},{y})") A sample run for the points up to \(x=100\) for \(y^2=x^3+17 \pmod {997}\): y^2=x^3+17 (mod 997) Found: (2,992) Found: (4,9) Found: (7,804) Found: (8,23) Found: (11,523) Found: (12,498) Found: (13,742) Found: (14,42) Found: (15,524) Found: (17,908) Found: (21,906) Found: (23,742) Found: (24,487) Found: (25,749) Found: (28,114) Found: (29,844) Found: (31,594) Found: (37,490) Found: (39,446) Found: (41,56) Found: (42,185) Found: (43,282) Found: (48,953) Found: (51,319) Found: (52,375) Found: (55,683) Found: (57,88) Found: (59,534) Found: (60,779) Found: (65,348) Found: (67,876) Found: (68,539) Found: (69,551) Found: (70,990) Found: (76,378) Found: (77,871) Found: (78,388) Found: (80,390) Found: (81,516) Found: (85,360) Found: (86,170) Found: (89,293) Found: (91,62) Found: (92,622) Found: (93,562) Found: (94,987) Found: (97,732) Found: (99,661) We can see that some of the x-axis points do not exist, such as for x=82, x=83 and x=84. And for \(y^2=x^3+17 \pmod {2^{255}-19}\): y^2=x^3+17 (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949) Found: (2,5) Found: (4,9) Found: (5,57800787394070956223430301608988389592958150720113516802481917179795121371783) Found: (6,13554660953088752976062579461958686215471337427385637654648525103553495795318) Found: (8,57896044618658097711785492504343953926634992332820282019728792003956564819926) Found: (10,47422998955828599794015002653885857561096684236460224366449083273632902735987) Found: (16,52099417252327274935470940374098828688298625794234243822754664480372217082192) Found: (18,50418846706062928586095650597602650559879216922608689843503666778337728370269) Found: (21,48522062596411172360081026727420813060485212876531882605295029195132772978620) Found: (23,34363427189385326838946870757664243422073398808942794773362454787598790323870) Found: (24,15350806730153623615185850141980208121341326665696416044955244766377360368248) Found: (27,32071300461033129460024284578043250945306967944784079341837044856667373231693) Found: (29,40049969268298181298325883112532978546585056893299156654425725834432582076272) Found: (31,23816130128998847322058381740966803868843090904842359313626313702976064590975) Found: (34,24841320630278285857553940559428697998572081150684518179182261258428892177467) Found: (35,31158340905102131809307996575399725138091300555104946410051579599356257871945) Found: (37,40812849727134136473740581020366670695051299873314350606255140785275532775405) Found: (38,24961486405884519694110818426994537878911444152544986208489437892651190091271) Found: (40,26722548616731531116253010698086663312512725483801945843795048165407120129233) Found: (41,37672780910489767151961792740944799934927503581355081277863764162457061807294) Found: (42,7816688925062250952379300010221117975143960932597678495817737746030020850834) Found: (43,282) Found: (47,4399884030186173224146747235408361114530573133727980415601784090900691026741) Found: (48,26815023295711448867901192296619593590111719494569920178571836010430301683491) Found: (49,23490464128453720982333933518243484145111207249113919321404201765020796581121) Found: (52,375) Found: (53,4798588938186369510385990275250967211815701045055784882281771565712744034515) Found: (55,37809194884583519049424944536422728109816410699695581216744272897252580748167) Found: (56,55331474097510291481920787212273895378892077489276009454548782416950074368845) Found: (58,16601280762178864470815693345821597254293644920499417442666882032052386414331) Found: (61,35986750229327926102012956552408297800094277027400097866459671822092055941532) Found: (62,24353352799656889538358502288935973359020732549120591841867573126555253060451) Found: (63,27430896521703228943618963721065657030814473375874229094649908284358538359915) Found: (66,26911308819090969753859581315167042326075006111265199628340167342258977409885) Found: (70,17763050496603892639993786637998581788432052343587356690162560888647831859059) Found: (76,9917293782433180655207042834065241735321299874267850509559125693424140388114) Found: (79,53790033746405713018203233008649201092678580501330968152742712468094203274236) Found: (81,52306181368836376530513681226438934946629112112226793976253827896073414854496) Found: (83,54145057902203407050660115549725422153075727446973577296927435380661486596015) Found: (85,37184163763180592028350692802335037406647601407009365145789536944379723733320) Found: (88,46605087641559515616540059118391678318077234607015134634118152401233721721979) Found: (90,15764804636583225799885526346458760241861965824556828079076491710038558831470) Found: (91,355450063868251267908332451452511479478005565994827226364721107391238320478) Found: (92,23675047858645477040286511197178979156161322025558259080716406381453256991459) Found: (94,14529853613922621224832115569356340122670924881612323595302842757346137740132) Found: (97,11039914837507245940833514018359653337597712174101912846793001131788293318612) Found: (99,39275862361156359764865193328419687144795077692475579141197026214448912997069) Now, we see we have many more points, and where x=1, x=3 and x=93 do not exist for a solution. It should be noted that there are two y-axis points for every x-value. ConclusionsOur online security is highly dependent on elliptic curve methods, so thank them for knowing that you have a secure encryption tunnel when connecting to Web sites. Under the hood, we use ECDH (Elliptic Curve Diffie Hellman) and which often uses the P256 curve. For Bitcoin, we use: \(y^2=x^3 + 7 \pmod p\) References[1] Brown, E., & Myers, B. T. (2002). Elliptic curves from Mordell to Diophantus and back. The American mathematical monthly, 109(7), 639–649. |