{"id":283451,"date":"2017-01-06T21:25:04","date_gmt":"2017-01-06T18:25:04","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=283451"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=283451","title":{"rendered":"\u041f\u043e\u043b\u0435 \u0413\u0430\u043b\u0443\u0430 \u043d\u0430 Scala"},"content":{"rendered":"<h2>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h2>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0430 \u0442\u0435\u043c\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c\u0438 \u043f\u043e\u043b\u044f\u043c\u0438 (\u0438\u043b\u0438 \u043f\u043e\u043b\u044f\u043c\u0438 \u0413\u0430\u043b\u0443\u0430), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0442\u0435\u043e\u0440\u0438\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u043d\u0430\u0443\u043a\u0430\u0445, \u0442.\u0435. \u0438\u043c\u0435\u044e\u0442 \u0448\u0438\u0440\u043e\u043a\u043e\u0435 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435.<br \/>  \u0421\u0443\u0445\u0443\u044e \u0442\u0435\u043e\u0440\u0438\u044e \u043e \u0433\u0440\u0443\u043f\u043f\u0430\u0445\/\u043a\u043e\u043b\u044c\u0446\u0430\u0445\/\u043f\u043e\u043b\u044f\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 <a href=\"http:\/\/math-deque.rhcloud.com\/articles\/index\/article_id\/pole_galua\">\u041f\u043e\u043b\u044f \u0413\u0430\u043b\u0443\u0430<\/a>, \u0430 \u0437\u0434\u0435\u0441\u044c \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0438 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Scala.<\/p>\n<h2>\u0422\u0438\u043f\u044b \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0431\u0441\u0443\u0434\u0438\u0442\u044c \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0435 \u0441 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0441 \u0443\u0447\u0435\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0442\u0438\u043f\u0430 <b><i>Int<\/i><\/b> \u0432 \u044f\u0437\u044b\u043a\u0435 Scala. \u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043d\u0438\u0436\u0435.<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0422\u0438\u043f <b><i>Int<\/i><\/b> \u0432 Scala\/Java \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 32 \u0431\u0438\u0442\u0430<\/li>\n<li>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0431\u0438\u0442\u044b: 0..30 \u2014 31, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 32-\u043e\u0439 \u0431\u0438\u0442 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u043a\u043e\u0432\u044b\u043c<\/li>\n<li>\u041f\u043e\u043b\u0438\u043d\u043e\u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0432 \u0434\u0438\u0430\u043f\u043e\u0437\u043e\u043d\u0435 0..29<\/li>\n<li>\u041d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b (\u0438\u043b\u0438 \u043c\u043e\u0434\u0443\u043b\u0438) \u0438\u043c\u0435\u044e\u0442 \u0434\u0438\u0430\u043f\u043e\u0437\u043e\u043d 1..30<\/li>\n<li>\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043f\u043e\u043b\u0435 \u0438\u043c\u0435\u0435\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/529\/d0b\/3da\/529d0b3dad052795b0a3c71b8fa2537f.gif\" title=\"q=2^m\"\/> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/li>\n<\/ul>\n<h2>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043e\u043f\u0438\u0448\u0435\u043c \u043a\u043b\u0430\u0441\u0441 <b><i>Polynomial<\/i><\/b>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u0438 4 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438.<br \/>  \u042d\u0442\u043e\u0442 \u0432\u0438\u0434 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u00ab\u043f\u043e\u043b\u0443\u0444\u0430\u0431\u0440\u0438\u043a\u0430\u0442\u043e\u043c\u00bb \u0438 \u043d\u0435 \u043f\u0440\u0438\u0432\u044f\u0437\u0430\u043d \u043a \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c\u0443 \u043f\u043e\u043b\u044e.<\/p>\n<p>  <a name=\"habracut\"><\/a>  <\/p>\n<pre><code class=\"scala\">class Polynomial(_p: Int) {   val polynomial: Int = _p    def order: Int =  = {     ...   }    def mul(p: Polynomial): Polynomial = {     ...   }   def div(p: Polynomial): (Int, Int)  = {     ...   }   def add(p: Polynomial): Polynomial = {     ...   }   def sub(p: Polynomial): Polynomial = {     ...   }    override def toString: String = Integer.toBinaryString(this.polynomial) } <\/code><\/pre>\n<p>  <\/p>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441 <b><i>FiniteField<\/i><\/b>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u0435\u043c \u043f\u043e\u043b\u0435\u0439 \u0413\u0430\u043b\u0443\u0430<br \/>  \u0412\u043d\u0443\u0442\u0440\u0438 <b><i>FiniteField<\/i><\/b> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0439 \u043a\u043b\u0430\u0441\u0441 <b><i>FiniteFieldPolynomial<\/i><\/b>, \u0442\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0442\u044c \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438 \u043f\u0440\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439.<br \/>  \u0411\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u044f.<br \/>  \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0447\u043b\u0435\u043d <b><i>modulo<\/i><\/b>, \u044d\u0442\u043e \u043c\u043e\u0434\u0443\u043b\u044c (\u0438\u043b\u0438 \u0436\u0435 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c) \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u043e\u043b\u044f.<\/p>\n<p>  <cut\/>  <\/p>\n<pre><code class=\"scala\">abstract class FiniteField(_initBitNumber: Int) {   type T &lt;: Polynomial   type GFPolynomial &lt;: FiniteFieldPolynomial    protected val checkBitNumber: Int =&gt; Int = ???   val modulo: T   val bits: Int = checkBitNumber(_initBitNumber)    protected def createModulo(): Option[Int]   def createPolynomial(_initPolynomial: Int): FiniteFieldPolynomial    abstract class FiniteFieldPolynomial {      protected val p: T     def +(other: GFPolynomial): GFPolynomial     def -(other: GFPolynomial): GFPolynomial = {       this + other     }     def *(other: GFPolynomial): GFPolynomial     def \/(other: GFPolynomial): GFPolynomial = this * other.mulInverse     def addInverse: GFPolynomial = self     def mulInverse: GFPolynomial     def self: GFPolynomial   } } <\/code><\/pre>\n<p>  <\/p>\n<p>\u0412\u0430\u0436\u043d\u044b\u043c \u044d\u0442\u0430\u043f\u043e\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u044f \u0413\u0430\u043b\u0443\u0430 \u0435\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043f\u043e\u043b\u044f, \u0430 \u0442\u0430\u043a \u0436\u0435 \u0432\u044b\u0431\u043e\u0440 \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437 \u043d\u0438\u0445. \u0421 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0439 \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430 \u043c\u043e\u0436\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 <a href=\"http:\/\/math-deque.rhcloud.com\/articles\/index\/article_id\/neprivodimiy_mnogochlen\">\u041d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b<\/a>.<br \/>  \u041d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u044f, \u0442\u043e\u0447\u043d\u043e \u0442\u0430\u043a \u0436\u0435 \u043a\u0430\u043a \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/d6c\/0b6\/fa9\/d6c0b6fa93ae2811419f3d8880a2ac1c.gif\" title=\"Z_p\"\/>.<br \/>  \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u044b\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b \u0438\u0433\u0440\u0430\u044e\u0442 \u0442\u0443 \u0436\u0435 \u0440\u043e\u043b\u044c \u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432, \u0447\u0442\u043e \u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u0445 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b.<br \/>  \u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u0434 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043d\u0438\u0436\u0435.<\/p>\n<p>  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439:  <\/p>\n<ol>\n<li>\u0435\u0441\u043b\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a deg \u0440\u0430\u0432\u0435\u043d 1, \u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442\u044c \u0433\u043e\u0442\u043e\u0432\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 1<\/li>\n<li>\u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0431\u043e\u043b\u0435\u0435 1:<br \/> \n<ol>\n<li>\u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <b><i>deg<\/i><\/b> (\u043f\u0443\u0441\u0442\u044c <b><i>P<\/i><\/b> \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u044d\u0442\u0438\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432)<\/li>\n<li>\u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u043f\u0438\u0441\u043e\u043a \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/aae\/33d\/d14\/aae33dd145b30b627dae495137cda206.gif\" title=\"\\dfrac{deg}{2}\"\/> (\u043f\u0443\u0441\u0442\u044c <b><i>G<\/i><\/b> \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u044d\u0442\u0438\u0445 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432)    <\/li>\n<li>\u0435\u0441\u043b\u0438 \u043f\u043e\u043b\u0438\u043d\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/7f4\/0eb\/f53\/7f40ebf5361c2e7d3074b1bb9001787c.gif\" title=\"p_{i}\"\/> \u043d\u0435 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u0431\u0435\u0437 \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043d\u0438 \u043d\u0430 \u043e\u0434\u0438\u043d \u043f\u043e\u043b\u0438\u043d\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/079\/69c\/733\/07969c7332bd9d8b2869d69e411663c8.gif\" title=\"g_{i}\"\/>, \u0442\u043e \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u043c, \u0437\u043d\u0430\u0447\u0438\u0442 \u043d\u0443\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/7f4\/0eb\/f53\/7f40ebf5361c2e7d3074b1bb9001787c.gif\" title=\"p_{i}\"\/> \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432-\u043c\u043e\u0434\u0443\u043b\u0435\u0439<\/li>\n<\/ol>\n<p>  <cut\/>  <\/p>\n<pre><code class=\"scala\">object IrreduciblePolynomials{  \tprivate def check(p: Int, list: List[Int]): Boolean = { \t\tval pol = Polynomial(p) \t\tlist.foreach((item: Int) =&gt; { \t\t\tval i = Polynomial(item) \t\t\tif ((pol div i)._2 == 0){ \t\t\t\treturn false \t\t\t} \t\t}) \t\ttrue \t}  \tdef calcIrreducible(deg :Int): List[Int] = { \t\tif (deg == 1) return List[Int](2, 3) \t\t\/\/ d &gt; 2 \t\tvar resultList = ListBuffer[Int]() \t\t\/\/ generate all polynomials of degree d \t\tval n = 1 &lt;&lt; deg \t\tfor(i &lt;- 0 until n){ \t\t\tval t = i ^ n\t\t\/\/ polynomial of P set, for testing \t\t\tval list: List[Int] = calcIrreducible(deg &gt;&gt; 1) \t\t\tif (check(t, list)) resultList += t \t\t} \t\tresultList.toList \t} } <\/code><\/pre>\n<p>  <\/p>\n<p>\u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u043a\u043b\u0430\u0441\u0441-\u043d\u0430\u0441\u043b\u0435\u0434\u043d\u0438\u043a <b><i>FiniteField<\/i><\/b>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0433\u043e\u0442\u043e\u0432\u044b\u043c \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c \u043f\u043e\u043b\u0435\u043c.<\/p>\n<p>  <cut\/>  <\/p>\n<pre><code class=\"scala\">class GaloisField(_initBitNumber: Int = FiniteField.DEFAULT_BIT_NUMBER) extends FiniteField(_initBitNumber) {   override val modulo: Polynomial = ...    protected def createModulo(): Option[Int] = {     val list = IrreduciblePolynomials(this.bits)     list.headOption   }    def createPolynomial(_initPolynomial: Int): GFPolynomial = {     ...   }   def createPolynomial(_binInitPolynomial: String): GFPolynomial = {     ...   }    class GFPolynomial private[GaloisField](_p: Int, _m: Int) extends FiniteFieldPolynomial with Comparable[GFPolynomial]{     override def equals(other: Any): Boolean = other match {       case other: GFPolynomial =&gt; this.p.polynomial == other.p.polynomial       case _ =&gt; false     }      override protected val p = Polynomial(_p) \t     def this(other: GFPolynomial){       this(other.p.polynomial, bits)     }     override def self: GFPolynomial = this      override def +(other: GFPolynomial): GFPolynomial = {       GFPolynomial(this.p.polynomial ^ other.p.polynomial, bits)     }     override def -(other: GFPolynomial): GFPolynomial = {  \/\/ In this case add and subtract are the same       this + other     }      override def *(other: GFPolynomial): GFPolynomial = {       val result: Polynomial = this.p mul other.p       if (result.order &gt;= bits){         GFPolynomial((result div modulo)._2, bits)       }       else GFPolynomial(result.polynomial, bits)     }      override def mulInverse: GFPolynomial = {       if (p.polynomial == 0)         throw new NoSuchElementException(&quot;Error: there is no multiplicative inverse for zero&quot;)       var r1: Polynomial = Polynomial(modulo.polynomial)       var r2: Polynomial = this.p       var s1 = Polynomial(1)       var s2 = Polynomial(0)       var t1 = Polynomial(0)       var t2 = Polynomial(1)       var t = Polynomial(0)       var s = Polynomial(0)       var r = Polynomial(0)       while(r2.polynomial &gt; 0){         val q: Polynomial = Polynomial((r1 div r2)._1)         r = r1 sub (q mul r2)         r1 = r2; r2 = r         s = s1 sub (q mul s2); s1 = s2; s2 = s         t = t1 sub (q mul t2); t1 = t2; t2 = t       }       GFPolynomial(t1.polynomial, bits)     }   } } <\/code><\/pre>\n<p>  <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u00ab\u0432\u044b\u043b\u0435\u0437\u0442\u0438\u00bb \u0437\u0430 \u0440\u0430\u043c\u043a\u0438 \u043f\u043e\u043b\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0438\u043d\u043e\u0433\u0434\u0430 \u043d\u0430\u0434\u043e \u0434\u0435\u043b\u0438\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0430 \u043c\u043e\u0434\u0443\u043b\u044c \u043f\u043e\u043b\u044f.<br \/>  \u0417\u0430\u043c\u0435\u0442\u044c\u0442\u0435 \u043a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e \u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u043e\u043d\u043e \u0435\u0441\u0442\u044c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 <b><i>a<\/i><\/b> \u043d\u0430 \u043c\u0443\u043b\u044c\u0442\u0438\u043f\u043b\u0438\u043a\u0430\u0442\u0438\u0432\u043d\u0443\u044e \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u044e <b><i>b<\/i><\/b>.<br \/>  \u0412 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438\u043d\u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0435\u043b\u0435\u043d\u0438\u044f, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0432 \u043a\u043b\u0430\u0441\u0441\u0435 <b><i>Polynomial<\/i><\/b>.<\/p>\n<p>  <\/p>\n<h2>\u0412\u044b\u0432\u043e\u0434<\/h2>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u043b\u0430\u0441\u044c \u0441\u0430\u043c\u043e\u0434\u0435\u043b\u044c\u043d\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u043e\u043b\u0435\u0439 \u0413\u0430\u043b\u0443\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0430 \u043f\u0443\u0442\u0435\u043c \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u043f\u043e\u043b\u044f (\u0432\u043c\u0435\u0441\u0442\u043e <b><i>Int<\/i><\/b> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u0438\u043d\u043d\u0443\u044e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u0438\u043b\u0438 \u0447\u0442\u043e \u0442\u043e \u0432 \u044d\u0442\u043e\u043c \u0440\u043e\u0434\u0435).<br \/>  \u0414\u0430\u043d\u043d\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u0435\u043d \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u0430\u043c \u0438 \u0432\u0441\u0435\u043c \u043a\u043e\u043c\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430 \u0442\u0435\u043c\u0430 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u043e\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u044b, \u043f\u043e\u043b\u0435\u0439 \u0438 \u0442\u0435\u043e\u0440\u0438\u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<br \/>  \u041f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043d\u0430 <a href=\"https:\/\/github.com\/mathsatan\/galois\">githab&#8217;\u0435<\/a><\/p>\n<\/li>\n<\/ol>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habrahabr.ru\/post\/319050\/\"> https:\/\/habrahabr.ru\/post\/319050\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<h2>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h2>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0430 \u0442\u0435\u043c\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c\u0438 \u043f\u043e\u043b\u044f\u043c\u0438 (\u0438\u043b\u0438 \u043f\u043e\u043b\u044f\u043c\u0438 \u0413\u0430\u043b\u0443\u0430), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0442\u0435\u043e\u0440\u0438\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438 \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u043d\u0430\u0443\u043a\u0430\u0445, \u0442.\u0435. \u0438\u043c\u0435\u044e\u0442 \u0448\u0438\u0440\u043e\u043a\u043e\u0435 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435.<br \/>  \u0421\u0443\u0445\u0443\u044e \u0442\u0435\u043e\u0440\u0438\u044e \u043e \u0433\u0440\u0443\u043f\u043f\u0430\u0445\/\u043a\u043e\u043b\u044c\u0446\u0430\u0445\/\u043f\u043e\u043b\u044f\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 <a href=\"http:\/\/math-deque.rhcloud.com\/articles\/index\/article_id\/pole_galua\">\u041f\u043e\u043b\u044f \u0413\u0430\u043b\u0443\u0430<\/a>, \u0430 \u0437\u0434\u0435\u0441\u044c \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0438 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Scala.<\/p>\n<h2>\u0422\u0438\u043f\u044b \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0431\u0441\u0443\u0434\u0438\u0442\u044c \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0435 \u0441 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0432 \u043f\u0430\u043c\u044f\u0442\u0438, \u0441 \u0443\u0447\u0435\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0442\u0438\u043f\u0430 <b><i>Int<\/i><\/b> \u0432 \u044f\u0437\u044b\u043a\u0435 Scala. \u0422\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u043d\u0438\u0436\u0435.<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0422\u0438\u043f <b><i>Int<\/i><\/b> \u0432 Scala\/Java \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 32 \u0431\u0438\u0442\u0430<\/li>\n<li>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0431\u0438\u0442\u044b: 0..30 \u2014 31, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 32-\u043e\u0439 \u0431\u0438\u0442 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u043a\u043e\u0432\u044b\u043c<\/li>\n<li>\u041f\u043e\u043b\u0438\u043d\u043e\u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0432 \u0434\u0438\u0430\u043f\u043e\u0437\u043e\u043d\u0435 0..29<\/li>\n<li>\u041d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u044b (\u0438\u043b\u0438 \u043c\u043e\u0434\u0443\u043b\u0438) \u0438\u043c\u0435\u044e\u0442 \u0434\u0438\u0430\u043f\u043e\u0437\u043e\u043d 1..30<\/li>\n<li>\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043f\u043e\u043b\u0435 \u0438\u043c\u0435\u0435\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/529\/d0b\/3da\/529d0b3dad052795b0a3c71b8fa2537f.gif\" title=\"q=2^m\"\/> \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/li>\n<\/ul>\n<h2>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043e\u043f\u0438\u0448\u0435\u043c \u043a\u043b\u0430\u0441\u0441 <b><i>Polynomial<\/i><\/b>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u0438 4 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438.<br \/>  \u042d\u0442\u043e\u0442 \u0432\u0438\u0434 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u00ab\u043f\u043e\u043b\u0443\u0444\u0430\u0431\u0440\u0438\u043a\u0430\u0442\u043e\u043c\u00bb \u0438 \u043d\u0435 \u043f\u0440\u0438\u0432\u044f\u0437\u0430\u043d \u043a \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c\u0443 \u043f\u043e\u043b\u044e.<\/p>\n<p>  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-283451","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/283451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=283451"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/283451\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=283451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=283451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=283451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}