{"entities":{"Q2370640":{"pageid":2381383,"ns":120,"title":"Item:Q2370640","lastrevid":50124131,"modified":"2026-01-13T05:30:23Z","type":"item","id":"Q2370640","labels":{"en":{"language":"en","value":"An efficient probabilistic public-key cryptosystem over quadratic fields quotients"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5168559"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$54B5C2DA-EF59-49F2-B5E2-4CBB23663C81","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f69829fc1c8bf9dc5bcd78777527cd8288969f9d","datavalue":{"value":{"text":"An efficient probabilistic public-key cryptosystem over quadratic fields quotients","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2370640$EF188C78-4401-4BB7-9ECB-317BA6F35DE3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"881989b36ff3004dfac9c5d57048c4dc1d72f579","datavalue":{"value":"1129.11056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$F3CB8E75-65BD-453B-94F0-F1EC05A2E8BD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e9b9e605b0d8e68ec25a51847e33400b7a338ca9","datavalue":{"value":{"entity-type":"item","numeric-id":1675727,"id":"Q1675727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$530039E5-3927-43FD-999A-BBEA13FFF37C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"33122a93dfb64681be222c65bf841053fa198b88","datavalue":{"value":{"entity-type":"item","numeric-id":165874,"id":"Q165874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$2046B20C-8E83-44CB-AF1C-20998DBED4B9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aa1c5baac12078a594b435871811db79b2b7374f","datavalue":{"value":{"time":"+2007-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2370640$AB3B3312-B09B-4EB3-97D5-8BAE9AB34F0B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8edd8ca4b744597672897ed5fb8e5c82e77a5b38","datavalue":{"value":"Quotients of quadratic fields feature in important primality tests and factoring. The LUC cryptosystem which was described by Smith, Lennon and Skinner in terms of Lucas sequences can be recast in this setting making its similarity to the RSA scheme clear. To this end, let \\(d\\) be an integer which is not a square, \\(\\mathcal O\\) the ring of integers of \\({\\mathbb Q}(\\sqrt d)\\), \\(n\\) an integer prime to \\(d\\), \\(N\\) the norm on \\({\\mathbb Q}(\\sqrt d)\\) defined by \\(N(x+y\\sqrt d)=x^2-dy^2\\) and Tr the trace defined by \\(\\text{Tr}(x+y\\sqrt d)=2x\\). Work in the multiplicative group \\({(\\mathcal O}/n{\\mathcal O})^\\times\\) which is also the set of finite points on the conic \\(X^2-dY^2=1\\). Let \\(d=P^2-4Q\\) and define the Lucas sequences:  \\[ \\begin{align*}{U_{k+1}(P,Q)&=PU_k(P,Q)-QU_{k-1}(P,Q), U_1(P,Q)=1, U_0(P,Q)=0\\cr V_{k+1}(P,Q)&=PV_k(P,Q)-QV_{k-1}(P,Q), V_1(P,Q)=P, V_0(P,Q)=2\\cr}\\end{align*} \\]  Lucas sequences enable efficient exponentiation in \\({\\mathcal O}\\). Let \\(\\alpha\\equiv x+y\\sqrt d\\bmod n\\). Then  \\[ \\alpha^r\\equiv {V_r(2x,N\\alpha)\\over 2}+yU_r(2x,N\\alpha)\\sqrt d, \\quad \\text{Tr}(\\alpha^r)\\equiv V_r(2x, N\\alpha)\\bmod n. \\]  Let \\(n=pq\\) where \\(p,q\\) are distinct odd primes and let \\(e\\) be an integer prime to \\((p^2-1)(q^2-1)\\). The \\(\\text{LUC}_e\\) function is defined by \\(x\\rightarrow V_e(x)\\). It is a permutation on the integers \\(x\\) with \\(0<x<n\\) and \\(\\text{gcd}(x^2-4,n)=1\\) and the connection to exponentiation \\(\\alpha\\rightarrow\\alpha^e\\) via the above congruence shows the analogy with the RSA function \\(x\\rightarrow x^e\\) defined on the integers modulo \\(n\\). The properties of LUC can be derived from the relationship to exponentiation \\(\\alpha\\rightarrow\\alpha^e\\) on \\({\\mathcal O}\\bmod n\\). For example, the inverse of \\(\\text{LUC}_e\\) is \\(\\text{LUC}_d\\) where \\(de\\equiv 1\\bmod \\phi_d(n)\\) and \\(\\phi_d(n)=(p-({d\\over p}))(q-({d\\over q}))\\) is the order of \\({\\mathcal O}\\bmod n\\).  The author uses LUC to define a new probabilistic cryptosystem in the same way that Catalano, Gennaro, Howgrave-Graham and Nguyen used RSA. The encryption function is  \\[ {\\mathcal E}_e: (m,r)\\rightarrow (1+n)^mV_e(r)\\bmod n^2 \\]  where \\(m\\) is in \\({\\mathbb Z}/n{\\mathbb Z}\\) and \\(x\\) is an integer with \\(0<x<n, \\text{ gcd}(x^2-4,n)=1, \\text{ gcd}(x,n)=1\\). To encrypt \\(m\\) take \\(r\\) randomly from \\(\\{1,2,\\ldots,n-1\\}\\) and calculate \\(c=(1+n)^mV_e(r)\\bmod n^2\\). The scheme appears to be at least as secure as RSA and the author shows that it is computationally competitive with other probabilistic schemes such as El Gamal's method based on RSA and elliptic curves.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2370640$6773C7B5-8DDF-4494-A306-659F3D13B45B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$B92122FF-77AC-4805-9E9C-8F862D85336A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$575AC6B1-E5F6-4585-A99A-32E683AC9B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ccc5a5c9dd2865ab4417f7cabfcec0ef477e1206","datavalue":{"value":"11B39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$DD491CF4-C59A-4F69-BE70-8E364D072726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a96ec27960548a095ff7d83af50617655333860","datavalue":{"value":"11R11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$DF883A05-D101-4A63-BF29-8F0B6004B04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$55D5B0C8-30E2-489E-A84B-A708D4DE49B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4298e2b9c3437d4a13acae5d4a872cd59ca3e014","datavalue":{"value":"5168559","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$66DD7249-A3D2-4635-8B46-B023B37D7C6B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4671352a659f914791d87cc8cc9bcb51313c06d","datavalue":{"value":"public-key cryptosystems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2370640$AD8D83DD-BC36-4731-B007-2BC1698C3F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6173606706b04932375fea9863120ddfa8f17e87","datavalue":{"value":"Lucas sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2370640$441ACE0A-DA3A-4E9C-B253-0D76A5043510","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2ca009dee2ffc0bac9a2c51660d5898dbd9ebb","datavalue":{"value":"quadratic fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q2370640$E062D862-BB87-40BB-BED8-6EE44B7D390F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cf658ad7ef7d6672e491794e6a4eead83097329a","datavalue":{"value":{"entity-type":"item","numeric-id":591958,"id":"Q591958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$B508A6E1-056B-4EB4-96F2-EC74E17B29FE","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$05EBC5BE-2A3D-4F06-B4C5-1B1FB1D713A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"77b5d4e751e696db2bc149bddaacfc531ca2c6e0","datavalue":{"value":"https://doi.org/10.1016/j.ffa.2006.05.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q2370640$9160959F-DDB7-4C36-BD92-DC0735959A84","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"034008734a7d8f660e8f336979595c37b28b21c5","datavalue":{"value":"W2008990579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$67042B9F-BB6A-4D4A-8D65-9007A74E6878","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40e06d5e16249040cb60e2ed1ea0c371fdd1dc6b","datavalue":{"value":{"entity-type":"item","numeric-id":3907627,"id":"Q3907627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$3A616BE9-C9DB-4BBD-8597-5DE24A1670DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"077b982c4221e66835b521f4bc80d724b08330ac","datavalue":{"value":{"entity-type":"item","numeric-id":4343411,"id":"Q4343411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$6956AB8C-7397-4A30-8E99-3B131DB913A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3d5be68ac2d16be0d3a5b9bd1ea2ca32f43532e","datavalue":{"value":{"entity-type":"item","numeric-id":4412805,"id":"Q4412805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$A8EF192A-C722-4FF8-AE2C-DFB36985CF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f01b47d3570cdbd01a25f3ea583448a6eb0c89d","datavalue":{"value":{"entity-type":"item","numeric-id":2876895,"id":"Q2876895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$D5DFE8DD-828E-4EE5-9223-D907C734A84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"444924ce7d7a8cdb382afa6836d2aea91bb2e725","datavalue":{"value":{"entity-type":"item","numeric-id":1601824,"id":"Q1601824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$BBD628A2-CB5F-4750-9320-82AAB727BD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6275149b34612c9823486f6bd17606110f754496","datavalue":{"value":{"entity-type":"item","numeric-id":4035724,"id":"Q4035724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$5F738B7B-3FE1-4189-8984-9DDCEED68409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab5eefdbbfafd3f01407f518b22bc797406b571b","datavalue":{"value":{"entity-type":"item","numeric-id":673987,"id":"Q673987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$5472A178-E472-44F9-AC9C-26BD7F38E67C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62284e3bb3374e4ff1f2f17f4d2dafc9025b1a2f","datavalue":{"value":{"entity-type":"item","numeric-id":4536791,"id":"Q4536791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$57FC75CA-3B21-49C6-9596-394EC5B51953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2111aabd21a2d955efb3251ee59917d523669906","datavalue":{"value":{"entity-type":"item","numeric-id":4250764,"id":"Q4250764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$DF58F0BE-9C1D-4142-A920-A7BB9063CDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b300651ebad30ef83012b699d9e53bdeead59d7b","datavalue":{"value":{"entity-type":"item","numeric-id":4342470,"id":"Q4342470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$D650A066-2381-4282-ACC6-09849F628169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c619a2e3ab1ab77110995c49c95e5c84936d89c8","datavalue":{"value":{"entity-type":"item","numeric-id":3953831,"id":"Q3953831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2370640$77A892E4-99D8-4454-BCAB-85897DAF0B78","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e876f54444ad54bcd81e1119bd12fac31111208","datavalue":{"value":"10.1016/J.FFA.2006.05.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2370640$FD60D22F-ED80-4353-8146-155143C7F6A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3aab7cb707e209319607c11ee0496385b69ecb2d","datavalue":{"value":{"entity-type":"item","numeric-id":1976266,"id":"Q1976266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0600b56bdfead488d7cdc0161f66ae816c14cb21","datavalue":{"value":{"amount":"+0.8199809193611145","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2370640$8FBEA2C5-0CC6-423D-918E-E2AD61864091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0db43faac02a78a384bb1ec0d9a903d42318ad53","datavalue":{"value":{"entity-type":"item","numeric-id":2789259,"id":"Q2789259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb1f44148bb7a13c8dae62bf58f6dc125636bfb6","datavalue":{"value":{"amount":"+0.8127729296684265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2370640$7E90C6B7-3C6E-455C-8AE6-9167AB5A589B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a10532d2d56164a27332584d33b4e418986bb00a","datavalue":{"value":{"entity-type":"item","numeric-id":2762761,"id":"Q2762761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d62268f1a627772d1cff3796d62812b8387d560","datavalue":{"value":{"amount":"+0.7856363654136658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2370640$1865E5A4-F9FC-4855-B194-8DF6244201ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b484a7a57de36b83892ae10bdbe303bd9940fd19","datavalue":{"value":{"entity-type":"item","numeric-id":3540038,"id":"Q3540038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d62268f1a627772d1cff3796d62812b8387d560","datavalue":{"value":{"amount":"+0.7856363654136658","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2370640$415135A3-FC0B-428B-AAA0-ED0F6B5221EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a684a2f985adc3847f52861ae76fd655efd8bee4","datavalue":{"value":{"entity-type":"item","numeric-id":954438,"id":"Q954438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d65e680b17b65deb741c46684067b79d968f73fe","datavalue":{"value":{"amount":"+0.7844703197479248","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2370640$9A257272-EA80-49B4-AA9E-0BAB66473BB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2370640","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2370640"}}}}}