बूलीय फलन: Difference between revisions
From Vigyanwiki
(TEXT) |
(TEXT) |
||
| Line 1: | Line 1: | ||
{{Short description|Function returning one of only two values}} | {{Short description|Function returning one of only two values}} | ||
[[File:BinaryDecisionTree.svg|thumb|एक द्विअंगी निर्णय आरेख और एक त्रिगुट बूलियन | [[File:BinaryDecisionTree.svg|thumb|एक द्विअंगी निर्णय आरेख और एक त्रिगुट बूलियन प्रकार्य की सत्यमान प्रकार्य]]गणित में, बूलियन प्रकार्य एक प्रकार्य (गणित) होता है जिसका प्रकार्य और परिणाम का तर्क दो-तत्व सम्मुच्चय (सामान्यतः {true, false}, {0,1} या {-1,1}) से मान लेता है।<ref>{{Cite web|title=Boolean function - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/wiki/Boolean_function|access-date=2021-05-03|website=encyclopediaofmath.org}}</ref><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Boolean Function|url=https://mathworld.wolfram.com/BooleanFunction.html|access-date=2021-05-03|website=mathworld.wolfram.com|language=en}}</ref> वैकल्पिक नाम स्विचन प्रकार्य हैं, विशेष रूप से पुराने [[कंप्यूटर विज्ञान]] साहित्य में उपयोग किए जाते हैं,<ref>{{Cite web|title=switching function|url=https://encyclopedia2.thefreedictionary.com/switching+function|access-date=2021-05-03|website=TheFreeDictionary.com}}</ref><ref>{{Cite journal|last=Davies|first=D. W.|date=December 1957|title=Switching Functions of Three Variables|url=https://ieeexplore.ieee.org/document/5222038|journal=IRE Transactions on Electronic Computers|volume=EC-6|issue=4|pages=265–275|doi=10.1109/TEC.1957.5222038|issn=0367-9950}}</ref> और सत्यमान प्रकार्य (या तार्किक कार्य) और [[तर्क]] में प्रयुक्त किए जाते हैं। बूलियन प्रकार्य [[बूलियन बीजगणित]] और [[स्विचिंग सिद्धांत|स्विचन सिद्धांत]] का विषय हैं।<ref>{{Citation|last=McCluskey|first=Edward J.|title=Switching theory|date=2003-01-01|url=https://dl.acm.org/doi/10.5555/1074100.1074844|encyclopedia=Encyclopedia of Computer Science|pages=1727–1731|place=GBR|publisher=John Wiley and Sons Ltd.|doi=|isbn=978-0-470-86412-8|access-date=2021-05-03}}</ref> | ||
एक बूलियन | एक बूलियन प्रकार्य <math>f:\{0,1\}^k \to \{0,1\}</math> रूप लेता है, जहाँ <math>\{0,1\}</math> [[बूलियन डोमेन|बूलियन कार्यक्षेत्र]] के रूप में जाना जाता है और <math>k</math> एक गैर-ऋणात्मक पूर्णांक है जिसे प्रकार्य की [[arity|अरिटी]] कहा जाता है। उस स्तिथि में जहां <math>k=0</math>, प्रकार्य का एक स्थिर तत्व <math>\{0,1\}</math> है। एकाधिक निष्पाद <math>f:\{0,1\}^k \to \{0,1\}^m</math> के साथ <math>m>1</math> के साथ बूलियन प्रकार्य सदिश या सदिश-मूल्यवान बूलियन प्रकार्य (सममित [[क्रिप्टोग्राफी|कूटलेखन]] में एक [[एस-बॉक्स|S-बक्स]]) है।<ref name=":2" /> | ||
वहाँ <math>2^{2^k}</math> विभिन्न बूलियन | वहाँ <math>2^{2^k}</math> विभिन्न बूलियन प्रकार्यों के साथ <math>k</math> तर्क हैं; विभिन्न सत्यमान प्रकार्य की संख्या के बराबर <math>2^k</math> प्रविष्टियाँ हैं। | ||
प्रत्येक <math>k</math>-एरी बूलियन | प्रत्येक <math>k</math>-एरी बूलियन प्रकार्य को प्रस्ताविक सूत्र <math>k</math> चर <math>x_1,...,x_k</math> के रूप में व्यक्त किया जा सकता है, और दो तर्कवाक्य सूत्र तार्किक तुल्यता हैं यदि और केवल यदि वे एक ही बूलियन प्रकार्य को व्यक्त करते हैं। | ||
== उदाहरण == | == उदाहरण == | ||
[[File:Logical connectives Hasse diagram.svg|alt=Diagram displaying the sixteen binary Boolean functions|thumb|सोलह युग्मक बूलियन | [[File:Logical connectives Hasse diagram.svg|alt=Diagram displaying the sixteen binary Boolean functions|thumb|सोलह युग्मक बूलियन प्रकार्य]] | ||
{{See also|सत्यमान सारणी}} | {{See also|सत्यमान सारणी}} | ||
प्रारंभिक सममित बूलियन | प्रारंभिक सममित बूलियन प्रकार्य ([[तार्किक संयोजक]] या तर्क द्वार) हैं: | ||
* NOT, प्रतिवाद अथवा [[तार्किक पूरक]] - जो एक निविष्टि प्राप्त करता है और उस निविष्टि के गलत होने पर सही हो जाता है (नहीं) | * NOT, प्रतिवाद अथवा [[तार्किक पूरक]] - जो एक निविष्टि प्राप्त करता है और उस निविष्टि के गलत होने पर सही हो जाता है (नहीं) | ||
| Line 25: | Line 25: | ||
*NOR अथवा तार्किक NOR - सत्य जब कोई भी निविष्टि सत्य नहीं है (अन्यतर) | *NOR अथवा तार्किक NOR - सत्य जब कोई भी निविष्टि सत्य नहीं है (अन्यतर) | ||
*XNOR अथवा [[तार्किक समानता]] - सच है जब दोनों निविष्टि समान (बराबर) हैं | *XNOR अथवा [[तार्किक समानता]] - सच है जब दोनों निविष्टि समान (बराबर) हैं | ||
अधिक जटिल | अधिक जटिल प्रकार्य का एक उदाहरण बहुसंख्यक प्रकार्य (विषम संख्या में निविष्टि) है। | ||
== प्रतिनिधित्व == | == प्रतिनिधित्व == | ||
[[File:Three input Boolean circuit.jpg|thumb|बूलियन | [[File:Three input Boolean circuit.jpg|thumb|बूलियन प्रकार्य एक [[बूलियन सर्किट|बूलियन परिपथ]] के रूप में दर्शाया गया है]]एक बूलियन प्रकार्य को विभिन्न तरीकों से निर्दिष्ट किया जा सकता है: | ||
* सत्यमान | * सत्यमान प्रकार्य: तर्कों के सभी संभावित मूल्यों के लिए इसके मूल्य को स्पष्ट रूप से सूचीबद्ध करना | ||
** मार्क्वांड आरेख: दो-आयामी संजाल में व्यवस्थित सत्यमान | ** मार्क्वांड आरेख: दो-आयामी संजाल में व्यवस्थित सत्यमान प्रकार्य मान (कर्नाघ मानचित्र में उपयोग किया जाता है) | ||
**द्विआधारी निर्णय आरेख, एक द्विआधारी वृक्ष के तल पर सत्यमान | **द्विआधारी निर्णय आरेख, एक द्विआधारी वृक्ष के तल पर सत्यमान प्रकार्य मानों को सूचीबद्ध करता है | ||
**[[वेन आरेख]], समतल के क्षेत्रों के रंग के रूप में सत्यमान | **[[वेन आरेख]], समतल के क्षेत्रों के रंग के रूप में सत्यमान प्रकार्य मानों का चित्रण | ||
बीजगणितीय रूप से, प्रारंभिक बूलियन कार्यों का उपयोग करके एक प्रस्तावक सूत्र के रूप में: | बीजगणितीय रूप से, प्रारंभिक बूलियन कार्यों का उपयोग करके एक प्रस्तावक सूत्र के रूप में: | ||
| Line 39: | Line 39: | ||
* वियोगात्मक सामान्य रूप, तर्कों और उनके पूरक के ANDs के OR के रूप में | * वियोगात्मक सामान्य रूप, तर्कों और उनके पूरक के ANDs के OR के रूप में | ||
* [[संयोजक सामान्य रूप]], तर्कों और उनके पूरक के ORs के AND के रूप में | * [[संयोजक सामान्य रूप]], तर्कों और उनके पूरक के ORs के AND के रूप में | ||
*[[कैननिकल सामान्य रूप|विहित सामान्य रूप]], एक मानकीकृत सूत्र जो विशिष्ट रूप से | *[[कैननिकल सामान्य रूप|विहित सामान्य रूप]], एक मानकीकृत सूत्र जो विशिष्ट रूप से प्रकार्य की पहचान करता है: | ||
**[[बीजगणितीय सामान्य रूप]] या झेगाल्किन बहुपद, तर्कों के ANDs के XOR के रूप में (कोई पूरक की अनुमति नहीं है) | **[[बीजगणितीय सामान्य रूप]] या झेगाल्किन बहुपद, तर्कों के ANDs के XOR के रूप में (कोई पूरक की अनुमति नहीं है) | ||
**पूर्ण (प्रामाणिक) वियोगात्मक सामान्य रूप, प्रत्येक तर्क या पूरक ([[minterms|गुणद]]) युक्त AND का OR | **पूर्ण (प्रामाणिक) वियोगात्मक सामान्य रूप, प्रत्येक तर्क या पूरक ([[minterms|गुणद]]) युक्त AND का OR | ||
**पूर्ण (प्रामाणिक) संयोजक सामान्य रूप, प्रत्येक तर्क या पूरक ([[maxterms|योपद]]) वाले ORs का AND | **पूर्ण (प्रामाणिक) संयोजक सामान्य रूप, प्रत्येक तर्क या पूरक ([[maxterms|योपद]]) वाले ORs का AND | ||
**[[ब्लेक विहित रूप]], | **[[ब्लेक विहित रूप]], प्रकार्य के सभी [[प्रधान शामिल है|प्रधान आपाद्य]] का OR | ||
बूलियन सूत्र को आरेख के रूप में भी प्रदर्शित किया जा सकता है: | बूलियन सूत्र को आरेख के रूप में भी प्रदर्शित किया जा सकता है: | ||
* [[प्रस्तावित निर्देशित विश्वकोश ग्राफ|प्रस्तावित निर्देशित विश्वकोश आरेख]] | * [[प्रस्तावित निर्देशित विश्वकोश ग्राफ|प्रस्तावित निर्देशित विश्वकोश आरेख]] | ||
**तर्क द्वार का अंकीय परिपथ (कंप्यूटर साइंस) रेखाचित्र, एक बूलियन परिपथ | **तर्क द्वार का अंकीय परिपथ (कंप्यूटर साइंस) रेखाचित्र, एक बूलियन परिपथ | ||
**[[और-पलटनेवाला ग्राफ|और-अंर्तवर्तक]] [[प्रस्तावित निर्देशित विश्वकोश ग्राफ|आरेख]], केवल AND और NOT का उपयोग करके | **[[और-पलटनेवाला ग्राफ|और-अंर्तवर्तक]] [[प्रस्तावित निर्देशित विश्वकोश ग्राफ|आरेख]], केवल AND और NOT का उपयोग करके | ||
इलेक्ट्रॉनिक परिपथ को अनुकूलित करने के लिए, बूलियन सूत्र क्विन-मैक्लुस्की कलन विधि या कर्णघ मानचित्र का उपयोग करके [[बूलियन कार्यों का न्यूनतमकरण|बूलियन | इलेक्ट्रॉनिक परिपथ को अनुकूलित करने के लिए, बूलियन सूत्र क्विन-मैक्लुस्की कलन विधि या कर्णघ मानचित्र का उपयोग करके [[बूलियन कार्यों का न्यूनतमकरण|बूलियन प्रकार्यों का न्यूनतमकरण]] हो सकता है। | ||
== विश्लेषण == | == विश्लेषण == | ||
| Line 56: | Line 56: | ||
=== गुण === | === गुण === | ||
एक बूलियन | एक बूलियन प्रकार्य में विभिन्न गुण हो सकते हैं:<ref name=":0">{{Cite web|title=Boolean functions — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html|access-date=2021-05-01|website=doc.sagemath.org}}</ref> | ||
* निरंतर कार्य: अपने तर्कों पर ध्यान दिए बिना हमेशा सत्य या हमेशा असत्य होता है। | * निरंतर कार्य: अपने तर्कों पर ध्यान दिए बिना हमेशा सत्य या हमेशा असत्य होता है। | ||
* एकदिष्ट | * एकदिष्ट प्रकार्य: तर्क मानों के प्रत्येक संयोजन के लिए, एक तर्क को असत्य से सत्य में बदलने से केवल निष्पाद को असत्य से सत्य पर स्विच करने का कारण बन सकता है न कि सत्य से असत्य में बदलने का कारण। एक प्रकार्य को एक निश्चित चर में [[अनएट फंक्शन|यूनेट प्रकार्य]] कहा जाता है यदि यह उस चर में परिवर्तन के संबंध में एकदिष्ट है। | ||
* रैखिकता: प्रत्येक चर के लिए, चर के मान को प्रतिवर्न करना या तो हमेशा सत्य मान में अंतर करता है या कभी भी अंतर नहीं करता है (एक समता | * रैखिकता: प्रत्येक चर के लिए, चर के मान को प्रतिवर्न करना या तो हमेशा सत्य मान में अंतर करता है या कभी भी अंतर नहीं करता है (एक समता प्रकार्य)। | ||
* [[सममित बूलियन फ़ंक्शन|सममित बूलियन | * [[सममित बूलियन फ़ंक्शन|सममित बूलियन प्रकार्य]]: मान इसके तर्कों के क्रम पर निर्भर नहीं करता है। | ||
* [[रीड-वन्स फंक्शन|रीड-वन्स | * [[रीड-वन्स फंक्शन|रीड-वन्स प्रकार्य]]: प्रत्येक चर के एक उदाहरण के साथ संयोजन, वियोजन और प्रतिवाद के साथ व्यक्त किया जा सकता है। | ||
*[[संतुलित बूलियन फ़ंक्शन|संतुलित बूलियन | *[[संतुलित बूलियन फ़ंक्शन|संतुलित बूलियन प्रकार्य]]: यदि इसकी सत्यमान सारणी में शून्य और एक की समान संख्या है। प्रकार्य का [[हैमिंग वजन|हैमिंग भार]] सत्यमान प्रकार्य में इकाइयों की संख्या है। | ||
* [[तुला समारोह|तुला | * [[तुला समारोह|तुला प्रकार्य]]: इसके व्युत्पन्न शब्द सभी संतुलित हैं (स्वसहसंबंध वर्णक्रम शून्य है) | ||
* m क्रम के लिए सहसंबंध उन्मुक्ति: यदि निष्पाद अधिकतम m तर्कों के सभी (रैखिक) संयोजनों के साथ असंबद्ध है | * m क्रम के लिए सहसंबंध उन्मुक्ति: यदि निष्पाद अधिकतम m तर्कों के सभी (रैखिक) संयोजनों के साथ असंबद्ध है | ||
* [[इवेसिव बूलियन फ़ंक्शन|अस्पष्ट बूलियन | * [[इवेसिव बूलियन फ़ंक्शन|अस्पष्ट बूलियन प्रकार्य]]: यदि प्रकार्य के मूल्यांकन के लिए सदैव सभी तर्कों के मान की आवश्यकता होती है | ||
*बूलियन | *बूलियन प्रकार्य एक शेफ़र प्रकार्य है यदि इसका उपयोग किसी भी स्वेच्छाचारी बूलियन प्रकार्य को बनाने (रचना द्वारा) करने के लिए किया जा सकता है ([[कार्यात्मक पूर्णता]] देखें) | ||
*किसी | *किसी प्रकार्य की बीजगणितीय घात उसके बीजगणितीय सामान्य रूप में उच्चतम क्रम के एकपदी का क्रम है | ||
[[सर्किट जटिलता|परिपथ जटिलता]] बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं। | [[सर्किट जटिलता|परिपथ जटिलता]] बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं। | ||
=== व्युत्पन्न कार्य === | === व्युत्पन्न कार्य === | ||
सकारात्मक और नकारात्मक शैनन सहगुणक ([[शैनन विस्तार]]) में बूल के विस्तार प्रमेय का उपयोग करके एक बूलियन | सकारात्मक और नकारात्मक शैनन सहगुणक ([[शैनन विस्तार]]) में बूल के विस्तार प्रमेय का उपयोग करके एक बूलियन प्रकार्य को विघटित किया जा सकता है, जो कि (k-1) -री प्रकार्य हैं जो किसी एक तर्क (शून्य या एक) को ठीक करने के परिणामस्वरूप होते हैं। निविष्टि के एक सम्मुच्चय (एक रैखिक उप-स्थान) पर एक रैखिक बाधा लगाकर प्राप्त सामान्य (k-एरी) कार्यों को उप-कार्यों के रूप में जाना जाता है।<ref name=":1">{{Cite journal|last1=Tarannikov|first1=Yuriy|last2=Korolev|first2=Peter|last3=Botev|first3=Anton|date=2001|editor-last=Boyd|editor-first=Colin|title=Autocorrelation Coefficients and Correlation Immunity of Boolean Functions|journal=Advances in Cryptology — ASIACRYPT 2001|series=Lecture Notes in Computer Science|volume=2248|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=460–479|doi=10.1007/3-540-45682-1_27|isbn=978-3-540-45682-7|doi-access=free}}</ref> | ||
किसी एक तर्क के लिए | किसी एक तर्क के लिए प्रकार्य का [[बूलियन व्युत्पन्न]] एक (k-1)-एरी प्रकार्य है जो तब सत्य होता है जब प्रकार्य का निष्पाद चुने गए निविष्टि चर के प्रति संवेदनशील होता है; यह दो संगत सहकारकों का XOR है। रीड-मुलर विस्तार में एक व्युत्पन्न और एक सहकारक का उपयोग किया जाता है। अवधारणा को x और x + dx पर प्रकार्य के अंतर (XOR) के रूप में प्राप्त दिशा dx में k-एरी व्युत्पन्न के रूप में सामान्यीकृत किया जा सकता है।<ref name=":1" /> | ||
एक बूलियन | एक बूलियन प्रकार्य का मोबिअस बहुपद रूपान्तरण (या बूले-मोबियस रूपान्तरण) इसके बहुपद (बीजीय सामान्य रूप) के गुणांकों का समुच्चय है, जो एकपदीय घातांक सदिशों के प्रकार्य के रूप में होता है। यह एक स्व-व्युत्क्रमण रूपांतर है। यह तेजी से फूरियर रूपांतरण के अनुरूप एक [[तितली आरेख]] ([[फास्ट फूरियर ट्रांसफॉर्म|तीव्र फूरियर रूपांतरण]]) का उपयोग करके कुशलतापूर्वक गणना की जा सकती है।<ref>{{Citation|last=Carlet|first=Claude|title=Boolean Functions for Cryptography and Error-Correcting Codes|date=2010|url=https://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf|work=Boolean Models and Methods in Mathematics, Computer Science, and Engineering|pages=257–397|editor-last=|editor-first=|series=Encyclopedia of Mathematics and its Applications|place=Cambridge|publisher=Cambridge University Press|isbn=978-0-521-84752-0|access-date=2021-05-17|editor2-last=|editor2-first=}}</ref> संपाती बूलियन प्रकार्य उनके मोबियस रूपांतरण के बराबर होते हैं, अर्थात उनकी सत्यमान प्रकार्य (गुणद) मान उनके बीजगणितीय (एकपद ) गुणांक के बराबर होते हैं।<ref>{{Cite journal|last1=Pieprzyk|first1=Josef|last2=Wang|first2=Huaxiong|last3=Zhang|first3=Xian-Mo|date=2011-05-01|title=Mobius transforms, coincident Boolean functions and non-coincidence property of Boolean functions|url=https://doi.org/10.1080/00207160.2010.509428|journal=International Journal of Computer Mathematics|volume=88|issue=7|pages=1398–1416|doi=10.1080/00207160.2010.509428|s2cid=9580510 |issn=0020-7160}}</ref> k तर्कों के 2^2^(k−1) संपाती प्रकार्य हैं।<ref>{{Cite journal|last1=Nitaj|first1=Abderrahmane|last2=Susilo|first2=Willy|last3=Tonien|first3=Joseph|date=2017-10-01|title=Dirichlet product for boolean functions|url=https://doi.org/10.1007/s12190-016-1037-4|journal=Journal of Applied Mathematics and Computing|language=en|volume=55|issue=1|pages=293–312|doi=10.1007/s12190-016-1037-4|s2cid=16760125 |issn=1865-2085}}</ref> | ||
=== गूढ़लेखिकी विश्लेषण === | === गूढ़लेखिकी विश्लेषण === | ||
बूलियन | बूलियन प्रकार्य का [[वॉल्श रूपांतरण]] एक k-एरी पूर्णांक-मूल्यवान प्रकार्य है, जो रैखिक प्रकार्य ([[वाल्श समारोह|वाल्श प्रकार्य]]) में अपघटन के गुणांक देता है, [[फूरियर रूपांतरण]] द्वारा [[लयबद्ध]] में वास्तविक-मूल्यवान प्रकार्य के अपघटन के अनुरूप होता है। इसका वर्ग मानावली प्रकार्य या वॉल्श प्रकार्य है। एकल बिट सदिश का वॉल्श गुणांक बूलियन प्रकार्य के निष्पाद के साथ उस बिट के सहसंबंध के लिए एक उपाय है। अधिकतम (पूर्ण मान में) वॉल्श गुणांक को प्रकार्य की रैखिकता के रूप में जाना जाता है।<ref name=":1" />बिट्स (अनुक्रम) की उच्चतम संख्या को प्रतिरोधक्षमता के रूप में जाना जाता है जिसके लिए सभी वॉल्श गुणांक 0 हैं (अर्थात उपप्रकार्य संतुलित हैं), और प्रकार्य को उस क्रम के प्रति सह-संबंध प्रतिरक्षा कहा जाता है।<ref name=":1" /> वॉल्श गुणांक [[रैखिक क्रिप्ट विश्लेषण]] में एक महत्वपूर्ण भूमिका निभाते हैं। | ||
बूलियन | बूलियन प्रकार्य का स्वत: सहसंबंध एक k-एरी पूर्णांक-मूल्यवान प्रकार्य है जो निविष्टि और प्रकार्य निष्पाद में परिवर्तन के एक निश्चित सम्मुच्चय के बीच संबंध देता है। किसी दिए गए बिट सदिश के लिए यह उस दिशा में व्युत्पन्न के हैमिंग भार से संबंधित है। अधिकतम स्वसहसंबंध गुणांक (निरपेक्ष मूल्य में) को निरपेक्ष संकेतक के रूप में जाना जाता है।<ref name=":0" /><ref name=":1" />यदि बिट्स की एक निश्चित संख्या के लिए सभी स्वतःसंबंध गुणांक 0 हैं (अर्थात व्युत्पन्न संतुलित हैं) तो प्रकार्य को उस क्रम के प्रचार मानदंड को पूरा करने के लिए कहा जाता है; यदि वे सभी शून्य हैं तो प्रकार्य बंकित प्रकार्य है।<ref>{{Cite journal|last1=Canteaut|first1=Anne|last2=Carlet|first2=Claude|last3=Charpin|first3=Pascale|last4=Fontaine|first4=Caroline|date=2000-05-14|title=Propagation characteristics and correlation-immunity of highly nonlinear boolean functions|url=https://dl.acm.org/doi/10.5555/1756169.1756219|journal=Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques|series=EUROCRYPT'00|location=Bruges, Belgium|publisher=Springer-Verlag|pages=507–522|isbn=978-3-540-67517-4}}</ref> स्वतः सहसंबंध गुणांक विभेदक क्रिप्ट विश्लेषण में महत्वपूर्ण भूमिका निभाते हैं। | ||
एक बूलियन | एक बूलियन प्रकार्य के वॉल्श गुणांक और इसके स्वत: सहसंबंध गुणांक वीनर-खिनचिन प्रमेय के समकक्ष से संबंधित हैं, जो बताता है कि स्वत: सहसंबंध और मानावली प्रकार्य वॉल्श रूपांतरण जोड़ी हैं।<ref name=":1" /> | ||
इन अवधारणाओं को स्वाभाविक रूप से सदिश बूलियन कार्यों के लिए उनके निष्पाद बिट्स (निर्देशांक) पर व्यक्तिगत रूप से, या अधिक अच्छी तरह से, निष्पाद बिट्स के सभी रैखिक कार्यों के सम्मुच्चय को देखकर, इसके घटकों के रूप में जाना जाता है।<ref name=":2">{{Cite web|last=Carlet|first=Claude|title=Vectorial Boolean Functions for Cryptography|url=https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf|url-status=live|website=University of Paris|archive-url=https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf |archive-date=2016-01-17 }}</ref> घटकों के वॉल्श रूपांतरणों के सम्मुच्चय को रैखिक सन्निकटन तालिका (LAT) या सहसंबंध परिवेश के रूप में जाना जाता है<ref name=":3">{{Cite web|last=Heys|first=Howard M.|title=A Tutorial on Linear and Differential Cryptanalysis|url=http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf|url-status=live|archive-url=https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf |archive-date=2017-05-17 }}</ref><ref name=":4">{{Cite web|title=S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html|access-date=2021-05-04|website=doc.sagemath.org}}</ref> <ref>{{Cite journal|last1=Daemen|first1=Joan|last2=Govaerts|first2=René|last3=Vandewalle|first3=Joos|date=1995|editor-last=Preneel|editor-first=Bart|title=Correlation matrices|journal=Fast Software Encryption|series=Lecture Notes in Computer Science|volume=1008|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=275–285|doi=10.1007/3-540-60590-8_21|isbn=978-3-540-47809-6|doi-access=free}}</ref><ref>{{Cite web|last=Daemen|first=Joan|date=10 June 1998|title=Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael|url=https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf|url-status=live|website=NIST|archive-url=https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf |archive-date=2018-07-23 }}</ref> यह निविष्टि और निष्पाद बिट्स के विभिन्न रैखिक संयोजनों के बीच संबंध का वर्णन करता है। घटकों के स्वत: सहसंबंध गुणांक का सम्मुच्चय स्वत: सहसंबंध तालिका है,<ref name=":4" />घटकों के वाल्श परिवर्तन से संबंधित<ref>{{Cite web|last=Nyberg|first=Kaisa|date=December 1, 2019|title=The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions|url=https://eprint.iacr.org/2019/1381.pdf|url-status=live|archive-url=https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf |archive-date=2020-11-02 }}</ref> अधिक व्यापक रूप से प्रयुक्त अंतर वितरण तालिका (DDT) के लिए<ref name=":3" /><ref name=":4" />जो निविष्टि और निष्पाद बिट्स में अंतर के बीच सहसंबंधों को सूचीबद्ध करता है (यह भी देखें: S-बक्स)। | इन अवधारणाओं को स्वाभाविक रूप से सदिश बूलियन कार्यों के लिए उनके निष्पाद बिट्स (निर्देशांक) पर व्यक्तिगत रूप से, या अधिक अच्छी तरह से, निष्पाद बिट्स के सभी रैखिक कार्यों के सम्मुच्चय को देखकर, इसके घटकों के रूप में जाना जाता है।<ref name=":2">{{Cite web|last=Carlet|first=Claude|title=Vectorial Boolean Functions for Cryptography|url=https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf|url-status=live|website=University of Paris|archive-url=https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf |archive-date=2016-01-17 }}</ref> घटकों के वॉल्श रूपांतरणों के सम्मुच्चय को रैखिक सन्निकटन तालिका (LAT) या सहसंबंध परिवेश के रूप में जाना जाता है<ref name=":3">{{Cite web|last=Heys|first=Howard M.|title=A Tutorial on Linear and Differential Cryptanalysis|url=http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf|url-status=live|archive-url=https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf |archive-date=2017-05-17 }}</ref><ref name=":4">{{Cite web|title=S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography|url=https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html|access-date=2021-05-04|website=doc.sagemath.org}}</ref> <ref>{{Cite journal|last1=Daemen|first1=Joan|last2=Govaerts|first2=René|last3=Vandewalle|first3=Joos|date=1995|editor-last=Preneel|editor-first=Bart|title=Correlation matrices|journal=Fast Software Encryption|series=Lecture Notes in Computer Science|volume=1008|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=275–285|doi=10.1007/3-540-60590-8_21|isbn=978-3-540-47809-6|doi-access=free}}</ref><ref>{{Cite web|last=Daemen|first=Joan|date=10 June 1998|title=Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael|url=https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf|url-status=live|website=NIST|archive-url=https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf |archive-date=2018-07-23 }}</ref> यह निविष्टि और निष्पाद बिट्स के विभिन्न रैखिक संयोजनों के बीच संबंध का वर्णन करता है। घटकों के स्वत: सहसंबंध गुणांक का सम्मुच्चय स्वत: सहसंबंध तालिका है,<ref name=":4" />घटकों के वाल्श परिवर्तन से संबंधित<ref>{{Cite web|last=Nyberg|first=Kaisa|date=December 1, 2019|title=The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions|url=https://eprint.iacr.org/2019/1381.pdf|url-status=live|archive-url=https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf |archive-date=2020-11-02 }}</ref> अधिक व्यापक रूप से प्रयुक्त अंतर वितरण तालिका (DDT) के लिए<ref name=":3" /><ref name=":4" />जो निविष्टि और निष्पाद बिट्स में अंतर के बीच सहसंबंधों को सूचीबद्ध करता है (यह भी देखें: S-बक्स)। | ||
| Line 89: | Line 89: | ||
'''एकांक अतिविम पर''' | '''एकांक अतिविम पर''' | ||
कोई भी बूलियन | कोई भी बूलियन प्रकार्य <math>f(x): \{0,1\}^n \rightarrow \{0,1\}</math> में एक [[बहुरेखीय बहुपद]] द्वारा विशिष्ट रूप से [[वास्तविक संख्या]] में <math>\mathbb{R}^n</math> विस्तारित (प्रक्षेपित) किया जा सकता है, [[लैग्रेंज बहुपद]] द्वारा गुणा किए गए सत्यमान प्रकार्य मानों के योग द्वारा निर्मित:<math display="block">f^*(x) = \sum_{a \in {\{0,1\}}^n} f(a) \prod_{i:a_i=1} x_i \prod_{i:a_i=0} (1-x_i)</math>उदाहरण के लिए, युग्मक XOR प्रकार्य का विस्तार <math>x \oplus y</math> है<math display="block">0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xy</math>जो बराबर है<math display="block">x + y -2xy</math>कुछ अन्य उदाहरण (<math>1-x</math>), और (<math>xy</math>) और या (<math>x + y - xy</math>) निषेध हैं। जब सभी संकार्य स्वतंत्र होते हैं (कोई चर साझा नहीं करते हैं) एक बूलियन सूत्र में संचालकों के बहुपदों को बार-बार लागू करके एक प्रकार्य का बहुपद रूप पाया जा सकता है। जब गुणांक की गणना की जाती है तो [[मॉड्यूलर अंकगणित]] एक बीजगणितीय सामान्य रूप प्राप्त करता है (झेगाल्किन बहुपद)। | ||
बहुपद के गुणांकों के लिए प्रत्यक्ष व्यंजक उपयुक्त अवकलज लेकर प्राप्त किए जा सकते हैं:<math display="block">\begin{array}{lcl} f^*(00) & = & (f^*)(00) & = & f(00) \\ | बहुपद के गुणांकों के लिए प्रत्यक्ष व्यंजक उपयुक्त अवकलज लेकर प्राप्त किए जा सकते हैं:<math display="block">\begin{array}{lcl} f^*(00) & = & (f^*)(00) & = & f(00) \\ | ||
| Line 97: | Line 97: | ||
\end{array}</math>यह मोबियस रूपांतरण के रूप में सामान्यीकृत होता है। बिट सदिश के आंशिक रूप से अनुक्रमित किए गए सम्मुच्चय के मोबियस व्युत्क्रमण:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>जहाँ <math>|a|</math> बिट सदिश के भार <math>a</math> को दर्शाता है। मोडुलो 2 बूलियन मोबियस रूपांतरण बहुपद है, जो बीजगणितीय सामान्य रूप गुणांक देता है:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>दोनों ही स्तिथि में, योग को सभी बिट-सदिश a पर m द्वारा आच्छादित किया जाता है। | \end{array}</math>यह मोबियस रूपांतरण के रूप में सामान्यीकृत होता है। बिट सदिश के आंशिक रूप से अनुक्रमित किए गए सम्मुच्चय के मोबियस व्युत्क्रमण:<math display="block">f^*(m) = \sum_{a \subseteq m} (-1)^{|a|+|m|} f(a)</math>जहाँ <math>|a|</math> बिट सदिश के भार <math>a</math> को दर्शाता है। मोडुलो 2 बूलियन मोबियस रूपांतरण बहुपद है, जो बीजगणितीय सामान्य रूप गुणांक देता है:<math display="block">\hat f(m) = \bigoplus_{a \subseteq m} f(a)</math>दोनों ही स्तिथि में, योग को सभी बिट-सदिश a पर m द्वारा आच्छादित किया जाता है। | ||
जब कार्यक्षेत्र n-विमीय [[अतिविम]] <math>[0,1]^n</math> तक सीमित है, बहुपद <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> एक सकारात्मक परिणाम की संभावना देता है जब बूलियन | जब कार्यक्षेत्र n-विमीय [[अतिविम]] <math>[0,1]^n</math> तक सीमित है, बहुपद <math>f^*(x): [0,1]^n \rightarrow [0,1]</math> एक सकारात्मक परिणाम की संभावना देता है जब बूलियन प्रकार्य f को अलग-अलग संभावनाओं x के साथ n स्वतंत्र यादृच्छिक (बर्नौली वितरण) चर पर लागू किया जाता है। इस तथ्य का एक विशेष स्तिथि पैरिटी प्रकार्य के लिए [[पाइलिंग-अप लेम्मा|पुंजन लेम्मा]] है। बूलियन प्रकार्य के बहुपद रूप का उपयोग [[फजी लॉजिक|स्वानुशासित तर्क]] के प्राकृतिक विस्तार के रूप में भी किया जा सकता है। | ||
'''सममित अतिविम पर''' | '''सममित अतिविम पर''' | ||
प्रायः, बूलियन कार्यक्षेत्र को <math>\{-1, 1\}</math> रूप में लिया जाता है, असत्य (0) प्रतिचित्रण के साथ 1 और सही (1) से -1 ([[बूलियन कार्यों का विश्लेषण]] देखें)। <math>g(x): \{-1,1\}^n \rightarrow \{-1,1\}</math> के अनुरूप बहुपद निम्न द्वारा दिया जाता है:<math display="block">g^*(x) = \sum_{a \in {\{-1,1\}}^n} g(a) \prod_{i:a_i=-1} \frac{1-x_i}{2} \prod_{i:a_i=1} \frac{1+x_i}{2}</math>सममित बूलियन कार्यक्षेत्र का उपयोग बूलियन कार्यों के विश्लेषण के कुछ पहलुओं को सरल करता है, क्योंकि निषेध -1 से गुणा करने के अनुरूप है और समता | प्रायः, बूलियन कार्यक्षेत्र को <math>\{-1, 1\}</math> रूप में लिया जाता है, असत्य (0) प्रतिचित्रण के साथ 1 और सही (1) से -1 ([[बूलियन का | ||