{"entities":{"Q1210295":{"pageid":1221044,"ns":120,"title":"Item:Q1210295","lastrevid":69906312,"modified":"2026-04-13T11:08:22Z","type":"item","id":"Q1210295","labels":{"en":{"language":"en","value":"The computational efficacy of finite-field arithmetic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 178039"}},"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":"Q1210295$FA23D5AF-E0C8-4665-AD45-B4DA742BBA95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"932b5012fe27a4bcda9b9185bd256894f1aea573","datavalue":{"value":{"text":"The computational efficacy of finite-field arithmetic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1210295$86609C27-9921-46D5-9D01-3890E4794CB8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94012e21f0a571f58c9a739b2e93b864b39feeba","datavalue":{"value":"0774.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$8728AC22-79F7-4ACF-925B-413F149D24D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"965a6987384124da31388e623b8964793f1fa1dc","datavalue":{"value":"10.1016/0304-3975(93)90022-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$35541D6D-A217-4360-884F-8D77F01AA4A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cd957eea0f03b8164e096cb6d211e5546c1a319","datavalue":{"value":{"entity-type":"item","numeric-id":1186609,"id":"Q1186609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$D2CCFE5B-32B2-4165-A351-FE6E5359AD01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"84f8c73d1d1e1f0a648e645ee4defd36dced9cfb","datavalue":{"value":{"entity-type":"item","numeric-id":633625,"id":"Q633625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$595FFB5E-64D9-45F2-926C-F31CEB4F22AA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$8C481781-ABB6-4883-874C-17849A8E321C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"03c5731f5d94178498d0ad4e21aec8fa89a18c16","datavalue":{"value":{"time":"+1993-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1210295$12579018-F6D3-447F-97F2-68C9E523F5F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"62a68fea2988dbc0c06af26a2259392342273312","datavalue":{"value":"The computational power of finite field arithmetic operations in terms of Boolean operations is investigated. A ``good'' representation of the finite field is one where the arithmetic has polynomial-size Boolean circuits. It is shown that finite-field arithmetic is as powerful as Boolean operations of polynomial size if and only if, in any good representation of field elements as bit strings, there is a polynomial size arithmetic circuit that computes from a field element its representation and vice-versa. A representation with this property is referred to as a strong representation. It is shown that if a strong representation exists then all representations are strong. Consequently the question of arithmetic compared to Boolean operations is reduced to whether a standard representation is strong. This reduces to the case of prime fields for which the standard representation of integers modulo \\(p\\) is taken. Define the function  \\[ f_ p(x)=\\left( {{x-x^ p} \\over p}\\right) \\bmod p \\]  where the arithmetic in parenthesis is integer arithmetic. It is shown the efficacy of arithmetic in finite fields is reduced to the arithmetic complexity of \\(f_ p\\). The function \\(f_ p\\) is reduced to the pair of functions \\(g_ p=\\sum_ 1^{p-1} x^ k/k\\) on \\(F_ p\\) and \\(m_ p\\) on \\(F_{p^ 2}\\), where \\(m_ p\\) is the \\(\\mod p\\) function. It is shown that \\(f_ p\\) has polynomial-size arithmetic circuits if and only if \\(g_ p\\) and \\(m_ p\\) have polynomial-size circuits. A connection between \\(f_ p\\) and \\(m_ p\\) is made with the Bernoulli polynomials.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210295$1AFC550A-5820-46D6-9444-AF2A51229F14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$AD6843A6-BA08-41AD-A408-2CC8C83E06FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$FB1D873C-67CC-461B-ADC3-5907C30129C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49677766e22a11802b3e4977c9057bac62508c51","datavalue":{"value":"11T99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$D3FC0DCC-FCBF-44C2-B5BE-7AAE86002906","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3c4253e2943febea9fb094a6aae6509ef407e2b","datavalue":{"value":"178039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$41D03F98-D5D0-49A8-BEB9-BA698C99D021","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3711b386902559bb22bf67091b7eca92012716a","datavalue":{"value":"finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210295$454D6328-17BF-4832-9E51-5965F10FA666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210295$5505D4E2-8597-4815-92D6-DA930B463A85","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$22D6422C-4C8C-4B7D-8470-B0635397B7DE","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":"Q1210295$1FD79E3D-451E-4152-8543-C234A240020E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9b1e9f4e02d67ed26a436ba01caa92c23e9bcb0","datavalue":{"value":{"entity-type":"item","numeric-id":1186610,"id":"Q1186610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$6A3A5A7C-0E7E-40D7-B957-D31B15821B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d398a8777c24ef2ba1a066089079161ece82c16","datavalue":{"value":{"entity-type":"item","numeric-id":3887397,"id":"Q3887397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$D95FDE38-57B7-4477-84C3-733699073B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a64e77a630b8af1c46f06b67a254f5adb7285ae3","datavalue":{"value":{"entity-type":"item","numeric-id":5577214,"id":"Q5577214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$7C46D51E-6279-417D-ACE6-5A32423BE70C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02be8e138861a707097d1b5ce89d199d18f0de98","datavalue":{"value":{"entity-type":"item","numeric-id":5792522,"id":"Q5792522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$E7F02823-250D-4631-AC40-D31CE18AF5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe550f3549cdf995505ee8803ca92194c9d942d","datavalue":{"value":{"entity-type":"item","numeric-id":5328221,"id":"Q5328221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$74855FA4-3FAE-47E9-9AE1-FB4A2150BC55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb8279b28c4358ee2866968595de568d8d1e7ba1","datavalue":{"value":{"entity-type":"item","numeric-id":4177670,"id":"Q4177670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$D2359023-A2B9-477B-88B8-DCA6E436E121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04dc3a748ca29fdc38f589835e541bad8a5023ad","datavalue":{"value":{"entity-type":"item","numeric-id":3216750,"id":"Q3216750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$DFEF3775-2E81-4AC9-899E-4EF3E20B4F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c551822e86c0407675a9f9f7fcb1ddd9dd22246b","datavalue":{"value":{"entity-type":"item","numeric-id":3726006,"id":"Q3726006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$42EA0E44-2287-4033-B72B-451B0981F1D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ffb7c4897464eade24b984dc253233d6968fb77","datavalue":{"value":{"entity-type":"item","numeric-id":1095871,"id":"Q1095871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210295$AE631248-8B15-4D73-8C0B-BF49277A591E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c686b1a7a4daaedc1fa0d2221a9dcfe9dad418ca","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90022-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q1210295$6F143601-BC47-45B3-A1A7-CEF9CE55DE30","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a19f232412037e78e72f47fda0e6262cc6728651","datavalue":{"value":"W2032013893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210295$8D90D432-7A9D-4C48-8069-878B8FDC7209","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd0602ea129231474b2099b4452e8e0d4fd8798e","datavalue":{"value":{"entity-type":"item","numeric-id":378003,"id":"Q378003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32419b1aebc335e5d1e2120dc7c13e7063b6dfeb","datavalue":{"value":{"amount":"+0.8373916745185852","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":"Q1210295$48FE693C-0E5C-484E-8131-F757F10DE206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d19ff24991d349648ec003437c008dbf692af39d","datavalue":{"value":{"entity-type":"item","numeric-id":1383509,"id":"Q1383509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3aca1a7ead00242531f45987c412477c980ec1a","datavalue":{"value":{"amount":"+0.8104583621025085","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":"Q1210295$165865AE-0A21-4BB6-BE99-13AA8DC3F300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9711bfb8916802120679f4287c5ebe05c73312f9","datavalue":{"value":{"entity-type":"item","numeric-id":910432,"id":"Q910432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6157ee558f30dee17f6a8adc8ca61350fa9c47ea","datavalue":{"value":{"amount":"+0.8024583458900452","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":"Q1210295$262DBB0F-8606-4E83-BD28-A36EFD6C2BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"811da7f8cd6aadf0966019c21222deab3ed1e722","datavalue":{"value":{"entity-type":"item","numeric-id":2998297,"id":"Q2998297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1ac582d5e92a536bf33f6d40d39dd203f077704","datavalue":{"value":{"amount":"+0.7928109765052795","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":"Q1210295$09D2371B-7572-4932-A8AF-713258745077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e44242e3da306273ad0a13a61c312bc7f8b6e5e","datavalue":{"value":{"entity-type":"item","numeric-id":2639101,"id":"Q2639101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"472da2715eb07747f0e231347e79e33c6d399a7e","datavalue":{"value":{"amount":"+0.7837412357330322","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":"Q1210295$44B318AD-50DA-43BB-B053-51629487A95C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The computational efficacy of finite-field arithmetic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_computational_efficacy_of_finite-field_arithmetic"}}}}}