|
|
!n次多項式f(x)の法pでの因数分解
!例
!f(x)=x^4+x^3+x^2+x+1なら、
!f(x)=(x-1)^4 (mod 5)
!f(x)=(x-3)(x-4)(x-5)(x-9) (mod 11)
!考察
!通常、実数の範囲での因数分解を考えると、
!fは2次式とする。
! f(x)≡f(x) (mod p) fは既約
! f(x)≡g(x)h(x) (mod p)、g,hは1次式
!と因数分解される。
!
!fは3次式とする。
! f(x)≡f(x) (mod p) fは既約
! f(x)≡g(x)h(x) (mod p)、gは2次式、hは1次式
! f(x)≡g(x)h(x)s(x) (mod p)、g,h,sは1次式
!と因数分解される。
!
!fは4次式とする。
! f(x)≡f(x) (mod p) fは既約
! f(x)≡g(x)h(x) (mod p)、gは3次式、hは1次式
! f(x)≡g(x)h(x) (mod p)、g,hは2次式
! f(x)≡g(x)h(x)s(x) (mod p)、gは2次式、h,sは1次式
! f(x)≡g(x)h(x)s(x)t(x) (mod p)、g,h,s,tは1次式
!と因数分解される。
!
!fは5次式とする。5=1+4=2+3=(1+1)+3=1+2+2=1+(1+1)+2=1+(1+1)+(1+1)
!次数5を1,2,3,4の和で表せばよい。
! ：
! ：
!
!
!考察
!aが解なら、-(P-a)も解である。すなわち、x-a≡0 (mod p)またはx+(P-a)≡0 (mod p)
DEF f(x)=x^4+x^3+x^2+x+1 !x^4+9*x^2+2*x+42
DEF e(x)=x^3+a*x^2+b*x+c !3次式
DEF g(x)=x^2+a*x+b !2次式
DEF h(x)=x^2+c*x+d
DEF s(x)=x-a !1次式
DEF t(x)=x-b
DEF u(x)=x-c
DEF v(x)=x-d
LET p=11 !素数
!3次式×1次式
LET K=0 !個数
FOR a=0 TO p-1 !係数 ※剰余の範囲
FOR b=0 TO p-1
FOR c=0 TO p-1
FOR d=0 TO p-1
FOR x=0 TO p-1 !同じ値となるなら
IF MOD(f(x) - e(x)*v(x) ,p)<>0 THEN EXIT FOR
NEXT x
IF x>p-1 THEN !因数分解される
LET K=K+1
PRINT "(x^3+";STR$(a);"x^2+";STR$(b);"x+";STR$(c);")"; !因数
PRINT "(x-";STR$(d);")"
PRINT "(x^3+";STR$(a);"x^2+";STR$(b);"x+";STR$(c);")"; !因数
PRINT "(x+";STR$(p-d);")"
END IF
NEXT d
NEXT c
NEXT b
NEXT a
IF K=0 THEN PRINT "解なし"
PRINT
!2次式×2次式
LET K=0 !個数
FOR a=0 TO p-1 !係数 ※剰余の範囲、a≦c
FOR b=0 TO p-1
FOR c=a TO p-1
FOR d=0 TO p-1
FOR x=0 TO p-1 !同じ値となるなら
IF MOD(f(x) - g(x)*h(x) ,p)<>0 THEN EXIT FOR
NEXT x
IF x>p-1 THEN !因数分解される
LET K=K+1
PRINT "(x^2+";STR$(a);"x+";STR$(b);")"; !因数
PRINT "(x^2+";STR$(c);"x+";STR$(d);")"
END IF
NEXT d
NEXT c
NEXT b
NEXT a
IF K=0 THEN PRINT "解なし"
PRINT
!2次式×1次式×1次式
LET K=0 !個数
FOR a=0 TO p-1 !係数 ※剰余の範囲、c≦d
FOR b=0 TO p-1
FOR c=0 TO p-1
FOR d=c TO p-1
FOR x=0 TO p-1 !同じ値となるなら
IF MOD(f(x) - g(x)*u(x)*v(x) ,p)<>0 THEN EXIT FOR
NEXT x
IF x>p-1 THEN !因数分解される
LET K=K+1
PRINT "(x^2+";STR$(a);"x+";STR$(b);")"; !因数
PRINT "(x-";STR$(c);")(x-";STR$(d);")"
PRINT "(x^2+";STR$(a);"x+";STR$(b);")"; !因数
PRINT "(x+";STR$(p-d);")(x+";STR$(p-c);")"
END IF
NEXT d
NEXT c
NEXT b
NEXT a
IF K=0 THEN PRINT "解なし"
PRINT
!1次式×1次式×1次式×1次式
LET K=0 !個数
FOR a=0 TO p-1 !係数 ※剰余の範囲、a≦b≦c≦d
FOR b=a TO p-1
FOR c=b TO p-1
FOR d=c TO p-1
FOR x=0 TO p-1 !同じ値となるなら
IF MOD(f(x) - s(x)*t(x)*u(x)*v(x) ,p)<>0 THEN EXIT FOR
NEXT x
IF x>p-1 THEN !因数分解される
LET K=K+1
PRINT "(x-";STR$(a);")(x-";STR$(b);")"; !因数
PRINT "(x-";STR$(c);")(x-";STR$(d);")"
PRINT "(x+";STR$(p-d);")(x+";STR$(p-c);")"; !因数
PRINT "(x+";STR$(p-b);")(x+";STR$(p-a);")"
END IF
NEXT d
NEXT c
NEXT b
NEXT a
IF K=0 THEN PRINT "解なし"
END
|
|