필드 수학들은 특정 공리 만족하도록, 그 위에 추가로 정의 곱셈 연산과 숫자의 집합 (위키의 설명을, 또한 아래 참조).

유한 필드는 p ⁿ 요소를 가질 수 있으며 , 여기서 p소수 n는 자연수입니다. 이 도전에서 p = 2and를 가져 와서 n = 8256 개의 요소로 필드를 만들어 봅시다.

필드의 요소를 포함하는 범위의 연속 정수해야 0하고 1:

-128 … 127
0 … 255
또는 다른 범위

추상 “추가”및 추상 “곱하기”에 대해 필드 공리를 만족하도록 두 가지 기능 (또는 더 쉬운 경우 프로그램)을 정의하십시오 .a(x,y)m(x,y)

일관성 : a(x,y)와 m(x,y)같은 인수로 호출 할 때 동일한 결과를
Closedness : 결과 a및 m관련 범위의 정수이고
연관성 : 모두에 대해 x, y및 z범위에 a(a(x,y),z)동일하다 a(x,a(y,z)); 같은m
교환 법칙 : 임의 용 x및 y범위는 a(x,y)동일하다 a(y,x); 같은m
분배 법칙 : 모두에 대해 x, y및 z범위에서 m(x,a(y,z))같다a(m(x,y),m(x,z))
중립 요소 : 모두에 대한 x범위에서 a(0,x)와 동일 x하고 m(1,x)동일하다x
부정은 : 어떤에 대한 x범위 등이 존재 y하는 a(x,y)것입니다0
역은 : 어떤에 대한 x≠0범위 등이 존재 y하는 m(x,y)것입니다1

이름 a과 m예제 일뿐입니다. 다른 이름이나 명명되지 않은 함수를 사용할 수 있습니다. 답의 점수는 a및 의 바이트 길이의 합입니다 m.

내장 함수를 사용하는 경우 결과로 생성되는 단어도 설명하십시오 (예 : 곱셈표 제공).

답변

인텔 x86-64 + AVX-512 + GFNI, 11 바이트

add:
    C5 F0 57 C0     # vxorps     xmm0, xmm1, xmm0
    C3              # ret
mul:
    C4 E2 79 CF C1  # vgf2p8mulb xmm0, xmm0, xmm1
    C3              # ret

GF2P8MULBIce Lake CPU에 대한 새로운 지침을 사용합니다 .

이 명령어는 유한 필드 GF (2 ⁸ )의 요소를 곱하여 첫 번째 소스 피연산자의 바이트 (필드 요소)와 두 번째 소스 피연산자의 해당 바이트에서 작동합니다. 필드 GF (2 ⁸ )는 다항식 x ⁸ + x ⁴ + x ³ + x + 1 로 다항식으로 표현됩니다 .

답변

파이썬 2, 11 + 45 = 56 바이트

추가 (11 바이트) :

int.__xor__

곱셈 (45 바이트) :

m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

범위 내에서 입력 번호를 [0 ... 255]받습니다. 덧셈은 비트 단위 XOR이며 곱셈은 러시아 농민 과 GF2의 계수로 다항식의 곱입니다 .

그리고 확인을 위해 :

a=int.__xor__
m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x

for x in range(256):
    assert a(0,x) == a(x,0) == x
    assert m(1,x) == m(x,1) == x

    assert any(a(x,y) == 0 for y in range(256))

    if x != 0:
        assert any(m(x,y) == 1 for y in range(256))

    for y in range(256):
        assert 0 <= a(x,y) < 256
        assert 0 <= m(x,y) < 256
        assert a(x,y) == a(y,x)
        assert m(x,y) == m(y,x)

        for z in range(256):
            assert a(a(x,y),z) == a(x,a(y,z))
            assert m(m(x,y),z) == m(x,m(y,z))
            assert m(x,a(y,z)) == a(m(x,y), m(x,z))

답변

자바 스크립트 (ES6), 10 + 49 = 59 바이트

a=(x,y)=>x^y
m=(x,y,p=0)=>x?m(x>>1,2*y^283*(y>>7),p^y*(x&1)):p

도메인은 0 … 255입니다. 소스 .

답변

Hoon , 22 바이트

[dif pro]:(ga 8 283 3)

Hoon은 이미 ++gaAES 구현에 사용하기 위해 Galois Field를 생성 하는 기능 을 가지고 있습니다. 두 개의 프로그램을 사용하는 대신 두 개의 함수 튜플을 반환합니다.

도메인에서 작동 [0...255]

테스트 스위트 :

=+  f=(ga 8 283 3)
=+  n=(gulf 0 255)

=+  a=dif:f
=+  m=pro:f

=+  %+  turn  n
    |=  x/@
    ?>  =((a 0 x) x)
    ?>  =((m 1 x) x)
    ~&  outer+x

    %+  turn  n
      |=  y/@
      ?>  =((a x y) (a y x))
      ?>  &((lte 0 (a x y)) (lte (a x y) 255))
      ?>  &((lte 0 (m x y)) (lte (m x y) 255))

      %+  turn  n
        |=  z/@
        ?>  =((a (a x y) z) (a x (a y z)))
        ?>  =((m x (a y z)) (a (m x y) (m x z)))
        ~
"ok"

곱셈 테이블을 게시하는 것은 거대하기 때문에 다음은 임의의 테스트 사례입니다.

20x148=229
61x189=143
111x239=181
163x36=29
193x40=1

답변

IA-32 기계 코드, 22 바이트

“곱셈”, 18 바이트 :

33 c0 92 d1 e9 73 02 33 d0 d0 e0 73 02 34 1b 41
e2 f1

“추가”, 4 바이트 :

92 33 c1 c3

이것은 규칙을 조금 확장시킨다 : “곱하기”코드는 기능 종료 코드가 없다; 그것은 바로 메모리에있는 “추가”코드에 의존하므로 “폴 스루”할 수 있습니다. 코드 크기를 1 바이트 줄이려고했습니다.

소스 코드 ( mlMS Visual Studio로 구성 가능) :

    TITLE   x

PUBLIC @m@8
PUBLIC @a@8

_TEXT   SEGMENT USE32
@m@8    PROC
    xor eax, eax;
    xchg eax, edx;
myloop:
    shr ecx, 1
    jnc sk1
    xor edx, eax
sk1:
    shl al, 1
    jnc sk2
    xor al, 1bh
sk2:
    inc ecx
    loop myloop
@m@8 endp

@a@8 proc
    xchg eax, edx;
    xor eax, ecx
    ret
@a@8    ENDP
_text ENDS
END

알고리즘은 x^8 + x^4 + x^3 + x + 116 진수로 표현되는 일반적인 다항식을 포함하는 표준 알고리즘입니다 1b. “곱하기”코드는 결과를에 누적합니다 edx. 완료되면 덧셈 코드로 넘어 가고 eax(반환 값을 유지하기 위해 기존 레지스터로 이동 ); xor와는 ecx그 시점에 있기 때문에, 아무 조합 없습니다 ecx지워집니다.

독특한 특징 중 하나는 루프입니다. 0을 확인하는 대신

cmp ecx, 0
jne myloop

전용 loop명령을 사용합니다 . 그러나이 명령어는 루프 “카운터”를 0과 비교하기 전에 감소시킵니다.이를 보완하기 위해 코드는 loop명령어 를 사용하기 전에 루프를 증가시킵니다 .

답변

Mathematica 155 바이트

f[y_]:=Total[x^Reverse@Range[0,Log[2,y]]*RealDigits[y,2][[1]]];o[q_,c_,d_]:=FromDigits[Reverse@Mod[CoefficientList[PolynomialMod[q[f@c,f@d],f@283],x],2],2]

이행

(*
  in: o[Times, 202, 83]    out: 1
  in: o[Plus, 202, 83]     out: 153
*)

추가 확인 :

(*
  in: BitXor[202, 83]      out: 153
*)

더:

(*
  in: o[Times, #, #2] & @@@ {{20, 148}, {61, 189}, {111, 239}, {163, 36}, {193, 40}}
  out: {229, 143, 181, 29, 1}
*)

NB {283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375, 379, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 499, 501, 505}대신 사용할 수 있어야합니다 283.

답변

Brainfuck, 28 자

다행히 표준 Brainfuck은 모든 모듈로 256을 수행합니다.

추가 : [->+<], 입력이 테이프의 처음 두 위치에 있다고 가정하고 출력을 위치 0에 배치합니다.

곱셈 : [->[->+>+<<]>[-<+>]<<], 입력이 테이프의 처음 두 위치에 있다고 가정하고 출력을 위치 3에 배치

How IT

언제든지 물어보세요.

256 개의 요소로 필드 정의 = 8256 개의 요소로 필드를 만들어

답변