|
|
ポラード・ロー素因数分解法(RHO)
(※ 素因数分解はしていません。約数1つ見つけるだけです)
OPTION ARITHMETIC RATIONAL
LET N=18446744073709551617
!'INPUT N
LET X=2
LET Y=2
LET D=1
DO WHILE D=1
LET X=F(X,N)
LET Y=F(F(Y,N),N)
LET D=GCD(ABS(X-Y),N)
LOOP
IF D<>N THEN PRINT D,N/D ELSE PRINT "失敗"
END
EXTERNAL FUNCTION F(X,N)
OPTION ARITHMETIC RATIONAL
LET C=1
LET F=MOD(X*X+C,N)
END FUNCTION
-----------------------------------------------------------------
OPTION ARITHMETIC RATIONAL
RANDOMIZE
LET N=10023859281455311421
!'INPUT N
LET X0=INT(RND*N)
LET M=INT(RND*N)
LET Y=X0
LET R=1
LET A=1
DO
LET X=Y
FOR I=1 TO R
LET Y=F(Y,N)
NEXT I
LET K=0
DO
LET YS=Y
FOR I=1 TO MIN(M,R-K)
LET Y=F(Y,N)
LET A=MOD(A*ABS(X-Y),N)
NEXT I
LET G=GCD(A,N)
LET K=K+M
LOOP UNTIL K>R OR G>1
LET R=2*R
LOOP UNTIL G>1
IF G=N THEN
DO
LET YS=F(YS,N)
LET G=GCD(ABS(X-YS),N)
LOOP UNTIL G>1
END IF
IF G=N THEN PRINT "失敗" ELSE PRINT G,N/G
END
EXTERNAL FUNCTION F(X,N)
OPTION ARITHMETIC RATIONAL
LET C=1
LET F=MOD(X*X+C,N)
END FUNCTION
|
|