{"entities":{"Q725955":{"pageid":727804,"ns":120,"title":"Item:Q725955","lastrevid":63864231,"modified":"2026-04-11T16:03:47Z","type":"item","id":"Q725955","labels":{"en":{"language":"en","value":"The number of Boolean functions with multiplicative complexity 2"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6912653"}},"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":"Q725955$13A6DB2E-DB9E-4C92-B866-0372D5BD56B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"832c77f3fcdcec6dbf86664ac4b8bccde1c9e79e","datavalue":{"value":{"text":"The number of Boolean functions with multiplicative complexity 2","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q725955$C5FFF1B4-394B-42BE-BD04-91413B4AE589","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8fba7d9451a66f80dc71aa01319628f6bb464fcd","datavalue":{"value":"1407.94195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725955$4EDCAB7A-56F6-4847-944A-B3FB79BD49E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"395f03376b4950bff4f5170903e9d60f6fd68b5c","datavalue":{"value":"10.1504/IJICOT.2017.10005826","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725955$F59FDF64-4343-462A-B3B3-58E8F4734679","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"409d1f9a4834ec23dc9b67676ce40a7d95cdf9bd","datavalue":{"value":{"entity-type":"item","numeric-id":725953,"id":"Q725953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725955$DB7C5A47-45BE-40EB-8D10-4AABE691288F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"542d667d2a651fb9b5730c34f96a81be507a6c0b","datavalue":{"value":{"entity-type":"item","numeric-id":285240,"id":"Q285240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725955$CA6AA474-09AD-4BAE-9243-3F62BDAD2FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50909f2fb9205ecb7eab87682e79b3e11e26d123","datavalue":{"value":{"entity-type":"item","numeric-id":725954,"id":"Q725954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725955$4FFA1960-67BA-4014-AF2D-E2C609DFD9EF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3e9e59970b6096537ac135b2cc16d1c02a64695","datavalue":{"value":{"entity-type":"item","numeric-id":274526,"id":"Q274526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725955$B6FD7D3D-9BBA-46AB-9AB8-7C6204715919","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a9aa22cb8a96ecb8781adebec8cb26e1601a98e8","datavalue":{"value":{"time":"+2018-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q725955$80D99B9F-03D2-4172-B6B6-B4D8CB8C1576","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11b3c90ddfb8ead8aa183c3e37294ae3a86f89b0","datavalue":{"value":"Summary: Multiplicative complexity is a complexity measure defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT). Implementations of ciphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multiparty computation and zero-knowledge proofs. \\textit{M. J. Fischer} and \\textit{R. Peralta} [``Counting Predicates of Conjunctive Complexity One'', Yale TR-1222, (2002)] computed the number of \\(n\\)-variable Boolean functions with multiplicative complexity 1. In this paper, we study Boolean functions that can be constructed with two AND gates. By characterising the structure of these functions in terms of affine equivalence relations, we provide a closed-form formula for the number of Boolean functions with multiplicative complexity 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q725955$33B2515A-AEA7-488D-A1E6-2AE476AA8987","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725955$14A1395F-F81F-435F-91CC-C736CA921295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725955$B705669B-0C24-4F83-805D-CBF3E5E3E0E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"536d6a7f91ebd6f4b5f8f6e2008dafdb1df2e8ab","datavalue":{"value":"6912653","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725955$FCCED8CE-7DCF-4325-8DEC-8B508CCDF05E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21bca372fe1e15bdf321eb5f06a052d961f46e3a","datavalue":{"value":"affine transformations","type":"string"},"datatype":"string"},"type":"statement","id":"Q725955$ADA117D7-C10E-4AC6-B094-E4B9D78433A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q725955$81C6D5AF-8E99-4717-8634-4736028A0B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f0cb341ca7876bc8468eee4ea8e9008984980e7","datavalue":{"value":"circuit complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q725955$E7357E5D-0D24-428C-87F4-57DB001E8E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q725955$C4628CB4-1E76-46EA-8385-8C2FF78C9851","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":"Q725955$DCC7FD16-733E-4442-BF90-C869D56B2233","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a8a3135f3c3b6bc64df4282ef560096cc2260b9","datavalue":{"value":{"entity-type":"item","numeric-id":314127,"id":"Q314127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"595834bde450e3e3e3d483eca7b9e56842eff183","datavalue":{"value":{"amount":"+0.8942732810974121","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":"Q725955$A688F4B1-7EE0-4DFF-8786-6DADD1448693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"060fb58f81084329e2689218a44a82b1e2e43f19","datavalue":{"value":{"entity-type":"item","numeric-id":2040305,"id":"Q2040305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fc90b83561ea8578450bd4c49d545b4ad91b404","datavalue":{"value":{"amount":"+0.8838452100753784","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":"Q725955$CAFAC276-D161-4721-ACE4-85BB1BB74C1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa2a7b89cfd5dfc7223bbdec7f8deb35281db00f","datavalue":{"value":{"entity-type":"item","numeric-id":2354498,"id":"Q2354498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bea6565e65b803a6b1ca4edc41cc17e15ed44d02","datavalue":{"value":{"amount":"+0.878714919090271","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":"Q725955$3C253556-8970-488C-8BB8-FE418D158EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5f8d988279c11007471e3095dc6655756ea195f","datavalue":{"value":{"entity-type":"item","numeric-id":4976406,"id":"Q4976406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70946fe68d079e8262f350176a21aea239f3bb1f","datavalue":{"value":{"amount":"+0.8779274821281433","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":"Q725955$E61D1EB7-0CED-48E0-899F-B9B308162958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8da2a1b07c5c2d4b5fb3eac34a956d511f891090","datavalue":{"value":{"entity-type":"item","numeric-id":1978699,"id":"Q1978699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7902ffd31a51022a9b3535fd89c406a2f874acd6","datavalue":{"value":{"amount":"+0.8732420802116394","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":"Q725955$5DF8DF93-6065-49C0-A23A-4383D1422355","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The number of Boolean functions with multiplicative complexity 2","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_number_of_Boolean_functions_with_multiplicative_complexity_2"}}}}}