n次多項式f(x)の法pでの因数分解

 投稿者:山中和義  投稿日:2012年 5月16日(水)09時29分16秒
 
!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

 

戻る