{"entities":{"Q685709":{"pageid":687558,"ns":120,"title":"Item:Q685709","lastrevid":63462456,"modified":"2026-04-11T13:20:02Z","type":"item","id":"Q685709","labels":{"en":{"language":"en","value":"Efficient and optimal exponentiation in finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 423594"}},"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":"Q685709$779BF5E3-0CAA-4B47-85C2-B6969607C4D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c510c89083aafdbccf3d9c3fd553f8f9bdd700e","datavalue":{"value":{"text":"Efficient and optimal exponentiation in finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685709$F5A0B903-9EA4-4BA2-B2E9-F650257C11C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"271a7b913611c9773f8dd7a9a9890e3571941aeb","datavalue":{"value":"0788.68074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$91915017-C04C-40F3-8D33-C41C3747AD16","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da7c2069b025892a3d2be3edbd61db62bf0fa351","datavalue":{"value":"10.1007/BF01212964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$8D8EDBF6-3AB2-402F-AF91-A6F50C2E9D9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7429c710692d5d0c38830d08277242d2066f38db","datavalue":{"value":{"entity-type":"item","numeric-id":165879,"id":"Q165879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$CF0DCEC3-4D77-4711-BEF8-06ABCCC429F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$AB88EBA0-232B-40A6-BDCA-F7D258DAF186","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9ee486378a5fb0f84338329fe78e00d0957904b","datavalue":{"value":{"time":"+1993-10-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685709$2DD98122-0833-4961-814D-D7FB9263691C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7071ab0431f3ae1aa9e5b6173c1b02c4b9b6cd7d","datavalue":{"value":"The problem of the efficient exponentiation in a finite field \\(\\mathbb F_{q^ n}\\) of order \\(q^ n\\) by arithmetic circuits over \\(\\mathbb F_{q^ n}\\) is considered, where \\(q\\) is a prime power and \\(n \\geq 1\\). The basic assumption of the computational model is that \\(q\\)-th powers can be computed for free. An algorithm using size about \\(n/ \\log_ qn\\) and depth about \\(\\log_ 2n\\) is presented. For \\(q=2\\) this is a slight improvement on a result of \\textit{D. R. Stinson} [SIAM J. Comput. 19, 711--717 (1990; Zbl 0697.68049)]. A counting argument shows that the size cannot be improved below essentially \\({1 \\over 3}n/ \\log_ qn\\). A detailed study of the depth is carried out by using addition chains with free multiples of \\(q\\).   Note: the references Jedwab and Mitchell (1989) [J. Jedwab and C. J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation, Electron. Lett. 25, 1171--1172 (1989; Zbl 0709.94699)] and Takagi et al. (1985) [N. Takagi et al., IEEE Trans. Comput. 34, 789--796 (1985; Zbl 0565.94021)] occur in the text, e.g. on p. 362, but they are not included in the bibliography, and so the reader cannot follow them up.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685709$15717640-14A9-4E02-A0FA-84CB467143A6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd80e9ade304e6b9b43fd50d0c3436276c3c217e","datavalue":{"value":"68M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$D9894CA7-76D6-48D1-B3F3-DC6117211066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$48D031A2-0943-433B-984F-4DC01350C6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$CC26837D-5F8E-4B45-849A-109CBD4C51BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$5D7B4B77-B900-44C5-8862-3698C0A93F66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d8ab3d6028aaafb9d6a7dbf8f6aa9afcbe2663b","datavalue":{"value":"423594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685709$EE96C10C-DB37-48B4-BAB3-62FC32656AD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6de652fb348ed6b22ea1dda6b5c7808e39c7ad68","datavalue":{"value":"efficient exponentiation","type":"string"},"datatype":"string"},"type":"statement","id":"Q685709$AEDEA8E5-8517-4B35-BAF4-8A8947AAFE6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q685709$7D5C132A-E8D7-47F8-86CF-2A669F4AE9F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916f2a5439f7e4b36d4fe8bc533c45ce2dc6fc9f","datavalue":{"value":"arithmetic circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q685709$1CBF7E4F-6F89-402D-B34C-112066AAD97E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"129770c7be84bc85a0534a5160c0f3ed6cbe5036","datavalue":{"value":{"entity-type":"item","numeric-id":165897,"id":"Q165897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$40DBB204-9693-4425-A2E9-99A9FE30DA0D","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":"Q685709$DC7D53B3-9940-4177-B2CD-7AFF3FBE5826","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc22b47c42ba322f4bd830111391b026b40a348","datavalue":{"value":{"entity-type":"item","numeric-id":1108812,"id":"Q1108812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$52191E21-24ED-419C-8D93-9D91AC454803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c163690e3ab68671bf083b2ff0b11eeff1a55e5e","datavalue":{"value":{"entity-type":"item","numeric-id":3798223,"id":"Q3798223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$4EB04C9E-09D1-45FC-A514-89F5DEFB0445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e873dc563373f6904d1fc7069f448c499a62f8f","datavalue":{"value":{"entity-type":"item","numeric-id":3776614,"id":"Q3776614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$9DC57C4B-AE8C-4039-B5EA-9ACDD1E93690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2668ba8fe68432f832105b211bd034668dbbcf68","datavalue":{"value":{"entity-type":"item","numeric-id":2638778,"id":"Q2638778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$0F7C7BF5-234E-46BA-9A21-E98E1DB28B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aba29627153c954a306e0b06e39afe7198273c33","datavalue":{"value":{"entity-type":"item","numeric-id":1186580,"id":"Q1186580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$3F0F5D75-F020-466F-9CED-D4879B09A7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b93a42633d7b69cb4ae25e08e07a27023648d8f","datavalue":{"value":{"entity-type":"item","numeric-id":2639102,"id":"Q2639102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$A2B38D59-0BEF-4B51-ADB6-2A3C7D7B3881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eafcc383877a99afdfab9a5d60ad413be3c12662","datavalue":{"value":{"entity-type":"item","numeric-id":2639101,"id":"Q2639101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$37B2A608-B76B-4137-9B5F-2DAC9996AC75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bb7ab87b4e68186afad4debc8887d4af7c7918a","datavalue":{"value":{"entity-type":"item","numeric-id":1111375,"id":"Q1111375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$A1B5981E-F77C-45C6-9125-625C3C78D56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0ff209a8c00e6853b2c43b2e31810805788f0","datavalue":{"value":{"entity-type":"item","numeric-id":3935355,"id":"Q3935355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$7027067F-C6DC-4262-8969-F48BCBB1EB48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"122f743327b0b23e5450e3f431ca45f2db2ee21a","datavalue":{"value":{"entity-type":"item","numeric-id":3474890,"id":"Q3474890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$A6F17608-7693-4E73-B71E-C66D703996E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f61d49b59d6ddddd441b0e63d321123095ffdd4","datavalue":{"value":{"entity-type":"item","numeric-id":3682399,"id":"Q3682399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685709$F6E98508-D589-4621-8CEF-DAD190A47E12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08ca6f857b8163d2c83ab2936328a00277e0918c","datavalue":{"value":{"entity-type":"item","numeric-id":1186580,"id":"Q1186580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4e5c9751d22b2ecaff4bd2e66cd84d74e903b1e","datavalue":{"value":{"amount":"+0.8371193408966064","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":"Q685709$D7F396F0-AAAD-448B-9F27-D8CC12F172B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"740f4608229bdd1232087d0e5c9d5cc84a1c1d90","datavalue":{"value":{"entity-type":"item","numeric-id":4226694,"id":"Q4226694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0f664bddcfba256765716205c73582ba9e226b0","datavalue":{"value":{"amount":"+0.8345630168914795","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":"Q685709$5912D838-FC6F-4434-89C4-5998669C9BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff6e114fe5348cfb53e22e3f9821af5abc38ec2a","datavalue":{"value":{"entity-type":"item","numeric-id":4813594,"id":"Q4813594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f36376558682962cc38340168f207efe046a59a","datavalue":{"value":{"amount":"+0.8119431734085083","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":"Q685709$9467467C-4161-4252-BDCB-F970092B59C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"413f1f223dd20bd1866022413c7aa0f91c1f9057","datavalue":{"value":{"entity-type":"item","numeric-id":4470462,"id":"Q4470462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f16299929af8225c7ff7d696794924d4f08c4874","datavalue":{"value":{"amount":"+0.8113126158714294","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":"Q685709$73A249BE-BA03-468B-B7BB-43A4919B9900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcac14a56523a19c0e9f8e6ea39695831b285c52","datavalue":{"value":{"entity-type":"item","numeric-id":3601777,"id":"Q3601777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcb59cb425b865c21eddc1234c3db5f43e62fe0d","datavalue":{"value":{"amount":"+0.8067925572395325","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":"Q685709$381D54B2-7418-4594-A45E-AACD77D9A8E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient and optimal exponentiation in finite fields","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_and_optimal_exponentiation_in_finite_fields"}}}}}