A355891 -id:A355891 - cp's OEIS frontend

A048631 Xfactorials - like factorials but use carryless GF(2)[ X ] polynomial multiplication.

1, 1, 2, 6, 24, 120, 272, 1904, 15232, 124800, 848640, 7507200, 39738368, 433441792, 2589116416, 30419859456, 486717751296, 8128101580800, 132557598294016, 1971862458400768, 30421253686034432, 512675443057623040, 7176891455747129344, 130521457800367308800

Offset: 0

Antti Karttunen, Jul 14 1999

In formula X stands for the multiplication in a ring of GF(2)[ X ] polynomials.

Vaclav Kotesovec, Table of n, a(n) for n = 0..475
Vaclav Kotesovec, Graph a(n+1)/a(n)

Cf. A000142, A048720, A048632, A061922.

Xfactorial := proc(n) option remember; if n=0 then 1
                else Xmult(n, Xfactorial(n-1)) fi
              end:
Xmult := proc(n, m) option remember; if n=0 then 0
           else Bits[Xor](((n mod 2)*m), Xmult(floor(n/2), m*2)) fi
         end:
seq(Xfactorial(n), n=0..23);

Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; s];
Xfactorial[n_] := Xfactorial[n] = If[0 == n, 1, Xmult[n, Xfactorial[n - 1]] ];
Table[Xfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Mar 04 2016, updated Mar 06 2016 after Maple *)

a(n)=my(s=Mod(1,2)); for(k=1,n, s*=Pol(binary(k))); fromdigits(Vec(lift(s)), 2) \\ Charles R Greathouse IV, Oct 03 2016

a(0) = 1, a(n) = n X a(n-1) (see the Maple function Xfactorial given below).

Using the notations introduced in A355891, we have a(n) = ivgenpoly(Product_{i=1..n} genpoly(n)). As an example, n = 6 corresponds to 1*x*(x+1)*x^2*(x^2+1)*(x^2+x) = x^8+x^4 in GF(2)[x], so a(6) = 2^8 + 2^4 = 272. - Jianing Song, Sep 30 2022

A354500 The Rijndael S-box used in the Advanced Encryption Standard (AES).

Original entry on oeis.org

99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226

Offset: 0

Jianing Song, Aug 15 2022

A permutation of {0, 1, ..., 255}.

The permutation can be decomposed into 5 cycles: 4, 242, 137, 167, ..., 48 (length 87); 1, 124, 16, 202, ..., 9 (length 81); 0, 99, 251, 15, ..., 82 (length 59); 11, 43, 241, 161, ..., 158 (length 27); 115, 143 (length 2).

			The Rijndael S-box written in hexadecimal:
     +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +A +B +C +D +E +F
  00 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76
  10 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0
  20 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15
  30 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75
  40 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84
  50 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF
  60 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8
  70 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2
  80 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73
  90 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB
  A0 E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79
  B0 E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08
  C0 BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A
  D0 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E
  E0 E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF
  F0 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16
The Rijndael S-box written in decimal:
       +0  +1  +2  +3  +4  +5  +6  +7  +8  +9 +10 +11 +12 +13 +14 +15
    0  99 124 119 123 242 107 111 197  48   1 103  43 254 215 171 118
   16 202 130 201 125 250  89  71 240 173 212 162 175 156 164 114 192
   32 183 253 147  38  54  63 247 204  52 165 229 241 113 216  49  21
   48   4 199  35 195  24 150   5 154   7  18 128 226 235  39 178 117
   64   9 131  44  26  27 110  90 160  82  59 214 179  41 227  47 132
   80  83 209   0 237  32 252 177  91 106 203 190  57  74  76  88 207
   96 208 239 170 251  67  77  51 133  69 249   2 127  80  60 159 168
  112  81 163  64 143 146 157  56 245 188 182 218  33  16 255 243 210
  128 205  12  19 236  95 151  68  23 196 167 126  61 100  93  25 115
  144  96 129  79 220  34  42 144 136  70 238 184  20 222  94  11 219
  160 224  50  58  10  73   6  36  92 194 211 172  98 145 149 228 121
  176 231 200  55 109 141 213  78 169 108  86 244 234 101 122 174   8
  192 186 120  37  46  28 166 180 198 232 221 116  31  75 189 139 138
  208 112  62 181 102  72   3 246  14  97  53  87 185 134 193  29 158
  224 225 248 152  17 105 217 142 148 155  30 135 233 206  85  40 223
  240 140 161 137  13 191 230  66 104  65 153  45  15 176  84 187  22

Jianing Song, Table of n, a(n) for n = 0..255
Institute of Telematics, Rijndael.cpp File Reference (contains the table of the Rijndael S-box written in decimal)
Wikipedia, Rijndael S-box

Cf. A354501 (the inverse permutation), A355891.

m(P) = Mod(P, 2);
A354500(n) = subst(lift(lift(Mod(m(x^4+x^3+x^2+x+1)*lift(Mod(m(Pol(binary(n))), m(x^8+x^4+x^3+x+1))^254)+m(x^6+x^5+x+1), m(x^8+1)))), x, 2)

a(n) = ivgenpoly(((x^4+x^3+x^2+x+1)*(genpoly(n)^254 mod (x^8+x^4+x^3+x+1)) + x^6 + x^5 + x + 1) mod (x^8+1)), where ivgenpoly and genpoly are the notations introduced in A355891. Beware that all the operations are done in GF(2)[x].
To be more concretely, to obtain a(n):
- Write the binary expansion of n and view it as a polynomial p(x) in GF(2)[x]; (E.g., 10 = 1010_2 => x^3 + x)
- Compute q(x) = p(x)^254 mod (x^8+x^4+x^3+x+1) in GF(2)[x]; (E.g., x^3 + x => x^5 + x^3 + 1)
- Compute r(x) = ((x^4+x^3+x^2+x+1)*q(x) + x^6 + x^5 + x + 1) mod (x^8+1) in GF(2)[x]; (E.g., x^5 + x^3 + 1 => x^6 + x^5 + x^2 + x + 1)
- To get a(n), view r(x) as a number. (E.g., x^6 + x^5 + x^2 + x + 1 => 2^6 + 2^5 + 2^2 + 2 + 1 = 103)

A354501 The inverse Rijndael S-box used in the Advanced Encryption Standard (AES); inverse permutation of A354500.

Original entry on oeis.org

82, 9, 106, 213, 48, 54, 165, 56, 191, 64, 163, 158, 129, 243, 215, 251, 124, 227, 57, 130, 155, 47, 255, 135, 52, 142, 67, 68, 196, 222, 233, 203, 84, 123, 148, 50, 166, 194, 35, 61, 238, 76, 149, 11, 66, 250, 195, 78, 8, 46, 161, 102, 40, 217, 36, 178, 118, 91, 162, 73, 109

Offset: 0

Jianing Song, Aug 15 2022

			The inverse Rijndael S-box written in hexadecimal:
     +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +A +B +C +D +E +F
  00 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB
  10 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB
  20 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E
  30 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25
  40 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92
  50 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84
  60 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06
  70 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B
  80 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73
  90 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E
  A0 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B
  B0 FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4
  C0 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F
  D0 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF
  E0 A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61
  F0 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D
The inverse Rijndael S-box written in decimal:
       +0  +1  +2  +3  +4  +5  +6  +7  +8  +9 +10 +11 +12 +13 +14 +15
    0  82   9 106 213  48  54 165  56 191  64 163 158 129 243 215 251
   16 124 227  57 130 155  47 255 135  52 142  67  68 196 222 233 203
   32  84 123 148  50 166 194  35  61 238  76 149  11  66 250 195  78
   48   8  46 161 102  40 217  36 178 118  91 162  73 109 139 209  37
   64 114 248 246 100 134 104 152  22 212 164  92 204  93 101 182 146
   80 108 112  72  80 253 237 185 218  94  21  70  87 167 141 157 132
   96 144 216 171   0 140 188 211  10 247 228  88   5 184 179  69   6
  112 208  44  30 143 202  63  15   2 193 175 189   3   1  19 138 107
  128  58 145  17  65  79 103 220 234 151 242 207 206 240 180 230 115
  144 150 172 116  34 231 173  53 133 226 249  55 232  28 117 223 110
  160  71 241  26 113  29  41 197 137 111 183  98  14 170  24 190  27
  176 252  86  62  75 198 210 121  32 154 219 192 254 120 205  90 244
  192  31 221 168  51 136   7 199  49 177  18  16  89  39 128 236  95
  208  96  81 127 169  25 181  74  13  45 229 122 159 147 201 156 239
  224 160 224  59  77 174  42 245 176 200 235 187  60 131  83 153  97
  240  23  43   4 126 186 119 214  38 225 105  20  99  85  33  12 125

Jianing Song, Table of n, a(n) for n = 0..255
Wikipedia, Rijndael S-box

Cf. A354500, A355891.

m(P) = Mod(P, 2);
A354501(n) = subst(lift(lift(Mod(lift(Mod(m(x^6+x^3+x)*Pol(binary(n))+m(x^2+1), m(x^8+1))), m(x^8+x^4+x^3+x+1))^254)), x, 2)

a(n) = ivgenpoly((((x^6+x^3+x)*genpoly(n) + x^2 + 1) mod (x^8+1))^254 mod (x^8+x^4+x^3+x+1)), where ivgenpoly and genpoly are the notations introduced in A355891. Beware that all the operations are done in GF(2)[x].
To be more concretely, to obtain a(n):
- Write the binary expansion of n and view it as a polynomial p(x) in GF(2)[x]; (E.g., 103 = 1100111_2 => x^6 + x^5 + x^2 + x + 1)
- Compute q(x) = ((x^6+x^3+x)*p(x) + x^2 + 1) mod (x^8+1) in GF(2)[x]; (E.g., x^6 + x^5 + x^2 + x + 1 => x^5 + x^3 + 1)
- Compute r(x) = q(x)^254 mod (x^8+x^4+x^3+x+1) in GF(2)[x]; (E.g., x^5 + x^3 + 1 => x^3 + x)
- To get a(n), view r(x) as a number. (E.g., x^3 + x => 2^3 + 2 = 10)
This is the inverse to the process described in A354500.

cp's OEIS Frontend

A048631 Xfactorials - like factorials but use carryless GF(2)[ X ] polynomial multiplication.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A354500 The Rijndael S-box used in the Advanced Encryption Standard (AES).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354501 The inverse Rijndael S-box used in the Advanced Encryption Standard (AES); inverse permutation of A354500.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula