turkmath.org

Türkiye'deki Matematiksel Etkinlikler


20 Mart 2018, 15:40


Orta Doğu Teknik Üniversitesi Uygulamalı Matematik Enstitüsü Seminerleri

The Multiplicative Complexity of 6-variable Boolean Functions

Çağdaş Çalık
The National Institute of Standards and Technology (NIST), USA, Türkiye

The multiplicative complexity of a Booleanfunction is the minimum number of AND gates that are necessary and sufficientto implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable,even for functions with small number of inputs. Turan et al. showed thatn-variable Boolean functions can be implemented with at most n-1 AND gates forn < 6. A counting argument can be used to show that, for n > 6, thereexist n-variable Boolean functions with multiplicative complexity of at leastn. In this talk, we will describe a method to find the multiplicativecomplexity of Boolean functions by analyzing circuits with a particular numberof AND gates and utilizing the affine equivalence of functions. We use thismethod to study the multiplicative complexity of 6-variable Boolean functions,and calculate the multiplicative complexities of all 150,357 affine equivalence classes. We showthat any 6-variable Boolean function can be implemented using at most 6 ANDgates. Additionally, we exhibit specific 6-variable Boolean functions whichhave multiplicative complexity 6.

Şifreleme ve Bilgi Güvenliği İngilizce
Institute of Applied Mathematics, S212

ume 17.03.2018

Yaklaşan Seminerler Seminer Arşivi
 

İLETİŞİM

Akademik biriminizin ya da çalışma grubunuzun ülkemizde gerçekleşen etkinliklerini, ilan etmek istediğiniz burs, ödül, akademik iş imkanlarını veya konuk ettiğiniz matematikçileri basit bir veri girişi ile kolayca turkmath.org sitesinde ücretsiz duyurabilirsiniz. Sisteme giriş yapmak için gerekli bilgileri almak ya da görüş ve önerilerinizi bildirmek için iletişime geçmekten çekinmeyiniz.

Özkan Değer ozkandeger@gmail.com

DESTEK VERENLER

ja2019

31. Journees Arithmetiques Konferansı Organizasyon Komitesi

Web sitesinin masraflarının karşılanması ve hizmetine devam edebilmesi için siz de bağış yapmak, sponsor olmak veya reklam vermek için lütfen iletişime geçiniz.

ONLİNE ZİYARETÇİLER


©2013-2020 turkmath.org
Tüm hakları saklıdır