|
|
p(x)÷(x^d-1)、p(x)÷(x^(d-1)+x^(d-2)+ … +x^2+x+1) の場合
考察
(x-1){x^(d-1)+x^(d-2)+ … +x^2+x+1}=x^d-1 であるので、
次のように次数を下げることで余りを求めることができる。
x^n
=(x^d-1)x^(n-d) +x^(n-d)
=(x^d-1)x^(n-d) +(x^d-1)x^(n-2d) +x^(n-2d)
=(x^d-1)x^(n-d) +(x^d-1)x^(n-2d) +(x^d-1)x^(n-3d) +x^(n-3d)
= ：
=(x^d-1){x^(n-d) +x^(n-2d) +x^(n-3d) +x^(n-4d) + … } +x^r ただし、n=qd+r
≡x^r mod (x^d-1)
（終り）
例
x^8+x^7+1
=(x^3-1)(x5+x^2)+x^2 +(x^3-1)(x^4+x)+x +1
≡x^2+x+1 mod (x^3-1)
≡0 mod (x^2+x+1)
DATA 8 !1+x^7+x^8
DATA 1,0,0,0,0,0,0,1,1
READ aa
DIM A(0 TO aa)
MAT READ A
LET d=3 !x^3-1
DIM B(0 TO d-1)
MAT B=ZER
FOR i=0 TO aa
IF A(i)<>0 THEN
LET q=INT(i/d) !i=q*d+r
LET r=MOD(i,d)
PRINT A(i); "x^"; STR$(r)
LET B(r)=B(r)+A(i)
END IF
NEXT i
MAT PRINT B; !余り B(0)+B(1)x+B(2)x^2+ …
END
同様に、
p(x)÷(x^d+1)、p(x)÷(x^(d-1)-x^(d-2)+ … +x^2-x+1) の場合
x^n
=(x^d+1)x^(n-d) -x^(n-d)
=(x^d+1)x^(n-d) -(x^d+1)x^(n-2d) +x^(n-2d)
=(x^d+1)x^(n-d) -(x^d+1)x^(n-2d) +(x^d+1)x^(n-3d) -x^(n-3d)
=(x^d+1)x^(n-d) -(x^d+1)x^(n-2d) +(x^d+1)x^(n-3d) -(x^d+1)x^(n-4d) +x^(n-4d)
= ：
=(x^d+1){x^(n-d) -x^(n-2d) +x^(n-3d) -x^(n-4d) + … } +(-1)^q x^r ただし、n=qd+r
└──────── q個 ───────┘
≡(-1)^q x^r mod (x^d+1)
例
x^8+x^4+1
=(x^3+1)(x5-x^2)+x^2 +(x^3+1)x-x +1
≡x^2-x+1 mod (x^3+1)
≡0 mod (x^2-x+1)
DATA 8 !1+x^4+x^8
DATA 1,0,0,0,1,0,0,0,1
READ aa
DIM A(0 TO aa)
MAT READ A
LET d=3 !x^3+1
DIM B(0 TO d-1)
MAT B=ZER
FOR i=0 TO aa
IF A(i)<>0 THEN
LET q=INT(i/d) !i=q*d+r
LET r=MOD(i,d)
PRINT A(i)*(-1)^q; "x^"; STR$(r)
LET B(r)=B(r)+A(i)*(-1)^q
END IF
NEXT i
MAT PRINT B; !余り B(0)+B(1)x+B(2)x^2+ …
END
問題
整式p(x)=x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1とする。
p(x^m)÷p(x)の余りを求めよ。
考察
(x-1)p(x)=x^12-1≡0 mod p(x)である。
たとえば、p(x^2)の場合、x^12≡1として、
p(x^2)
=x^22+x^20+x^18+x^16+x^14+x^12+x^10+x^8+x^6+x^4+x^2+1
=x^10+x^8 +x^6 +x^4 +x^2 +1 +x^10+x^8+x^6+x^4+x^2+1
=2(x^10+x^8+x^6+x^4+x^2+1)
また、
±0≡0,12 mod 12
±1≡1,11 mod 12
±2≡2,10 mod 12
±3≡3,9 mod 12
±4≡4,8 mod 12
±5≡5,7 mod 12
±6≡6 mod 12
なので、
p(x^0)=p(x^12)
p(x^1)=p(x^11)
p(x^2)=p(x^10)
p(x^3)=p(x^9)
p(x^4)=p(x^8)
p(x^5)=p(x^7)
p(x^6)
と予想される。
ちなみに、
p(x^10)
=x^110+x^100+x^90+x^80+x^70+x^60+x^50+x^40+x^30+x^20+x^10+1
=x^2 +x^4 +x^6 +x^8 +x^10+1 +x^2 +x^4 +x^6 +x^8 +x^10+1
≡2(1+x^2+x^4+x^6+x^8+x^10)
のように、計算してみると予想通りである。
また、12と互いに素、すなわち、1,5,7,11の場合、
p(x^1)=p(x^5)=p(x^7)=p(x^11)≡0
とわかる。
よって、
p(x^0)=p(x^12)≡12
p(x^1)=p(x^5)=p(x^7)=p(x^11)≡0
p(x^2)=p(x^10)≡2(1+x^2+x^4+x^6+x^8+x^10)
p(x^3)=p(x^9)≡3(1+x^3+x^6+x^9)
p(x^4)=p(x^8)≡4(1+x^4+x^8)
p(x^6)≡6(1+x^6)
（終り）
LET m=2 !p(x^m)
LET k=11 !1+x+x^2+ … +x^k
DIM A(0 TO m*k)
FOR i=0 TO k
LET A(m*i)=1
NEXT i
LET d=12 !x^12-1
DIM B(0 TO d-1)
MAT B=ZER
FOR i=0 TO m*k
IF A(i)<>0 THEN
LET q=INT(i/d) !i=q*d+r
LET r=MOD(i,d)
PRINT A(i); "x^"; STR$(r)
LET B(r)=B(r)+A(i)
END IF
NEXT i
MAT PRINT B; !余り B(0)+B(1)x+B(2)x^2+ …
END
|
|