Ìèíèñòåðñòâî îáðàçîâàíèÿ è íàóêè Ðîññèéñêîé Ôåäåðàöèè
Ôåäåðàëüíîå àãåíòñòâî ïî îáðàçîâàíèþ
Ôåäåðàëüíîå ãîñóäàðñòâåííîå îáðàçîâàòåëüíîå ó÷ðåæäåíèå âûñøåãî
ïðîôåññèîíàëüíîãî îáðàçîâàíèÿ ¾Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé
óíèâåðñèòåò¿
Ìàòåìàòèêî-ìåõàíè÷åñêèé ôàêóëüòåò
Êàôåäðà èññëåäîâàíèÿ îïåðàöèé
Äèïëîìíàÿ ðàáîòà
Èñàåâ Ãëåá Àíäðååâè÷
Ïîèñê áóëåâûõ ôóíêöèé ìàêñèìàëüíîé íåëèíåéíîñòè ïðè
íàëè÷èè îãðàíè÷åíèé
Çàâåäóþùèé êàôåäðîé:
ä. ô.-ì. í., ïðîôåññîð È. Â. Ðîìàíîâñêèé
Íàó÷íûé ðóêîâîäèòåëü:
ê. ô.-ì. í., äîöåíò È. Â. Àãàôîíîâà
Ðåöåíçåíò:
ê. ô.-ì. í., äîöåíò Î. Ì. Äìèòðèåâà
Ñàíêò-Ïåòåðáóðã
2016 ã.
Saint Petersburg State University
Faculty of Mathematics and Mechanics
Department of Operations Research
Graduation Thesis
Isaev Gleb Andreevich
Finding Boolean functions with maximal nonlinearity under
constraints
Head of Department:
Professor I. V. Romanovsky
Scienti c Supervisor:
Associate Professor I. V. Agafonova
Reviewer:
Associate Professor O. M. Dmitrieva
Saint Petersburg
2016
Ñîäåðæàíèå
Ââåäåíèå
2
1
Îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ
3
2
Íåêîòîðûå òåîðåìû è ëåììû, ñâÿçàííûå ñ íåëèíåéíîñòÿìè
5
3
Ìåòîä ïîñòðîåíèÿ óñòîé÷èâûõ ôóíêöèé ïîðÿäêà m ñ âûñîêîé íåëèíåéíîñòüþ
8
4
Èñïîëüçîâàíèå öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ äëÿ ìàêñèìèçàöèè
íåëèíåéíîñòè ïðè îãðàíè÷åííîé óñòîé÷èâîñòè
10
5
Ïðèáëèæåííûå àëãîðèòìû ïîèñêà áóëåâûõ ôóíêöèé
5.1
5.2
5.3
Ãåíåòè÷åñêèé àëãîðèòì (GA) . . . . . . . .
Àëãîðèòì íàïðàâëåííîãî ïîèñêà (DSA) . .
5.2.1 Ïðèìåðû ðàáîòû àëãîðèòìà . . . .
5.2.2 Ïðîãðàììà, ðåàëèçóþùàÿ àëãîðèòì
Ðåçóëüòàòû àëãîðèòìà . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
13
14
16
17
18
Çàêëþ÷åíèå
19
Ëèòåðàòóðà
20
1
Ââåäåíèå
Ðàáîòà ïîñâÿùåíà ïîñòðîåíèþ è ïîèñêó áóëåâûõ ôóíêöèé ìàêñèìàëüíîé íåëèíåéíîñòè ïðè íàëè÷èè êðèïòîãðàôè÷åñêè âàæíûõ îãðàíè÷åíèé, òàêèõ, êàê ñáàëàíñèðîâàííîñòü, êîððåëÿöèîííàÿ èììóííîñòü è óñòîé÷èâîñòü. Ìû ïîñ÷èòàåì ìàêñèìàëüíóþ
íåëèíåéíîñòü ïðè îãðàíè÷åííîé óñòîé÷èâîñòè â îïðåäåëåííûõ ñëó÷àÿõ è ðàññìîòðèì
íåêîòîðûå ìåòîäû ïîèñêà è ïîñòðîåíèÿ áóëåâûõ ôóíêöèé ñ âûñîêîé íåëèíåéíîñòüþ è
íåêîòîðîé ôèêñèðîâàííîé óñòîé÷èâîñòüþ.
 äàííîé ðàáîòå îòìåòèì òðè îñíîâíûõ íàïðàâëåíèÿ. Âî-ïåðâûõ, äëÿ áóëåâîé ôóíêöèè îò n ïåðåìåííûõ ìû áóäåì ìàêñèìèçèðîâàòü íåëèíåéíîñòü ïðè îãðàíè÷åííîé óñòîé÷èâîñòè â îïðåäåëåííûõ ñëó÷àÿõ, âîñïîëüçîâàâøèñü ëèíåéíûìè îãðàíè÷åíèÿìè è íåêîòîðûìè òåîðåìàìè î ãðàíèöàõ íåëèíåéíîñòè. Âî-âòîðûõ, ìû èçó÷èì ìåòîä ïîñòðîåíèÿ
óñòîé÷èâûõ ôóíêöèé ñ õîðîøåé íåëèíåéíîñòüþ, êîòîðûé áûë ïðåäñòàâëåí â [2]. Âòðåòüèõ, ìû ðàññìîòðèì ïðèáëèæåííûå àëãîðèòìû ïîèñêà áóëåâûõ ôóíêöèé, òàêèå,
êàê ãåíåòè÷åñêèé àëãîðèòì è àëãîðèòì íàïðàâëåííîãî ïîèñêà. Îíè ïðåäíàçíà÷åíû äëÿ
íàõîæäåíèÿ áóëåâûõ ôóíêöèé ñ õîðîøèìè ñâîéñòâàìè, òàêèõ, êàê íåëèíåéíîñòü, âûñîêèé ïîðÿäîê êîððåëÿöèîííîé èììóííîñòè è ò.ä. Òàêîé àëãîðèòì áûë ðàññìîòðåí â
[1].
Ðàáîòà îðãàíèçîâàíà ñëåäóþùèì îáðàçîì.  ïåðâîì ðàçäåëå äàíû îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ, ïðèìåíÿåìûå â äàííîé ðàáîòå. Âî âòîðîì ðàçäåëå ïðèâîäÿòñÿ òåîðåìû, ñâÿçàííûå ñ äîêàçàòåëüñòâîì ñóùåñòâîâàíèÿ îïðåäåëåííûõ ãðàíèö íåëèíåéíîñòè, âìåñòå ñ ïðèìåðàìè.  òðåòüåì ðàçäåëå ðàññìàòðèâàåòñÿ ìåòîä ïîñòðîåíèÿ
óñòîé÷èâûõ áóëåâûõ ôóíêöèé ñ âûñîêîé íåëèíåéíîñòüþ, êîòîðûé áûë ïðåäñòàâëåí â
[2].  ÷åòâåðòîì ðàçäåëå îïèñûâàåòñÿ èñïîëüçîâàíèå öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ äëÿ ìàêñèìèçàöèè íåëèíåéíîñòè áóëåâûõ ôóíêöèé ñ îãðàíè÷åííîé óñòîé÷èâîñòüþ.
 ïÿòîì ðàçäåëå ïðèâîäÿòñÿ ïðèáëèæåííûå àëãîðèòìû ïîèñêà áóëåâûõ ôóíêöèé, òàêèå, êàê ãåíåòè÷åñêèé àëãîðèòì è àëãîðèòì íàïðàâëåííîãî ïîèñêà áóëåâûõ ôóíêöèé
ñ õîðîøèìè ñâîéñòâàìè. Àâòîð ðàáîòû çàïðîãðàììèðîâàë ìåòîäû, îïèñàííûå â äâóõ
ïîñëåäíèõ ðàçäåëàõ, íà ÿçûêàõ MATLAB è PASCAL. Â MATLAB áûëè èñïîëüçîâàíû
âñòðîåííûå ôóíêöèè öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ è ãåíåòè÷åñêîãî àëãîðèòìà.
2
1
Îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ
Áóëåâà ôóíêöèÿ ýòî òàêàÿ ôóíêöèÿ f îò n ïåðåìåííûõ, ó êîòîðîé êàæäûé
íåçàâèñèìûé àðãóìåíò xi , i ∈ 1 : n è êàæäîå çíà÷åíèå ôóíêöèè f (x1 , . . . , xn ) ðàâíî 0
èëè 1. Îáû÷íî áóëåâó ôóíêöèþ îòîæäåñòâëÿþò ñ å¼ âåêòîðîì çíà÷åíèé. Ìíîæåñòâî
âåêòîðîâ ðàçìåðíîñòè n, ñîñòîÿùèõ èç ëîãè÷åñêèõ ïåðåìåííûõ, îáîçíà÷èì ÷åðåç Vn , à
ìíîæåñòâî áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ ÷åðåç Fn .
Ôóíêöèÿ îò n ïåðåìåííûõ èìååò 2n çíà÷åíèé. Òàê êàê íà êàæäîì âåêòîðå áóëåâà
ôóíêöèÿ ìîæåò ïðèíèìàòü çíà÷åíèå ëèáî 0, ëèáî 1, òî êîëè÷åñòâî âñåõ n-àðíûõ áóëåâûõ
n
ôóíêöèé ðàâíî 22 .
Ëþáóþ áóëåâó ôóíêöèþ ìîæíî åäèíñòâåííûì îáðàçîì çàïèñàòü â àëãåáðàè÷åñêîé
íîðìàëüíîé ôîðìå (ÀÍÔ), òî åñòü
f (x1 , x2 , . . . , xn ) = a0 ⊕ a1 x1 ⊕ a2 x2 ⊕ · · · ⊕ an xn ⊕ a12 x1 x2 ⊕ a13 x1 x3 ⊕ · · · ⊕ a1...n x1 . . . xn ,
ãäå ai1 ...in ∈ {0, 1}, à îïåðàöèÿìè â ýòîì ìíîãî÷ëåíå ñëóæàò êîíúþíêèÿ è ñëîæåíèå ïî
ìîäóëþ 2 (îáîçíà÷àåòñÿ çíàêîì ⊕).
Àëãåáðàè÷åñêàÿ ñòåïåíü ôóíêöèè ýòî ñòåïåíü ÀÍÔ ýòîé ôóíêöèè, òî åñòü
ìàêñèìàëüíàÿ ñòåïåíü ñðåäè ñòåïåíåé âñåõ ìîíîìîâ. Ôóíêöèè, èìåþùèå ñòåïåíü íå
âûøå 1, íàçûâàþòñÿ àôôèííûìè.
Ââåäåì ñêàëÿðíîå ïðîçâåäåíèå ha, bi = a1 b1 ⊕· · ·⊕an bn . Ïðåîáðàçîâàíèåì Óîëøà
Àäàìàðà áóëåâîé ôóíêöèè f îò n ïåðåìåííûõ íàçûâàåòñÿ öåëî÷èñëåííàÿ ôóíêöèÿ Wf ,
çàäàííàÿ íà ìíîæåñòâå Vn ðàâåíñòâîì
X
(−1)hu,ωi⊕f (u) .
Wf (ω) =
u∈Vn
Ïðåîáðàçîâàíèåì Ôóðüå áóëåâîé ôóíêöèè f îò n ïåðåìåííûõ íàçûâàåòñÿ öåëî÷èñëåííàÿ ôóíêöèÿ Ff , çàäàííàÿ íà ìíîæåñòâå Vn ðàâåíñòâîì
X
(−1)hu,ωi f (u).
Ff (ω) =
u∈Vn
Øèðîêî èçâåñòíà ôîðìóëà îáðàùåíèÿ ïðåîáðàçîâàíèÿ Ôóðüå â ïðåîáðàçîâàíèå Óîëøà
Àäàìàðà:
Wf (ω) = δ0 (ω) · 2n − 2Ff (ω),
ãäå
(
δ0 (ω) =
1, ω = 0;
0, ω =
6 0.
Âåñ Õýììèíãà wt(f ) áóëåâîé ôóíêöèè f ýòî ÷èñëî åäèíèö âåêòîðà çíà÷åíèé
ôóíêöèè f .
Ðàññòîÿíèåì Õýììèíãà ìåæäó äâóìÿ ôóíêöèÿìè f è g íàçûâàåòñÿ âåñ ôóíêöèè
f ⊕ g èëè, èíà÷å ãîâîðÿ, ÷èñëî òàêèõ âåêòîðîâ x, ïðè êîòîðûõ f (x) 6= g(x).
3
Íåëèíåéíîñòü Nf áóëåâîé ôóíêöèè f ýòî ðàññòîÿíèå Õýììèíãà ìåæäó f è
ìíîæåñòâîì àôôèííûõ ôóíêöèé.
Øèðîêî èçâåñòíà ôîðìóëà ïîäñ÷åòà íåëèíåéíîñòè:
Nf = 2n−1 −
1
· max |Wf (ω)| .
2 ω∈Vn
Ðàññìîòðèì âàæíåéøèå êëàññû áóëåâûõ ôóíêöèé.
Áåíò-ôóíêöèåé íàçûâàåòñÿ òàêàÿ áóëåâà ôóíêöèÿ îò n ïåðåìåííûõn (n ÷åòíî),
÷òî ìîäóëü êàæäîãî êîýôôèöèåíòà Óîëøà-Àäàìàðà ýòîé ôóíêöèè ðàâåí 2 2 .
Áóëåâà ôóíêöèÿ íàçûâàåòñÿ ñáàëàíñèðîâàííîé, åñëè â òàáëèöå èñòèííîñòè êîëè÷åñòâî íóëåé ñîâïàäàåò ñ êîëè÷åñòâîì åäèíèö.
Ôóíêöèÿ f (x1 , x2 , . . . , xn ) íàçûâàåòñÿ êîððåëÿöèîííî èììóííîé ïîðÿäêà m, åñëè
ïðè ôèêñàöèè íå áîëåå m êîîðäèíàò âåðîÿòíîñòü ðàñïðåäåëåíèÿ çíà÷åíèé ëþáîãî èç
ñóæåíèé ôóíêöèè íå ìåíÿåòñÿ. Ýêâèâàëåíòíîå îïðåäåëåíèå: ôóíêöèÿ f (x1 , x2 , . . . , xn )
íàçûâàåòñÿ êîððåëÿöèîííî èììóííîé ïîðÿäêà m, åñëè å¼ ïðåîáðàçîâàíèå Óîëøà
Àäàìàðà Wf óäîâëåòâîðÿåò ðàâåíñòâó Wf (ω) = 0 ïðè 1 6 wt(ω) 6 m. Î÷åâèäíî, ÷òî
åñëè ôóíêöèÿ êîððåëÿöèîííî èììóííà ïîðÿäêà m, m > 1, òî îíà êîðððåëÿöèîííî èììóííà ïîðÿäêà j, 1 6 j < m. Ââåäåì ñëåäóþùåå îáîçíà÷åíèå:
corf = max{m ∈ N | f êîððåëÿöèîííî èììóííà ïîðÿäêà m}.
Ôóíêöèÿ f (x1 , x2 , . . . , xn ) íàçûâàåòñÿ m-óñòîé÷èâîé, åñëè ïðè ôèêñàöèè íå áîëåå
m êîîðäèíàò ëþáîå èç ñóæåíèé ôóíêöèè f ñáàëàíñèðîâàíî. Ýêâèâàëåíòíîå îïðåäåëåíèå: ôóíêöèÿ f (x1 , x2 , . . . , xn ) íàçûâàåòñÿ m-óñòîé÷èâîé, åñëè å¼ ïðåîáðàçîâàíèå
ÓîëøàÀäàìàðà Wf óäîâëåòâîðÿåò ðàâåíñòâó Wf (ω) = 0 ïðè 0 6 wt(ω) 6 m. Î÷åâèäíî, ÷òî åñëè ôóíêöèÿ m-óñòîé÷èâà, m > 1, òî îíà j -óñòîé÷èâà, ãäå 1 6 j < m.
Çàìåòèì, ÷òî åñëè ôóíêöèÿ ÿâëÿåòñÿ êîððåëÿöèîííî èììóííîé ïîðÿäêà m, òî îíà
ìîæåò áûòü è m-óñòîé÷èâîé, åñëè äîïîëíèòåëüíî ïðîâåðèòü óñëîâèå Wf (ω) = 0, ãäå
wt(ω) = 0. Äëÿ ýòîãî äîñòàòî÷íî ïîêàçàòü, ñáàëàíñèðîâàíà ëè íàøà ôóíêöèÿ èëè íåò.
Ââåä¼ì åù¼ îäíî îáîçíà÷åíèå:
sut f = max{d ∈ N | f ÿâëÿåòñÿ d − óñòîé÷èâîé ôóíêöèåé}.
Çàìåòèì, ÷òî äëÿ ëþáîé f ∈ Fn ñïðàâåäëèâî íåðàâåíñòâî n − 1 > sut f .
Íåðàâåíñòâà Çèãåíòàëåðà:
• Åñëè f êîððåëÿöèîííî èììóííàÿ ôóíêöèÿ ïîðÿäêà m îò n ïåðåìåííûõ, òî
deg f 6 n − m.
• Åñëè f ÿâëÿåòñÿ m-óñòîé÷èâîé ôóíêöèåé è m 6 n − 2, òî deg f 6 n − m − 1.
Ýòè íåðàâåíñòâà ïðèâåäåíû âìåñòå ñ äîêàçàòåëüñòâîì â [6].
4
2
Íåêîòîðûå òåîðåìû è ëåììû, ñâÿçàííûå ñ íåëèíåéíîñòÿìè
Èñïîëüçîâàíèå óñòîé÷èâûõ ôóíêöèé â êðèïòîãðàôè÷åñêèõ öåëÿõ âûçûâàåò èíòåðåñ ê èçó÷åíèþ íåëèíåéíîñòè ýòèõ ôóíêöèé. Ñëåäóþùèé ðàçäåë ïîñâÿùåí îöåíêàì
íåëèíåéíîñòè êîððåëÿöèîííî èììóííûõ è óñòîé÷èâûõ ôóíêöèé, à òàêæå óñëîâèÿì äîñòèæèìîñòè ýòèõ îöåíîê. Âñå òåîðåìû è óòâåðæäåíèÿ áûëè âçÿòû èç [4].
Òåîðåìà 1. Ñïðàâäåäëèâû ñëåäóþùèå óòâåðæäåíèÿ:
1) Åñëè
2) Åñëè
f ∈ Fn , cor f = m 6 n − 1,
f ∈ Fn , sut f = m 6 n − 2,
òî
òî
Nf 6 2n−1 − 2m ;
Nf 6 2n−1 − 2m+1 .
Ïðèìåð 1. Äîñòèæèìîñòü îöåíêè 1 èç òåîðåìû 1.
Ïóñòü n = 6, m = 3. Âîçüìåì ôóíêöèþ
M
f (x1 , . . . , x6 ) =
xi xj xk ⊕
4
M
xi xi+1 ⊕ x1 x5 ⊕
i=1
16i<j<k66
5
M
⊕1.
i=1
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ íåñáàëàíñèðîâàííîé êîððåëÿöèîííî èììóííîé ïîðÿäêà 3
ôóíêöèåé. ż íåëèíåéíîñòü ðàâíà 24: Nf = 24, ò.å. îöåíêà äîñòèãàåòñÿ.
Ïðèìåð 2. Äîñòèæèìîñòü îöåíêè 2 èç òåîðåìû 1.
Ïóñòü n = 3, m = 0. Âîçüìåì ôóíêöèþ
f (x1 , x2 , x3 ) = 1 ⊕ x2 ⊕ x3 ⊕ x1 x2 ⊕ x2 x3 .
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ ñáàëàíñèðîâàííîé. ż íåëèíåéíîñòü ðàâíà 2: Nf = 2, ò.å.
îöåíêà äîñòèãàåòñÿ.
Òåîðåìà 2. Ïóñòü f ∈ Fn , sut f = m 6 n − 3, deg f + sut f 6 n − 2. Òîãäà Nf 6
6 2n−1 − 2m+2 .
Ïðèìåð 3. Äîñòèæèìîñòü îöåíêè èç òåîðåìû 2.
Ïóñòü n = 4, m = 0. Âîçüìåì ôóíêöèþ f = B2171 .
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ ñáàëàíñèðîâàííîé. ż íåëèíåéíîñòü ðàâíà 4: Nf = 4, ò.å.
îöåíêà äîñòèãàåòñÿ.
Ñëåäñòâèå 1. Ïóñòü f ∈ Fn , f 6= const, sut f = m 6 n − 2, Nf = 2n−1 − 2m+1 . Òîãäà
deg f + sut f = n − 1.
Ôóíêöèÿ èç ïðèìåðà 2 êàê ðàç óäîâëåòâîðÿåò ýòîìó ñëåäñòâèþ.
Òåîðåìà 3. Ïóñòü f ∈ Fn .
1. Åñëè
cor f = m 6
n
2
− 1,
òî
n
Nf 6 2n−1 − 2 2 −1 − 2m .
1 Çäåñü
è äàëåå âåêòîð çíà÷åíèé áóëåâîé ôóíêöèè îò áîëüøîãî ÷èñëà ïåðåìåííûõ áóäåì ïèñàòü â
øåñòíàäöàòåðè÷íîì âèäå.
5
2. Åñëè
sut f = m 6
n
2
− 2,
òî
n
Nf 6 2n−1 − 2 2 −1 − 2m+1 .
Ïðèìåð 4. Äîñòèæèìîñòü îöåíêè 1 èç òåîðåìû 3.
Ïóñòü n = 4, m = 1. Âîçüìåì ôóíêöèþ f = 6DDE .
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ íåñáàëàíñèðîâàííîé êîððåëÿöèîííî èììóííîé ïîðÿäêà 1
ôóíêöèåé. ż íåëèíåéíîñòü ðàâíà 4: Nf = 4, ò.å. îöåíêà äîñòèãàåòñÿ.
Ïðèìåð 5. Äîñòèæèìîñòü îöåíêè 2 èç òåîðåìû 3.
Ïóñòü n = 6, m = 1. Âîçüìåì ôóíêöèþ f = BF 6882394A54A57D.
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ 1-óñòîé÷èâîé. ż íåëèíåéíîñòü ðàâíà 24: Nf = 24, ò.å.
îöåíêà äîñòèãàåòñÿ.
Òåîðåìà 4. Ïóñòü f ∈ Fn , sut f = m 6
n
2
− 2.
&
Òîãäà
2n−m−2
q
P
2n − m
i=1
Nf 6 2n−1 − 2m+1
'
n
i
.
Ôóíêöèÿ èç ïðèìåðà 5 äîñòèãàåò îöåíêè èç òåîðåìû 4.
Îáîçíà÷èì ÷åðåç Nmax (n, m) ìàêñèìàëüíî âîçìîæíóþ íåëèíåéíîñòü m-óñòîé÷èâîé
áóëåâîé ôóíêöèè èç Fn . Ëþáóþ ïðîèçâîëüíóþ ôóíêöèþ îò n ïåðåìåííûõ íàçîâåì (−1)óñòîé÷èâîé ôóíêöèåé, ïîñêîëüêó ó íå¼ íå ñóùåñòâóåò ïîäôóíêöèé îò n + 1 ïåðåìåííûõ,
à ëþáóþ ñáàëàíñèðîâàííóþ ôóíêöèþ 0-óñòîé÷èâîé ôóíêöèåé. Äëÿ (−1)-óñòîé÷èâûõ
ôóíêöèé ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ:
n
• Nmax (n, −1) 6 2n−1 − 2 2 −1 (äîñòèãàåòñÿ ïðè áåíò-ôóíêöèÿõ);
• Ïðè íå÷åòíûõ n 6 7: Nmax (n, −1) = 2n−1 − 2
n−1
2
• Ïðè íå÷åòíûõ n > 15: Nmax (n, −1) > 2n−1 − 2
;
n−1
2
.
Äëÿ 0-óñòîé÷èâûõ ôóíêöèé f ∈ Fn èìååì:
n
• Nf < 2n−1 − 2 2 −1 ;
n
• Nmax (n, m) < 2n−1 − 2 2 −1 ïðè m > 0.
Äëÿ m-óñòîé÷èâûõ ôóíêöèé f ∈ Fn èçâåñòíû ñëåäóþùèå ôàêòû:
• Åñëè m > n − 2, òî deg f 6 1 è Nmax (n, m) = 0;
• Nmax (n, n − 3) = 2n−2 ;
• Nmax (n, n − 4) = 2n−1 − 2n−3 .
 ÷àñòíîñòè èçâåñòíî, ÷òî
• Nmax (4, 0) = 4;
• Nmax (5, −1) = Nmax (5, 0) = Nmax (5, 1) = 12;
6
• Nmax (6, 0) = 26;
• Nmax (6, 1) = Nmax (6, 2) = 24;
• Nmax (7, −1) = Nmax (7, 0) = Nmax (7, 1) = 56.
Òåîðåìà 5. Ïóñòü
2n−7
3
6 m 6 n − 2.
Òîãäà âûïîëíÿåòñÿ
Nmax (n, m) = 2n−1 − 2m+1 .
Ïîçäíåå áûëî äîêàçàíî, ÷òî ýòà íåëèíåéíîñòü òàêæå äîñòèãàåòñÿ ïðè îãðàíè÷åíèÿõ
6 m 6 n − 2.
2n−8
3
Ïðèìåð 6. Äîñòèæèìîñòü ìàêñèìàëüíîé íåëèíåéíîñòè èç òåîðåìû 5.
Ïóñòü n = 4, m = 1. Âîçüìåì ôóíêöèþ f = D18B .
Òàêàÿ ôóíêöèÿ ÿâëÿåòñÿ 1-óñòîé÷èâîé. ż íåëèíåéíîñòü ðàâíà 4: Nf = 4, ò.å. ìàêñèìàëüíàÿ íåëèíåéíîñòü äîñòèãàåòñÿ.
Òåîðåìà 6. Äëÿ öåëûõ m è n, óäîâëåòâîðÿþùèõ íåðàâåíñòâàì
−
− log2 n+2
3
n−1
m+1
2
−2
2,
ñóùåñòâóåò
m-óñòîé÷èâàÿ
áóëåâà ôóíêöèÿ èç
Fn
2n−7
3
6 m 6 n−
ñ íåëèíåéíîñòüþ
, óäîâëåòâîðÿþùàÿ íåðàâåíñòâó Çèãåíòàëåðà äëÿ êàæäîé îòäåëüíîé ïå-
ðåìåííîé.
Ôóíêöèÿ èç ïðèìåðà 6 óäîâëåòâîðÿåò óñëîâèÿì òåîðåìû 6 è ÿâëÿåòñÿ èñêîìîé ôóíêöèåé.
7
3
Ìåòîä ïîñòðîåíèÿ óñòîé÷èâûõ ôóíêöèé ïîðÿäêà
m
ñ âûñîêîé íåëèíåéíîñòüþ
 äàííîì ðàçäåëå îïèøåì ìåòîä ïîñòðîåíèÿ óñòîé÷èâîé ôóíêöèè ïîðÿäêà m îò
n ïåðåìåííûõ ïðè îïðåäåëåííîì l1 ñ íåëèíåéíîñòüþ Nf = 2n−1 − 2l1 −1 , êîòîðûé áûë
ïðåäñòàâëåí â [2]. Îñîáåííî âàæíî îòìåòèòü, ÷òî òàêàÿ íåëèíåéíîñòü î÷åíü âûñîêà, íî
íå âñåãäà ìàêñèìàëüíà.
Âõîä. n (n > 4; êîëè÷åñòâî àðãóìåíòîâ áóëåâîé ôóíêöèè), m (1 6 m 6 n − 3;
óñòîé÷èâîñòü).
1. Ïóñòü l1 , m + 1 6 l1 6 n òàêîå íàèìåíüøåå ÷èñëî, óäîâëåòâîðÿþùåå
l1
l1
l1
+
+ ··· +
> 2n−l1 .
m+1
m+2
l1
2. Âûáåðåì 2n−l1 âåêòîðîâ A0 , A1 , . . . , A2n−l1 −1 èç ìíîæåñòâà Vl1 ñ âåñîì íå ìåíüøèì,
÷åì m + 1.
3. Îïðåäåëèì ôóíêöèþ f ∈ Fn ñëåäóþùèì îáðàçîì:
f (y1 , . . . , yn−l1 , x1 , . . . , xl1 ) = f (y, x) = Ay · x.
Ôóíêöèÿ, îïðåäåëåííàÿ â øàãå 3, ïîëó÷àåòñÿ m-óñòîé÷èâîé, è îíà èìååò íåëèíåéíîñòü Nf = 2n−1 − 2l1 −1 . Ýòî îáúÿñíÿåòñÿ òåîðåìàìè, ïðèâåäåííûìè â [2]. Àëãåáðàè÷åñêàÿ ñòåïåíü òàêîé ôóíêöèè f (x) âûâîäèòñÿ èç ðàâåíñòâà deg(f ) = n − l1 + 1.
Ýòîò ìåòîä è ñâÿçàííûå ñ íèì ôàêòû ðàññìàòðèâàþòñÿ â [2].
Ïðèìåð. Ïîñòðîèì 1-óñòîé÷èâóþ íåëèíåéíóþ áóëåâó ôóíêöèþ îò 7 ïåðåìåííûõ.
n = 7, k = 1.
3
3
4
4
4
7−3
1. Èç-çà òîãî, ÷òî
+
2
è
+
+
> 27−4 , ìû èìååì l1 = 4.
2
3
2
3
4
Âõîä:
2. Âûáåðåì 8 âåêòîðîâ Ai ∈ V4 ñ âåñîì wt(Ai ) > 2.
A0 = (1, 1, 0, 0), A1 = (1, 0, 1, 0),
A2 = (1, 0, 0, 1), A3 = (0, 1, 1, 0),
A4 = (0, 1, 0, 1), A5 = (0, 0, 1, 1),
A6 = (1, 1, 1, 0), A7 = (1, 1, 0, 1).
3. Îïðåäåëèì ôóíêöèþ f : V7 → V1 òàêèì îáðàçîì:
f (y, x) = f (y1 , y2 , y3 , x1 , x2 , x3 , x4 ) = Ay · x =
= (y1 ⊕ 1)(y2 ⊕ 1)(y3 ⊕ 1)(x1 ⊕ x2 ) ⊕ (y1 ⊕ 1)(y2 ⊕ 1)y3 (x1 ⊕ x3 )⊕
⊕(y1 ⊕ 1)y2 (y3 ⊕ 1)(x1 ⊕ x4 ) ⊕ (y1 ⊕ 1)y2 y3 (x2 ⊕ x3 )⊕
⊕y1 (y2 ⊕ 1)(y3 ⊕ 1)(x2 ⊕ x4 ) ⊕ y1 (y2 ⊕ 1)y3 (x3 ⊕ x4 )⊕
⊕y1 y2 (y3 ⊕ 1)(x1 ⊕ x2 ⊕ x3 ) ⊕ y1 y2 y3 (x1 ⊕ x2 ⊕ x4 ).
8
Òàêàÿ ôóíêöèÿ f 1-óñòîé÷èâà è èìååò íåëèíåéíîñòü Nf = 26 − 23 = 56 è ñòåïåíü
deg f = 7 − 4 + 1 = 4.
Ïàçàëèê è Éîõàíññîí ñ ïîìîùüþ ýòîãî ìåòîäà ñìîãëè ïîñòðîèòü ôóíêöèè ñ âûñîêîé íåëèíåéíîñòüþ è ïðèâåëè òàáëèöó íåëèíåéíîñòåé m-óñòîé÷èâûõ ôóíêöèé îò n
ïåðåìåííûõ.
m
0
1
2
3
4
5
6
5
12
12
8
0
0
0
0
6
24
24
24
16
0
0
0
n
8
112
112
112
96
96
64
0
7
56
56
48
48
32
0
0
9
240
240
240
224
192
192
128
10
480
480
480
480
448
448
384
Òàáëèöà 1. Íåëèíåéíîñòü Nf , ïîëó÷åííàÿ â ñîîòâåòñòâèè ñ ìåòîäîì ïîñòðîåíèÿ èç [2].
Ñòîèò çàìåòèòü, ÷òî èç íåðàâåíñòâà Çèãåíòàëåðà ñëåäóåò, ÷òî m 6 n − 1 − deg f .
Ïîýòîìó ôóíêöèÿ, èìåþùàÿ óñòîé÷èâîñòü ïîðÿäêà íå ìåíåå, ÷åì n − 2, ÿâëÿåòñÿ ëèáî
àôôèííîé, ëèáî íóëåâîé, ÷òî è îáúÿñíÿåò íóëåâóþ íåëèíåéíîñòü.
9
4
Èñïîëüçîâàíèå öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ
äëÿ ìàêñèìèçàöèè íåëèíåéíîñòè ïðè îãðàíè÷åííîé
óñòîé÷èâîñòè
×òîáû ìàêñèìèçèðîâàòü íåëèíåéíîñòü ïðè îãðàíè÷åííîé óñòîé÷èâîñòè, âîñïîëüçóåìñÿ ëèíåéíûìè îãðàíè÷åíèÿìè, êîòîðûå áóäóò ïðèâåäåíû íèæå,
Ïðîáëåìà ñóùåñòâîâàíèÿ m-óñòîé÷èâîé áóëåâîé ôóíêöèè f (x) ñ íåëèíåéíîñòüþ Nf
ýêâèâàëåíòíà çàäà÷å íàõîæäåíèÿ òàêîé áóëåâîé ôóíêöèè f (x), ïðåîáðàçîâàíèå Ôóðüå
êîòîðîé óäîâëåòâîðÿåò íàáîðó ñëåäóþùèõ îãðàíè÷åíèé:
Ff (0) = 2n−1 , ñáàëàíñèðîâàííîñòü,
Ff (ω) = 0, 1 6 wt(ω) 6 m, m − óñòîé÷èâîñòü,
(1)
|Ff (ω)| 6 2n−1 − Nf , ω 6= 0, íåëèíåéíîñòü.
Çàïèøåì ýêñòðåìàëüíóþ çàäà÷ó íà ìàêñèìèçàöèþ íåëèíåéíîñòè, ôèêñèðóÿ ïîðÿäîê
óñòîé÷èâîñòè:
Nf → sup
ïðè óñëîâèè, ÷òî
Ff (0) = 2n−1 ,
Ff (ω) = 0, 1 6 wt(ω) 6 m,
Ff (ω) + Nf 6 2n−1 , ω 6= 0,
(2)
−Ff (ω) + Nf 6 2n−1 , ω 6= 0,
Nf > 0, Nf öåëîå.
Ìû çíàåì ïî îïðåäåëåíèþ, ÷òî Ff (ω) = Aω f , ãäå A ýòî ìàòðèöà, ñîñòîÿùàÿ èç ±1,
êîòîðûå ïîëó÷åíû èç ôóíêöèè Óîëøà (−1)hω,xi (ìàòðèöà ÓîëøàÀäàìàðà), Aω ýòî
ñòðîêà ìàòðèöû ÓîëøàÀäàìàðà A, ñîîòâåòñòâóþùàÿ ω (ñì. [3]). Òîãäà ìîæíî çàïèñàòü
çàäà÷ó 2 êàê çàäà÷ó öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ:
Nf → sup
ïðè óñëîâèè, ÷òî
AO f = 2n−1 ,
Aω f = 0, 1 6 wt(ω) 6 m,
Aω f + Nf 6 2n−1 , ω 6= 0,
(3)
−Aω f + Nf 6 2n−1 , ω 6= 0,
f ∈ {0, 1}n , Nf > 0, Nf öåëîå.
Êðîìå òîãî, ñ ïîìîùüþ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ ìîæíî ðåøàòü çàäà÷è
ìàêñèìèçàöèè íåëèíåéíîñòè íåñáàëàíñèðîâàííûõ ôóíêöèé è êîððåëÿöèîííî èììóííûõ ôóíêöèé. Äëÿ ýòîãî äîñòàòî÷íî óáðàòü èç çàäà÷è 3 ïåðâûå äâà îãðàíè÷åíèÿ èëè
òîëüêî ïåðâîå îãðàíè÷åíèå (â çàâèñèìîñòè îò òîãî, êàêóþ èìåííî çàäà÷ó ìû ðåøàåì) è
10
äîáàâèòü äâà äðóãèõ îãðàíè÷åíèÿ, ïîëó÷åííûå èç ôîðìóëû îáðàùåíèÿ ïðåîáðàçîâàíèé.
Íîâûå îãðàíè÷åíèÿ âûãëÿäÿò ñëóäóþùèì îáðàçîì:
AO f + Nf 6 2n ,
−AO f + Nf 6 0.
Ïðîèëëþñòðèðóåì çàäà÷ó íà ïðîñòîì ïðèìåðå. Ðàññìîòðèì âîïðîñ ìàêñèìèçàöèè
íåëèíåéíîñòè 1-óñòîé÷èâîé ôóíêöèè (m = 1) îò ïÿòè ïåðåìåííûõ (n = 5). Ïîëó÷èì
ñëåäóþùóþ çàäà÷ó:
Nf → sup
A(00000) f = 2n−1 = 16,
A(00001) f = 0,
...
...
...
A(10000) f = 0,
Aω f + Nf 6 16, wt(ω) > 1,
−Aω f + Nf 6 16, wt(ω) > 1.
Ðåøåíèåì ýòîé çàäà÷è ÿâëÿåòñÿ ôóíêöèÿ 4966F18C ñ Nf = 12.
Ïàçàëèêó è Éîõàíññîíó ñ ïîìîùüþ ýòîãî ìåòîäà óäàëîñü ïîñ÷èòàòü íåëèíåéíîñòè
ïðè ïÿòè è øåñòè ïåðåìåííûõ è ïðè óñòîé÷èâîñòè ïîðÿäêà îò åäèíèöû äî ïÿòè. Ïðè
ñåìè ïåðåìåííûõ íåëèíåéíîñòè èì ïîñ÷èòàòü íå óäàëîñü ([1]). Ïîëó÷åííûå ðåçóëüòàòû
ìîæíî ïîñìîòðåòü â òàáëèöå, ïðèâåäåííîé íèæå.
n
5
6
7
0
12
26
*
Óñòîé÷èâîñòü
1
2
3 4
12 8
0 0
24 24 16 0
*
*
* *
5
0
0
0
Òàáëèöà 2. Ìàêñèìàëüíàÿ Nf , ïîëó÷åííàÿ èç ðåøåíèÿ 01 çàäà÷è ÖËÏ. Ñèìâîë *
îçíà÷àåò, ÷òî íåëèíåéíîñòü ïîñ÷èòàòü íå óäàëîñü.
Èçâåñòåí ôàêò, ÷òî ïðè n = 7 è óñòîé÷èâîñòè ïîðÿäêà m ∈ −1 : 1 íåëèíåéíîñòü
ðàâíà 56 ([4]). Äîïîëíèì òàáëèöó 2, ïîñ÷èòàâ ìàêñèìàëüíûå íåëèíåéíîñòè ïðè n = 7
è ïðè m ∈ 2 : 5 ñ ïîìîùüþ ñðåäñòâ MATLAB. Íàïîìíèì, ÷òî ÷åðåç (−1)-óñòîé÷èâóþ
ôóíêöèþ ìû îáîçíà÷àåì ëþáóþ áóëåâó ôóíêöèþ.
n
7
-1
56
Óñòîé÷èâîñòü
0
1
2
3
4
56 56 56 48 32
5
0
Òàáëèöà 3. Ìàêñèìàëüíàÿ Nf ïðè 7 ïåðåìåííûõ, ïîëó÷åííàÿ èç ðåøåíèÿ 01 çàäà÷è
ÖËÏ.
11
Ïðèâåäåì ôóíêöèè, äîñòèãàþùèå ñîîòâåòñòâóþùèå íåëèíåéíîñòè ïðè îïðåäåëåííîì
ïîðÿäêå óñòîé÷èâîñòè.
• D9045715901872031F6894835A11B2FF èìååò -1-óñòîé÷èâîñòü è íåëèíåéíîñòü 56;
• 5261B1504B7D196488F1DF93E31739F8 èìååò 0-óñòîé÷èâîñòü è íåëèíåéíîñòü 56;
• A77567948BE1C94100E2FA9C6D37839E èìååò 1-óñòîé÷èâîñòü è íåëèíåéíîñòü
56;
• 92564DE3E13DAB48BE294678856C719B èìååò 2-óñòîé÷èâîñòü è íåëèíåéíîñòü
56;
• BC16C29743BC3DC216E99768E943683D èìååò 3-óñòîé÷èâîñòü è íåëèíåéíîñòü
48;
• A5965A69695A96A55A69A59696A5695A èìååò 4-óñòîé÷èâîñòü è íåëèíåéíîñòü
32;
Ïî ïðîøåñòâèè äâóõ ÷àñîâ íåïðåðûâíîé ðàáîòû íà êîìïüþòåðå ñ ïðîöåññîðîì Intel(R)
Pentium(R) CPU B980, 2.4 GHz è îïåðàòèâíîé ïàìÿòüþ 4 ÃÁ ïðè âîñüìè ïåðåìåííûõ
è âûøå ïðîãðàììà íà MATLAB'å íå ñìîãëà íàéòè ïëàíû ýòîé çàäà÷è.
12
5
Ïðèáëèæåííûå àëãîðèòìû ïîèñêà áóëåâûõ ôóíêöèé
5.1
Ãåíåòè÷åñêèé àëãîðèòì (GA)
Ãåíåòè÷åñêèé àëãîðèòì ïðåäñòàâëÿåò èç ñåáÿ ìåòîä ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ ñ îãðàíè÷åíèÿìè è áåç îãðàíè÷åíèé, îñíîâàííûé íà ïðîöåññå åñòåñòâåííîãî îòáîðà,
òåì ñàìûì èìèòèðóÿ áèîëîãè÷åñêóþ ýâîëþöèþ. Àëãîðèòì ìíîãîêðàòíî ìîäèôèöèóåò
ïîïóëÿöèþ èíäèâèäóàëüíûõ ðåøåíèé. Íà êàæäîì øàãå ãåíåòè÷åñêîãî àëãîðèòìà ñëó÷àéíûì îáðàçîì âûáèðàþòñÿ îñîáè èç òåêóùåé ïîïóëÿöèè è èñïîëüçóþòñÿ â êà÷åñòâå
ðîäèòåëåé, ÷òîáû ïðîèçâåñòè ïîòîìêîâ äëÿ ñëåäóþùåãî ïîêîëåíèÿ.  òå÷åíèå ïîñëåäóþùèõ ïîêîëåíèé ïîïóëÿöèÿ ¾ýâîëþöèîíèðóåò¿ â ñòîðîíó îïòèìàëüíîãî ðåøåíèÿ.
 ñëåäóþùåé òàáëèöå êðàòêî èçëîæèì îòëè÷èÿ ãåíåòè÷åñêîãî àëãîðèòìà îò êëàññè÷åñêèõ îïòèìèçàöèîííûõ àëãîðèòìîâ:
Êëàññè÷åñêèé àëãîðèòì
Ãåíåòè÷åñêèé àëãîðèòì
Ãåíåðèðóåòñÿ îäíà òî÷êà
íà êàæäîé èòåðàöèè.
Ïîñëåäîâàòåëüíîñòü òàêèõ òî÷åê
ñõîäèòñÿ ê îïòèìàëüíîìó ðåøåíèþ.
Âûáèðàåòñÿ ñëåäóþùàÿ òî÷êà
â ïîñëåäîâàòåëüíîñòè ïóòåì
îïðåäåëåííûõ â àëãîðèòìå âû÷èñëåíèé.
Ãåíåðèðóåòñÿ ïîïóëÿöèÿ òî÷åê
íà êàæäîé èòåðàöèè.
Ëó÷øàÿ òî÷êà â ïîïóëÿöèè
ïðèáëèæàåòñÿ ê îïòèìàëüíîìó ðåøåíèþ.
Âûáèðàåòñÿ ñëåäóþùàÿ ïîïóëÿöèÿ
ïóòåì âû÷èñëåíèé, êîòîðûå
èñïîëüçóþò ãåíåðàöèþ ñëó÷àéíûõ ÷èñåë.
Ãåíåòè÷åñêèé àëãîðèòì ìîæíî èñïîëüçîâàòü äëÿ íàõîæäåíèÿ áóëåâûõ ôóíêöèé ìàêñèìàëüíîé íåëèíåéíîñòè. Äëÿ ýòîé çàäà÷è âîçüìåì â êà÷åñòâå öåëåâîé ôóíêöèè ôóíêöèþ àáñîëþòíîãî ìàêñèìóìà ñðåäè âñåõ êîýôôèöèåíòîâ ÓîëøàÀäàìàðà áóëåâîé ôóíêöèè îò n ïåðåìåííûõ. Íàì íåîáõîäèìî ìèíèìèçèðîâàòü ýòó ôóíêöèþ.
Çàïèøåì öåëåâóþ ôóíêöèþ â àíàëèòè÷åñêîì âèäå ÷åðåç êîýôôèöèåíòû Ôóðüå. Äëÿ
ýòîãî âîñïîëüçóåìñÿ ôîðìóëîé îáðàùåíèÿ ïðåîáðàçîâàíèé. Ìû çíàåì ïî îïðåäåëåíèþ,
÷òî Ff (ω) = Aω f , ãäå Aω ýòî ñòðîêà ìàòðèöû ÓîëøàÀäàìàðà A, ñîîòâåòñòâóþùàÿ
ω . Òàêèì îáðàçîì, öåëåâàÿ ôóíêöèÿ ïðèíèìàåò âèä:
g(x) = max{|2n−1 − AO f |, |Aω1 f |, |Aω2 f |, . . . , |Aω2n −1 f |},
ãäå ω1 , . . . , ω2n −1 ðàçëè÷íûå íåíóëåâûå âåêòîðà äëèíû n.
Çàìåòèì, ÷òî òàêàÿ çàäà÷à áåç îãðàíè÷åíèé íà ñáàëàíñèðîâàííîñòü è ïîðÿäîê óñòîé÷âîñòè. Ñëåäîâàòåëüíî, ðåçóëüòàòîì ãåíåòè÷åñêîãî àëãîðèòìà ìîæåò áûòü íåñáàëàíñèðîâàííàÿ è íå êîððåëÿöèîííî èììóííàÿ ôóíêöèÿ. Åñëè äîïîëíèòåëüíî íàëîæèì íà ýòó
çàäà÷ó ïåðâûå äâà îãðàíè÷åíèÿ èç çàäà÷è 3, òî ìû ñìîæåì íàéòè ñáàëàíñèðîâàííûå è
óñòîé÷èâûå ôóíêöèè âûñîêîé íåëèíåéíîñòè.
Áëàãîäàðÿ ãåíåòè÷åñêîìó àëãîðèòìó áûëè ïîëó÷åíû ñëåäóþùèå ðåçóëüòàòû ïðè
îãðàíè÷åíèè íà êîëè÷åñòâî ïîïóëÿöèé, ðàâíûì 100 · n (áûëè èñïîëüçîâàíû ñðåäñòâà
MATLAB):
13
n
8
9
10
11
12
-1
112
234
474
966
1962
0
110
230
472
964
1950
Óñòîé÷èâîñòü
1
2
3
108 104 98
226 220 218
460 452 448
936 934 922
1924
*
*
4
96
214
448
*
*
5
94
210
444
*
*
Òàáëèöà 4. Íåëèíåéíîñòè, ïîëó÷åííûå ãåíåòè÷åñêèì àëãîðèòìîì2 .
5.2
Àëãîðèòì íàïðàâëåííîãî ïîèñêà (DSA)
Äàëåå ïðèâåä¼ì óíèâåðñàëüíûé àëãîðèòì ïîèñêà ëó÷øèõ áóëåâûõ ôóíêöèé ïî ðàçëè÷íûì êðèòåðèÿì, êàê, íàïðèìåð, íåëèíåéíîñòü, êîððåëÿöèîííàÿ èììóííîñòü è ò.ä.
Àâòîðàìè îí áûë íàçâàí êàê àëãîðèòì íàïðàâëåííîãî ïîèñêà (DSA). Àëãîðèòì
ïðèìå÷àòåëåí òåì, ÷òî íà êàæäîé èòåðàöèè îí óìåíüøàåò ìàêñèìàëüíûé ïî ìîäóëþ
êîýôôèöèåíò ÓîëøàÀäàìàðà, òåì ñàìûì ìàêñèìèçèðóÿ íåëèíåéíîñòü ôóíêöèè îò n
ïåðåìåííûõ.
Êðàòêî îïèøåì ýòîò àëãîðèòì. Ïóñòü äàíà ôóíêöèÿ f (x). Îáîçíà÷èì fˆ(x) = (−1)f (x) .
Ïóñòü fˆ∗ ïîëó÷àåòñÿ èç fˆ èíâåðòèðîâàíèåì (â äàííîì ñëó÷àå, çàìåíîé 1 íà −1 èëè íàîáîðîò) îäíîé èç êîìïîíåíò, ñêàæåì, k -îé.  âåêòîðíîé ôîðìå òàêàÿ îïåðàöèÿ ìîæåò
áûòü ðàññìîòðåíà êàê ïðîñòîå ñóììèðîâàíèå âåêòîðîâ:
fˆ∗ = fˆ + f k ,
ãäå f k ýòî âåêòîð, êîòîðûé ïîëíîñòüþ ñîñòîèò èç íóëåé, çà èñêëþ÷åíèåì k -îé ïîçèöèè,
ãäå ñòîèò 2 èëè −2. Èíâåðòèðîâàíèå k -îé êîìïîíåíòû â fˆ èçìåíèò êàæäûé ýëåìåíò
âåêòîðà Wf íà êîíñòàíòó +2 èëè −2. Îáîçíà÷èì ÷åðåç Wf ∗ âåêòîð êîýôôèöèåíòîâ
ÓîëøàÀäàìàðà ïîñëå èíâåðòèðîâàíèÿ â fˆ. Îí ïîëó÷åí òàêèì îáðàçîì:
Wf ∗ = Afˆ∗ = Afˆ + Af k = Wf + A.k fk ,
ãäå A.k ýòî k -ûé ñòîëáåö ìàòðèöû Àäàìàðà A.
Ïóñòü íà m-îé êîîðäèíàòå âåêòîðà Wf ñòîèò ìàêñèìàëüíûé ïî ìîäóëþ ýëåìåíò
(íàçîâåì åãî Wmax ). Òî åñòü Wmax = |Wf [m]| = max16l62n |Wf [l]|.
Ââåäåì âåêòîð c äëèíû 2n , ñîñòîÿùèé èç 0 è 1. Ýëåìåíò cj ðàâåí 1, åñëè Wmax
óìåíüøàåòñÿ íà 2 ïîñëå èíâåðòèðîâàíèÿ êîìïîíåíòû fˆj .  ïðîòèâíîì ñëó÷àå ýëåìåíò
cj ðàâåí 0. Ñëåäîâàòåëüíî, âîçüìåì òàêèå èíäåêñû sj , j ∈ 1 : p, ïðè êîòîðûõ csj = 1.
Ëþáîé èç ýëåìåíòîâ fˆs1 , . . . , fˆsp ìîæíî èíâåðòèðîâàòü.
Wmax ãàðàíòèðîâàííî óìåíüøèòñÿ ïîñëå èíâåðòèðîâàíèÿ â fˆ, åñëè Wmax äîñòèãàåòñÿ
òîëüêî íà m-îé êîîðäèíàòå. Íî åñëè áîëåå ÷åì îäèí ýëåìåíò â Wf ðàâåí Wmax , òî íå
ôàêò, ÷òî ïîñëå èíâåðòèðîâàíèÿ âñå òàêèå êîýôôèöèåíòû óìåíüøàòñÿ. Êðîìå òîãî,
êîìïîíåíòû â Wf ñî çíà÷åíèåì Wmax − 2 áóäóò äåéñòâîâàòü íåïðåäñêàçóåìî, òî åñòü
áóäóò óâåëè÷èâàòüñÿ èëè óìåíüøàòüñÿ â ñëó÷àéíîì ïîðÿäêå.
2 Ñèìâîë
* îçíà÷àåò, ÷òî ïî ïðîøåñòâèè äâóõ ÷àñîâ íåïðåðûâíîé ðàáîòû íà êîìïüþòåðå ñ ïðîöåñ-
ñîðîì Intel(R) Pentium(R) CPU B980, 2.4 GHz è îïåðàòèâíîé ïàìÿòüþ 4 ÃÁ ïðîãðàììà íà MATLAB'å
íå ñìîãëà íàéòè ôóíêöèè, óäîâëåòâîðÿþùèå îãðàíè÷åíèÿì.
14
×òîáû èçáåæàòü òàêèõ êîëåáàíèé, àëãîðèòì ñîðòèðóåò ýëåìåíòû |Wf [i]| ïî óáûâàíèþ, à çàòåì âûáèðàåò òàêîé èíäåêñ k , ãäå ïîñëå èíâåðòèðîâàíèÿ ýëåìåíòà fˆk óìåíüøàåòñÿ êàê ìîæíî áîëüøåå êîëè÷åñòâî |Wfm |. Çàòåì àëãîðèòì ïðîäîëæàåòñÿ ñ òîé æå
ïðîöåäóðîé, èíâåðòèðóÿ áèòû â òàáëèöå èñòèííîñòè íîâîé ôóíêöèè. Åñëè âîçíèêàåò
ñëó÷àé, êîãäà ïîÿâëÿåòñÿ f (x), êîòîðàÿ áûëà íà ïðåäûäóùèõ øàãàõ, òî ìû âîçâðàùàåìñÿ â íà÷àëî àëãîðèòìà. Òàêîé ñëó÷àé íàçûâàåòñÿ öèêëîì.
Àëãîðèòì íàïðàâëåííîãî ïîèñêà ìîæåò áûòü îïèñàí ñëåäóþùèì îáðàçîì:
1. Ãåíåðèðóåì ñëó÷àéíóþ ñáàëàíñèðîâàííóþ áóëåâó ôóíêöèþ f (x).
2. Âû÷èñëÿåì Wf è ñîðòèðóåì èíäåêñû â Wf òàê: |Wfi1 | > |Wfi2 | > · · · > |Wfi2n |
3. Íàõîäèì èíäåêñ s, ïðè êîòîðîì ìàêñèìèçèðóåòñÿ êîëè÷åñòâî |Wfij |, êîòîðûå áóäóò
óìåíüøàòüñÿ, êîãäà s-é áèò èíâåðòèðîâàí. Èíâåðòèðóåì s-é áèò â f (x).
4. Ïðîâåðèì íåëèíåéíîñòü íîâîãî f (x). Åñëè öèêë îáíàðóæåí (òî åñòü ïîëó÷åíà
ôóíêöèÿ, êîòîðàÿ áûëà íà ïðåäûäóùèõ øàãàõ), ïåðåõîäèì ê øàãó 1, â ïðîòèâíîì
ñëó÷àå ê øàãó 2.
5. Âûâåäåì ëó÷øóþ ïîëó÷åííóþ ôóíêöèþ.
Ðåçóëüòèðóþùàÿ ôóíêöèÿ ìîæåò áûòü íå ñáàëàíñèðîâàííîé è íå êîððåëÿöèîííî
èììóííîé ïîðÿäêà 1, íî åå ìîæíî ïðåâðàòèòü.
Ïóñòü f (x) íåñáàëàíñèðîâàííàÿ ôóíêöèÿ íà Fn . Ïðåäïîëîæèì, ÷òî Wf (ω0 ) = 0
äëÿ íåêîòîðîãî âåêòîðà ω0 6= 0 â Vn . Òîãäà îïðåäåëèì íîâóþ ôóíêöèþ f ∗ (x) = f (x) ⊕
⊕ hx, ω0 i íà Fn , êîòîðàÿ ñáàëàíñèðîâàíà, èìåÿ òó æå ñàìóþ íåëèíåéíîñòü è àëãåáðàè÷åñêóþ ñòåïåíü, êàê è f (x). Î÷åâèäíî, ÷òî íåëèíåéíîñòü è àëãåáðàè÷åñêàÿ ñòåïåíü
îñòàþòñÿ òàêèìè æå, òàê êàê ôóíêöèÿ f ∗ (x) îòëè÷àåòñÿ îò f (x) òîëüêî â ëèíåéíûõ
ñòðîêàõ. Ññûëàÿñü íà îïðåäåëåíèå ïðåîáðàçîâàíèÿ ÓîëøàÀäàìàðà, ìû èìååì,
X
X
∗
Wf ∗ (0) =
(−1)f (x) =
(−1)f (x) (−1)hω0 ,xi = Wf (ω0 ) = 0.
x
x
Òåïåðü ðàññìîòðèì, êàê ïîëó÷èòü êîððåëÿöèîííî èììóííóþ ôóíêöèþ ïîðÿäêà 1. Ïðè
ôèêñèðîâàííîé f (x) îáîçíà÷èì W 0 = {ω : Wf (ω) = 0, ω ∈ Vn }. Ïóñòü B ìàòðèöà
m × n, m 6 n, ÷üè ñòðîêè ýòî ëèíåéíî íåçàâèñèìûå âåêòîðà èç W 0 . Î÷åâèäíî, åñëè m =
n, òî äîñòàòî÷íî ïåðåìåñòèòü âåêòîðà èç B â æåëàåìûå ïîçèöèè, èñïîëüçóÿ ëèíåéíóþ
ìàòðèöó ïðåîáðàçîâàíèé C . Áóëåâà ôóíêöèÿ f (x), äëÿ òîãî, ÷òîáû áûòü êîððåëÿöèîííî
èììóííîé ïîðÿäêà 1, äîëæíà èìåòü íóëè â Wf (ω) äëÿ wt(ω) = 1. Ñëåäîâàòåëüíî, ìû
ïî ñóòè ïåðåìåùàåì íåêîòîðûå òî÷êè èç W 0 â òàêèå n òî÷åê, ãäå wt(ω) = 1, èñïîëüçóÿ
ëèíåéíîå ïðåîáðàçîâàíèå.
Ïóñòü m = n è C = B −1 . Òîãäà îïðåäåëèì íîâóþ ôóíêöèþ f ∗ (x) = f (C · x).
Äîêàæåì, ÷òî f ∗ (x) ÿâëÿåòñÿ êîððåëÿöèîííî èììóííîé ôóíêöèåé ïîðÿäêà 1:
X
X
Wf ∗ (ω) =
(−1)f (C·x) (−1)hω,xi =
(−1)f (x) (−1)hω,B·xi = 0,
x
x
wt(ω) = 1.
Òàêèì îáðàçîì, ôóíêöèþ, ïîëó÷åííóþ â ðåçóëüòàòå ðàáîòû àëãîðèòìà, ìîæíî ïðåâðàòèòü â ñáàëàíñèðîâàííóþ è êîððåëÿöèîííî èììóííóþ ïîðÿäêà 1 ôóíêöèþ, ñîõðàíÿÿ
15
íåëèíåéíîñòü è äðóãèå ñâîéñòâà. Ïðåâðàòèòü ôóíêöèþ â 1-óñòîé÷èâóþ ôóíêöèþ íå
ïîëó÷èòñÿ. Ýòîò ôàêò ïîäòâåðæäàåò ñëåäóþùèé êîíòðïðèìåð.
Ïóñòü ðåçóëüòàòîì àëãîðèòìà ÿâëÿåòñÿ ôóíêöèÿ f îò ïÿòè ïåðåìåííûõ ñî çíà÷åíèÿìè 1141093F íåëèíåéíîñòè 12 (ìàêñèìàëüíàÿ). ż êîýôôèöèåíòû Óîëøà-Àäàìàðà ðàâíû (8, 8, 8, −8, 8, 0, 0, 8, 8, 0, 0, −8, 0, 0, 0, 0, 8, 8, 0, 0, −8, 0, −8, 0, −8, 0, 8, 0, 0, 0, 8, −8). Ïðåâðàòèì ýòó ôóíêöèþ â ñáàëàíñèðîâàííóþ. Âîçüìåì, íàïðèìåð, ω0 = (0, 1, 1, 0, 1). Âèäíî,
÷òî Wf (ω0 ) = 0. Òîãäà îïðåäåëèì ôóíêöèþ f ∗ (x) = f (x) ⊕ hx, ω0 i. Çíà÷åíèÿ ýòîé íîâîé
ôóíêöèè áóäóò òàêèìè: f ∗ = 4BE4539A. Î÷åâèäíî, ÷òî íîâàÿ ôóíêöèÿ ñáàëàíñèðîâàíà.
Áîëåå òîãî, îíà ÿâëÿåòñÿ 1-óñòîéèâîé.
Ïîïðîáóåì ïðåâðàòèòü èñõîäíóþ ôóíêöèþ f â êîððåëÿöèîííî èìóííóþ ôóíêöèþ
ïîðÿäêà 1. Âîçüìåì ïÿòåðêó âåêòîðîâ ω1 = (0, 0, 1, 0, 1), ω2 = (0, 0, 1, 1, 0), ω3 = (0, 1, 0, 0, 1), ω4 =
(1, 0, 0, 1, 1), ω5 = (1, 1, 0, 1, 1), êîòîðûå, î÷åâèäíî, ïðèíàäëåæàò W0 . Ïîñòðîèì èç ýòîé
òðîéêè ìàòðèöó B :
0 0 1 0 1
0 0 1 1 0
B = 0 1 0 0 1 .
1 0 0 1 1
1 1 0 1 1
Ñîîòâåòñòâåííî, ìàòðèöà C = B −1 âûãëÿäèò òàê
è −2 íà 0):
1 1 0 1
0 0 0 1
C = 1 0 1 1
1 1 1 1
0 0 1 1
(ïðåäâàðèòåëüíî çàìåíèì −1 íà 1 è 2
0
1
1 .
1
1
Îïðåäåëèì íîâóþ ôóíêöèþ f ∗ (x) = f (C · x). Çíà÷åíèÿ ýòîé íîâîé ôóíêöèè áóäóò f ∗ =
6944243A, à åå êîýôôèöèåíòû ÓîëøàÀäàìàðà ðàâíû Wf ∗ = (8, 0, 0, 8, 0, 0, 8, 8, 0, 0, 0, 0, 0,
− 8, 0, 8, 0, 8, −8, 0, 0, 0, −8, 8, −8, −8, 8, −8, 0, 8, 0, 8). Âèäíî, ÷òî íîâàÿ ôóíêöèÿ êîððåëÿöèîííî èììóííà ïîðÿäêà 1. Òåïåðü îñòàëîñü ïðåâðàòèòü f ∗ â 1-óñòîé÷èâóþ ôóíêöèþ, òî
åñòü ñäåëàòü èç f ∗ ñáàëàíñèðîâàííóþ ôóíêöèþ, ñîõðàíèâ êîððåëÿöèîííóþ èììóííîñòü.
Âîçüìåì âåêòîð ω0 = (1, 0, 0, 1, 1). Âèäíî, ÷òî Wf ∗ (ω0 ) = 0. Òîãäà îïðåäåëèì ôóíêöèþ f ∗∗ (x) = f ∗ (x) ⊕ hx, ω0 i. Çíà÷åíèÿ ýòîé íîâîé ôóíêöèè áóäóò f ∗∗ = 0F22BDA3, à åå
êîýôôèöèåíòû ÓîëøàÀäàìàðà ðàâíû Wf ∗∗ = (0, −8, 8, 0, 8, −8, 0, 0, −8, 8, −8, −8, 8, 0, 8,
0, 8, 0, 0, 8, 8, 8, 0, 0, 0, 0, 0, 0, 8, 0, −8, 0). Íîâàÿ ôóíêöèÿ ñáàëàíñèðîâàíà, íî íå ÿâëÿåòñÿ
1-óñòîé÷èâîé. Ê ñîæàëåíèþ, îïèñàííûì âûøå ñïîñîáîì íàì íå óäàëîñü ñîõðàíèòü êîððåëÿöèîííóþ èììóííîñòü. Òàêèì îáðàçîì, ïîëó÷èòü 1-óñòîé÷èâóþ ôóíêöèþ òàêèìè
ìåòîäàìè íå âñåãäà âîçìîæíî.
5.2.1
Ïðèìåðû ðàáîòû àëãîðèòìà
Ðàññìîòðèì ðàáîòó àëãîðèòìà íà ïðîñòîì ïðèìåðå. Ìû õîòèì âûâåñòè ôóíêöèþ
ìàêñèìàëüíîé íåëèíåéíîñòè.
Ïðèìåð. Ïóñòü f íà÷àëüíàÿ ñáàëàíñèðîâàííàÿ ôóíêöèÿ îò äâóõ ïåðåìåííûõ
ñî çíà÷åíèÿìè (1, 0, 0, 1). Ïîñ÷èòàåì å¼ êîýôôèöèåíòû ÓîëøàÀäàìàðà. Îíè ðàâíû
(0, 0, 0, −4). Ñîðòèðóåì êîýôôèöèåíòû ïî ìîäóëþ: 4, 0, 0, 0. Çàòåì èíâåðòèðóåì êàæäûé
áèò. Ïðîâåðèì âñå âîçìîæíûå âàðèàíòû.
16
1. f ∗ = (0, 0, 0, 1).Wf ∗ = (2, 2, 2, −2). Ñîðòèðóåì êîýôôèöèåíòû ïî ìîäóëþ: 2, 2, 2, 2.
Îäèí êîýôôèöèåíò ÓîëøàÀäàìàðà óìåíüøèëñÿ.
2. f ∗ = (1, 1, 0, 1).Wf ∗ = (−2, 2, −2, −2). Ñîðòèðóåì êîýôôèöèåíòû ïî ìîäóëþ: 2, 2, 2, 2.
Îäèí êîýôôèöèåíò ÓîëøàÀäàìàðà óìåíüøèëñÿ.
3. f ∗ = (1, 0, 1, 1).Wf ∗ = (−2, −2, 2, −2). Ñîðòèðóåì êîýôôèöèåíòû ïî ìîäóëþ: 2, 2, 2, 2.
Îäèí êîýôôèöèåíò ÓîëøàÀäàìàðà óìåíüøèëñÿ.
4. f ∗ = (1, 0, 0, 0).Wf ∗ = (2, −2, −2, −2). Ñîðòèðóåì êîýôôèöèåíòû ïî ìîäóëþ: 2, 2, 2, 2.
Îäèí êîýôôèöèåíò ÓîëøàÀäàìàðà óìåíüøèëñÿ.
Ó íàñ åñòü ÷åòûðå âàðèàíòà èíâåðòèðîâàíèÿ. Íàïðèìåð, èíâåðòèðóåì â f âòîðîé
áèò. Ïîñ÷èòàåì íåëèíåéíîñòü ïîëó÷åííîé ôóíêöèè. Îíà ðàâíà 1, è îíà ìàêñèìàëüíà.
Çíà÷èò, àëãîðèòì ìîæíî çàâåðøèòü.
5.2.2
Ïðîãðàììà, ðåàëèçóþùàÿ àëãîðèòì
Òåïåðü îïèøåì, êàê ðàáîòàåò ïðîãðàììà, ðåàëèçóþùàÿ àëãîðèòì íàïðàâëåííîãî ïîèñêà. Ïðîãðàììà áûëà íàïèñàíà íà ÿçûêå PASCAL. Ðàññìîòðèì åå ðàáîòó íà íàõîæäåíèå ôóíêöèè ñ ìàêñèìàëüíîé íåëèíåéíîñòüþ.
Ñíà÷àëà ñîçäàåòñÿ òåêñòîâûé ôàéë, â êîòîðîì áóäóò íàõîäèòüñÿ ïðîâåðåííûå ôóíêöèè. Åñëè òàì áûëà êàêàÿ-ëèáî èíôîðìàöèÿ, òî îíà óíè÷òîæàåòñÿ. Äàëåå ââîäèì ñ
êëàâèàòóðû êîëè÷åñòâî ïåðåìåííûõ n. Ïîòîì ñ÷èòàåì êîëè÷åñòâî çíà÷åíèé ôóíêöèè
p = 2n è ìàêñèìàëüíóþ íåëèíåéíîñòü linmax. Ìàêñèìàëüíóþ íåëèíåéíîñòü ìû íàõîäèì ïî ãèïîòåçå 1. Ôîðìóëèðîâêà ãèïîòåçû ñëåäóþùàÿ:
Ãèïîòåçà 1. Ìàêñèìàëüíóþ íåëèíåéíîñòü 1-óñòîé÷èâîé áóëåâîé ôóíêöèè f (x) îò n
ïåðåìåííûõ ìîæíî íàéòè èç ñèñòåìû:
(
Nf =
n
2n−1 − 2 2 ,
2n−1 − 2
n−1
2
n
, n
÷åòíîå;
íå÷åòíîå.
Ãèïîòåçà ïîäòâåðæäàåòñÿ ðåçóëüòàòàìè ðåøåíèÿ çàäà÷è öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ ïðè n ∈ 4 : 7. Òàêèìè æå äîâîäàìè ðóêîâîäñòâîâàëèñü Ïàçàëèê è Éîõàíññîí
(ñì. [1]).
Òåïåðü ðàññìîòðèì ðàáîòó öèêëà, êîòîðûé ðåàëèçóåò âñå øàãè àëãîðèòìà íàïðàâëåííîãî ïîèñêà. Ñíà÷àëà ñ ïîìîùüþ ïðîöåäóðû balance ãåíåðèðóåì ñëó÷àéíóþ ñáàëàíñèðîâàííóþ áóëåâó ôóíêöèþ. Ñîçäàåòñÿ ñòðîêà, ñîñòîÿùàÿ èç èäóùèõ ïîäðÿä åäèíèö
è íóëåé, êîëè÷åñòâî êîòîðûõ îäèíàêîâî. Äëèíà ýòîé ñòðîêè ðàâíà p. Äàëåå ñëó÷àéíûì
îáðàçîì âûáèðàåì èíäåêñ ñòðîêè è çàïèñûâàåì ñîîòâåòñòâóþùåå åìó ÷èñëî â ôóíêöèþ f ïî ïîðÿäêó. Óäàëÿåì âçÿòîå ÷èñëî èç ñòðîêè. Çàòåì ñíîâà âûáèðàåì ñëó÷àéíûé
èíäåêñ ñòðîêè. È òàê äàëåå. Çàïèñûâàåì ïîëó÷åííóþ ôóíêöèþ â ôàéë. Ñ÷èòàåì êîýôôèöèåíòû Óîëøà-Àäàìàðà ïîëó÷åííîé ôóíêöèè, ïîìåùàåì èõ â ìîäóëè è ñîðòèðóåì.
Èíâåðòèðóåì êàæäûé áèò ôóíêöèè, ïîñ÷èòàåì êîýôôèöèåíòû Óîëøà-Àäàìàðà êàæäîé ïîëó÷åííîé ôóíêöèè, àíàëîãè÷íûì îáðàçîì èõ óïîðÿäî÷èì è çàïèøåì ðåçóëüòàòû.
Òåïåðü áóäåì ñðàâíèâàòü êîýôôèöèåíòû Óîëøà-Àäàìàðà ñòàðîé ôóíêöèè è èíâåðòèðîâàííûõ ôóíêöèé. Âûáèðàåì òàêóþ èíâåðòèðîâàííóþ ôóíêöèþ, ó êîòîðîé êîëè÷åñòâî
óìåíüøåííûõ êîýôôèöèåíòîâ ìàêñèìàëüíî.
17
À òåïåðü íàäî ïðîâåðèòü, áûëà ëè ýòà ôóíêöèÿ íà ïðåäûäóùèõ øàãàõ èëè íåò. Äëÿ
ýòîãî ïðîãîíÿåì å¼ ïî ôóíêöèÿì, êîòîðûå çàïèñàíû â ôàéëå. Åñëè òàêàÿ ôóíêöèÿ óæå
áûëà, òî çàïèñûâàåì â ëîãè÷åñêóþ ïåðåìåííóþ f lag çíà÷åíèå f alse, â ïðîòèâíîì ñëó÷àå
çàïèñûâàåì çíà÷åíèå true.
Åñëè çíà÷åíèå f lag ÿâëÿåòñÿ ëîæüþ, òî âîçâðàùàåìñÿ ê øàãó 1, òî åñòü çàíîâî ãåíåðèðóåì ñëó÷àéíóþ áóëåâó ôóíêöèþ. Åñëè çíà÷åíèå f lag ÿâëÿåòñÿ èñòèíîé, òî ñ÷èòàåì
å¼ íåëèíåéíîñòü è ñðàâíèâàåì ñ ìàêñèìàëüíîé íåëèíåéíîñòüþ linmax. Åñëè îíà ðàâíà
linmax, òî âûâîäèì ðåçóëüòèðóþùóþ ôóíêöèþ è å¼ íåëèíåéíîñòü è çàâåðøàåì ðàáîòó
àëãîðèòìà.  ïðîòèâíîì ñëó÷àå âîçâðàùàåìñÿ â íà÷àëî öèêëà.
5.3
Ðåçóëüòàòû àëãîðèòìà
Ïðè ïÿòè ïåðåìåííûõ áûëè ïîëó÷åíû òàêèå ôóíêöèè:
• BF7931AD ôóíêöèÿ íå ñáàëàíñèðîâàíà, íå êîððåëÿöèîííî èììóííà è èìååò
íåëèíåéíîñòü 12.
• E3625D4A ôóíêöèÿ ñáàëàíñèðîâàíà, íå êîððåëÿöèîííî èììóííà è èìååò íåëèíåéíîñòü 12.
Ïðè øåñòè ïåðåìåííûõ áûëè ïîëó÷åíû òàêèå ôóíêöèè:
• 28D319895790FECE ôóíêöèÿ ñáàëàíñèðîâàíà, íå êîððåëÿöèîííî èììóííà è
èìååò íåëèíåéíîñòü 24.
• 9DB12186B2D61505 ôóíêöèÿ íå ñáàëàíñèðîâàíà, íå êîððåëÿöèîííî èììóííà è
èìååò íåëèíåéíîñòü 24.
18
Çàêëþ÷åíèå
 ðàáîòå áûëè ïðåäñòàâëåíû è ïðîàíàëèçèðîâàíû íåêîòîðûå ðåçóëüòàòû ïî íåëèíåéíîñòè óñòîé÷èâûõ áóëåâûõ ôóíêöèé â îïðåäåëåííûõ ñëó÷àÿõ. Áûëè ðàçîáðàíû ýôôåêòèâíûå ìåòîäû ìàêñèìèçàöèè íåëèíåéíîñòè ïðè íàëè÷èè ëèíåéíûõ îãðàíè÷åíèé è
ïîñòðîåíèÿ óñòîé÷èâûõ ôóíêöèé ñ âûñîêîé íåëèíåéíîñòüþ. Âî âòîðîé ÷àñòè ñòàòüè áûëè ðàññìîòðåíû ãåíåòè÷åñêèé àëãîðèòì è àëãîðèòì íàïðàâëåííîãî ïîèñêà. Àëãîðèòì
íàïðàâëåííîãî ïîèñêà ïðåäëîæåí êàê î÷åíü ýôôåêòèâíûé â ïîèñêå âûñîêî íåëèíåéíûõ
áóëåâûõ ôóíêöèé, êîòîðûå ÿâëÿþòñÿ ñáàëàíñèðîâàííûìè èëè êîððåëÿöèîííî èììóííûìè ïîðÿäêà 1. ×àñòü àëãîðèòìîâ áûëè çàïðîãðàììèðîâàíû. Òàêæå áûëè ïðèâåäåíû
ïðèìåðû ôóíêöèé è ðåçóëüòàòû îïèñàííûõ ìåòîäîâ.
19
Ñïèñîê ëèòåðàòóðû
[1] E. Pasalic, T. Johansson ¾Further Results on the Relation Between Nonlinearity and
Resiliency for Boolean Functions¿ 7th IMA International Conference In Cryptography
and Coding / Lecture Notes in Computer Science, 1746, 10 p., 1999.
[2] S. Chee, S. Lee, D. Lee, S.H. Sung ¾On the Correlation Immune Functions and Their
Nonlinearity¿ Advances in Cryptology ASIACRYPT '96, Lecture Notes in Computer
Science, 1163, 235242 pp., SpringerVerlag, 1996.
[3] Â.Í. Ìàëîç¼ìîâ ¾Äèñêðåòíûå ôóíêöèè Óîëøà¿ Ñåìèíàð ïî äèñêðåòíîìó ãàðìîíè÷åñêîìó àíàëèçó è ãåîìåòðè÷åñêîìó ìîäåëèðîâàíèþ ¾DHA & CAGD¿, 10 ñ., 2011.
[4] Î.À. Ëîãà÷åâ, À.À. Ñàëüíèêîâ., Â.Â. ßùåíêî. ¾Áóëåâû ôóíêöèè â òåîðèè êîäèðîâàíèÿ è êðèïòîëîãèè¿ Ì.: Ìîñêîâñêèé öåíòð íåïðåðûâíîãî ìàòåìàòè÷åñêîãî îáðàçîâàíèÿ, 303314 cñ., 2004.
[5] S. Maitra, E. Pasalic ¾Further Constructions of Resilient Boolean Functions With Very
High Nonlinearity¿ IEEE Transactions on Information Theory, Vol. 48, No. 7, 1825
1834 pp., 2002.
[6] Þ.Â. Òàðàííèêîâ. ¾Êîìáèíàòîðíûå ñâîéñòâà äèñêðåòíûõ ñòðóêòóð è ïðèëîæåíèÿ
ê êðèïòîëîãèè¿ Ìîñêâà, Èçäàòåëüñòâî ÌÖÍÌÎ, 141142 ññ., 2014.
[7] MATLAB Help ¾Genetic Algorithm¿. The Mathworks, Inc. Âåðñèÿ MATLAB R2015b.
20
Отзывы:
Авторизуйтесь, чтобы оставить отзыв