बिटफील्ड xor के किस सबसेट को दूसरे बिटफील्ड में कैसे ढूंढें?

Question

मेरे पास कुछ हद तक गणित उन्मुख समस्या है। मेरे पास बिटफील्ड का एक समूह है और यह गणना करना चाहते हैं कि उनमें से कौन सा सबसेट एक निश्चित अन्य बिटफील्ड प्राप्त करने के लिए एक साथ जुड़ने के लिए है, या यदि ऐसा करने का कोई तरीका नहीं है तो पता चलता है कि ऐसा कोई सबसेट मौजूद नहीं है।

मैं मूल कोड की बजाय एक मुफ्त पुस्तकालय का उपयोग करके ऐसा करना चाहता हूं, और मैं दृढ़ता से पाइथन बाइंडिंग के साथ कुछ पसंद करूंगा (पायथन के अंतर्निहित गणित पुस्तकालयों का उपयोग करके भी स्वीकार्य होगा, लेकिन मैं पोर्ट बनाना चाहता हूं अंत में यह कई भाषाओं में)। साथ ही प्रत्येक बिट को अपने बाइट में विस्तारित करने की मेमोरी हिट नहीं लेना अच्छा होगा।

कुछ और स्पष्टीकरण: मुझे केवल एक ही समाधान की आवश्यकता है। मेरी matrices sparse के विपरीत हैं। मुझे रनटाइम को पूर्ण न्यूनतम रखने में बहुत दिलचस्पी है, इसलिए मैट्रिक्स को बदलने के लिए एल्गोरिदमिक फैंसी विधियों का उपयोग करना दृढ़ता से पसंद किया जाता है। साथ ही, यह बहुत महत्वपूर्ण है कि विशिष्ट दिए गए बिटफील्ड को आउटपुट किया जाए, इसलिए एक ऐसी तकनीक जो सिर्फ एक सबसेट पाती है जो xor to 0 को काफी कट नहीं करती है।

और मुझे आमतौर पर गाऊशियन उन्मूलन के बारे में पता है। मैं खरोंच से ऐसा करने से बचने की कोशिश कर रहा हूं! mathoverflow को

पोस्ट की गई है, क्योंकि यह स्पष्ट नहीं है कि क्या इस प्रश्न के लिए सही जगह है - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

Answer 1

गणितीय बोल दो बिट्स के XOR F_2 क्षेत्र में अतिरिक्त के रूप में इलाज किया जा सकता।

आप एक F_2 फ़ील्ड में समीकरणों का एक सेट हल करना चाहते हैं। बिट्स के साथ चार बिटफाइल के लिए (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n), आपको समीकरण मिलते हैं:

x * a_0 + y * b_0 + z * c_0 = r_0 
x * a_1 + y * b_1 + z * c_1 = r_1 
... 
x * a_n + y * b_n + z * c_n = r_n 

(जहां आप एक्स, वाई, जेड देखें)।

आप इसे glpk के साथ एक साधारण पूर्णांक रैखिक समस्या के रूप में प्रोग्राम कर सकते हैं, शायद lp_solve (लेकिन मुझे यह याद नहीं है कि यह फिट होगा या नहीं)। हालांकि यह बहुत धीरे-धीरे काम कर सकता है, क्योंकि वे अधिक सामान्य समस्या को हल करने की कोशिश कर रहे हैं।

थोड़ी देर के लिए googling के बाद, ऐसा लगता है कि यह page कोड की तलाश में एक अच्छी शुरुआत हो सकती है। विवरण से ऐसा लगता है कि Dixon और LinBox एक अच्छा फिट हो सकता है।

वैसे भी, मुझे लगता है कि मैथोवरफ्लो में पूछना आपको अधिक सटीक उत्तर दे सकता है। यदि आप करते हैं, तो कृपया यहां अपने प्रश्न को लिंक करें।

अद्यतन:Sagemath इस समस्या को हल करने के लिए M4RI का उपयोग करता है। यह इसे (मेरे लिए) एक बहुत अच्छी सिफारिश बनाता है।

Answer 2

छोटे उदाहरणों के लिए जो स्मृति में आसानी से फिट होते हैं, यह सिर्फ F_2 पर एक रैखिक प्रणाली को हल कर रहा है, इसलिए मॉड -2 गॉसियन उन्मूलन को आजमाएं। फैक्टरिंग (चलनी) एल्गोरिदम में होने वाले बहुत बड़े स्पैस उदाहरणों के लिए, Wiedemann एल्गोरिदम देखें।

Answer 3

एक ही मूल्य पर एकाधिक सबसेट xor होना संभव है; क्या आप सभी सबसेट खोजने की परवाह करते हैं?

शायद एक भारी हाथ से दृष्टिकोण बिटफील्ड की शक्ति को फ़िल्टर करना होगा। हास्केल में:

import Data.Bits 

xorsTo :: Int -> [Int] -> [[Int]] 
xorsTo target fields = filter xorsToTarget (powerset fields) 
    where xorsToTarget f = (foldl xor 0 f) == target 

powerset [] = [[]] 
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) 

यह सुनिश्चित नहीं है कि पावरसेट उत्पन्न किए बिना ऐसा करने का कोई तरीका है या नहीं।(सबसे बुरे मामले में, वास्तव में पूरे पावरसेट के समाधान के लिए संभव है)।

Answer 4

liori के जवाब पर विस्तार से ऊपर हम समीकरण (सापेक्ष 2 में) की एक रेखीय प्रणाली है:

a0, b0, c0 ...| r0 
a1, b1, c1 ...| r1 
...   | 
an, bn, cn ...| rn 

गाऊसी उन्मूलन प्रणाली को हल करने के लिए इस्तेमाल किया जा सकता है। मॉड्यूलो 2 में, ऐड पंक्ति ऑपरेशन एक एक्सओआर ऑपरेशन बन जाता है। जेनेरिक रैखिक सिस्टम सॉल्वर का उपयोग करने के बजाय ऐसा करने के लिए यह बहुत सरल कम्प्यूटेशनल है।

तो, यदि ए 0 शून्य है तो हम एक पंक्ति को स्वैप करते हैं जिसमें एक स्थिति में 1 होता है। फिर किसी अन्य पंक्ति पर एक एक्सओआर (पंक्ति 0 का उपयोग करके) करें "ए" बिट 1 है। फिर पंक्ति 1 और कॉलम बी का उपयोग करके दोहराएं, फिर पंक्ति 2 कॉल सी, आदि

यदि आपको शून्य की पंक्ति मिलती है आर कॉलम में गैर-शून्य के साथ फिर सबसेट डीएनई।