Factoring 5^79-1

[2002.02.28]5^79-1の素因数分解

• 楕円曲線を使った素因数分解プログラム(ruby版)

■楕円曲線を使って、5⁷⁹-1を素因数分解する。

c55 = (5**79-1)/(5-1)
print("c55=",c55,"\n")

t1=Time::new
k=1.lcm_to(30000)
t2=Time::new
print("k=lcm{1,..,30000}=",k,"\n")
print("time=",(t2-t1),"[s]\n")

FiniteField.setorder(c55)
p31.pp(k,0,100000)

   .... 省略 ....
y^2=x^3+29x+(-113)
k(3 1)=(595539380516320663448907963905625847074556541557139324 3513565888319798214610715388893460501360365008063453945)
time=342.439281[s]
y^2=x^3+30x+(-116)
k(3 1)=(3857472591171786362477409524051867733131925275023115724 239010692649389852123332102846653027353831791146918627)
time=342.281186[s]
y^2=x^3+31x+(-119)
k(3 1)=(2994670124293890914118454536354591750986310451803085210 301084414512569122753718060727096152975163260685866679)
time=342.239202[s]
y^2=x^3+32x+(-122)
k(3 1)=(205367807127911 nil)
time=342.423274[s]

c55 = (5**79-1)/(5-1)
c41 = c55/205367807127911
print("c41=",c41,"\n")
# c41 = 20139003871181904621449723414125752904421 # composite number

t1=Time::new
k=1.lcm_to(35000)
t2=Time::new
print("k=lcm{1,..,35000}=",k,"\n")
print("time=",(t2-t1),"[s]\n")

FiniteField.setorder(c41)
p31.pp(k,100,100000)

   .... 省略 ....  
y^2=x^3+206x+(-644)
k(3 1)=(13910994060295757518022648157548333307728 1940025909573328293355309245277967757722)
time=315.86732[s]
y^2=x^3+207x+(-647)
k(3 1)=(18106709001779912939742686851620369286167 16314164303226244531218507566445600219166)
time=315.422956[s]
y^2=x^3+208x+(-650)
k(3 1)=(7240576451957239769284415423479989378741 3563930715291536484265909048389215058289)
time=315.769393[s]
y^2=x^3+209x+(-653)
k(3 1)=(9720601146817911642565036711374631962926 1301846935198105326756437850014255170210)
time=315.620909[s]
y^2=x^3+210x+(-656)
k(3 1)=(11580344266918145262332236841417407772438 16659006988883958633100554905123219985164)
time=315.513321[s]
y^2=x^3+211x+(-659)
k(3 1)=(58523123221688392679 nil)
time=316.04192[s]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                          %
%                           ECPP                           %
%                                                          %
%                  by Fran\c{c}ois MORAIN                  %
%                  morain@inria.inria.fr                   %
%                      Version V3.4.1                      %
%                                                          %
%           "3 is prime, 5 is prime, 7 is prime            %
%              so every odd number is prime"               %
%                                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Working on 205367807127911
% Performing a quick compositeness test
% This number might be prime
% Entering ECPP
% Starting phase 1: building the sequence of primes
% Pmax=5000
% N_0=205367807127911
% next D is 0
% Cofactor after sieve is a probable prime
% D[[0]]=-1
% Factor= 79^1
% Factor= 7^1
% Factor= 5^1
% Factor= 2^1
% End of depth 0 at 0.069256 s

% Pmax=5000
% N_1=37137035647
% next D is 0
% itmax=0 ngcd=0 b1=0 b2=0
% Cofactor after sieve is a probable prime
% D[[1]]=1
% Factor= 2^7
% End of depth 1 at 0.081489 s

% Pmax=5000
% N_2=290133091
% next D is 0
% Factorization completed using sieve only
% D[[2]]=-1
% Factor= 467^1
% Factor= 59^1
% Factor= 13^1
% Factor= 5^1
% Factor= 3^4
% Factor= 2^1
% Cofactor is 1
% End of depth 2 at 0.093141 s

% Pmax=5000
% N_3=467
% next D is 0
% Factorization completed using sieve only
% D[[3]]=-1
% Factor= 233^1
% Factor= 2^1
% Cofactor is 1
% End of depth 3 at 0.107700 s

% Pmax=5000
% N_4=233
% next D is 0
% Factorization completed using sieve only
% D[[4]]=-1
% Factor= 29^1
% Factor= 2^3
% Cofactor is 1

% Time for building is 0.086041 s

% Starting phase 2: proving
% Starting proving job for step 0
% N_0 is prime
% Time for proof[0] is 0.001865 s

% Starting proving job for step 1
% N_1 is prime
% Time for proof[1] is 0.010108 s

% Starting proving job for step 2
% Using complete factorization theorem
% b=1
% Nonresidue is 3
% b=1
% Nonresidue is 8
% b=1
% Nonresidue is 10
% N_2 is prime
% Time for proof[2] is 0.002907 s

% Starting proving job for step 3
% N_3 is prime
% Time for proof[3] is 0.000298 s

% Starting proving job for step 4
% Using complete factorization theorem
% N_4 is prime
% Time for proof[4] is 0.000494 s
% Time for building is 0.086041 s
% Time for proving  is 0.019688 s
% Total time is        0.105821 s
This number is prime
% Time for this number is 0.132495s

Working on 58523123221688392679
% Performing a quick compositeness test
% This number might be prime
% Entering ECPP
% Starting phase 1: building the sequence of primes
% Pmax=5000
% N_0=58523123221688392679
% next D is 0
% itmax=0 ngcd=0 b1=0 b2=0
% itmax=0 ngcd=0 b1=0 b2=0
% next D is 11
% itmax=0 ngcd=0 b1=0 b2=0
% Cofactor after sieve is a probable prime
% D[[0]]=11
% A[[0]]=-3923745015
% B[[0]]=-4458869791
% m[[0]]=58523123225612137695
% Factor= 97^1
% Factor= 5^1
% Factor= 3^1
% End of depth 0 at 0.211699 s

% Pmax=5000
% N_1=40222077818290129
% next D is 0
% Cofactor after sieve is a probable prime
% D[[1]]=-1
% Factor= 1723^1
% Factor= 1373^1
% Factor= 193^1
% Factor= 59^1
% Factor= 3^2
% Factor= 2^4
% End of depth 1 at 0.236225 s

% Pmax=5000
% N_2=10369
% next D is 0
% Factorization completed using sieve only
% D[[2]]=-1
% Factor= 3^4
% Factor= 2^7
% Cofactor is 1

% Time for building is 0.089527 s

% Starting phase 2: proving
% Starting proving job for step 0
% File /home/his/ECPP/Ecpp/Data/Weber/h1g1.cwdx does not exist
% tpber=0.000327s
% j has been computed
% E found
% Suggested twist(11)=1
% N_0 is prime
% Time for proof[0] is 0.045361 s

% Starting proving job for step 1
% Using complete factorization theorem
% N_1 is prime
% Time for proof[1] is 0.010118 s

% Starting proving job for step 2
% Using complete factorization theorem
% b=1
% Nonresidue is 13
% N_2 is prime
% Time for proof[2] is 0.000946 s
% Time for building is 0.089527 s
% Time for proving  is 0.057145 s
% Total time is        0.146844 s
This number is prime
% Time for this number is 0.172294s

Working on 344120456368919234899
% Performing a quick compositeness test
% This number might be prime
% Entering ECPP
% Starting phase 1: building the sequence of primes
% Pmax=5000
% N_0=344120456368919234899
% next D is 0
% itmax=0 ngcd=0 b1=0 b2=0
% Cofactor after sieve is a probable prime
% D[[0]]=1
% Factor= 4903^1
% Factor= 509^1
% Factor= 29^1
% Factor= 7^1
% Factor= 5^2
% Factor= 2^2
% End of depth 0 at 0.371952 s

% Pmax=5000
% N_1=6792580229
% next D is 0
% Cofactor after sieve is a probable prime
% D[[1]]=-1
% Factor= 83^1
% Factor= 7^1
% Factor= 2^2
% End of depth 1 at 0.394722 s

% Pmax=5000
% N_2=2922797
% next D is 0
% Cofactor after sieve is a probable prime
% D[[2]]=-1
% Factor= 43^1
% Factor= 2^2
% End of depth 2 at 0.408765 s

% Pmax=5000
% N_3=16993
% next D is 0
% Factorization completed using sieve only
% D[[3]]=-1
% Factor= 59^1
% Factor= 3^2
% Factor= 2^5
% Cofactor is 1

% Time for building is 0.086059 s

% Starting phase 2: proving
% Starting proving job for step 0
% N_0 is prime
% Time for proof[0] is 0.050706 s

% Starting proving job for step 1
% N_1 is prime
% Time for proof[1] is 0.000803 s

% Starting proving job for step 2
% N_2 is prime
% Time for proof[2] is 0.000478 s

% Starting proving job for step 3
% Using complete factorization theorem
% b=1
% Nonresidue is 10
% N_3 is prime
% Time for proof[3] is 0.001152 s
% Time for building is 0.086059 s
% Time for proving  is 0.054193 s
% Total time is        0.140366 s
This number is prime
% Time for this number is 0.169847s

% ==> Total time for the computations is 0.470292s

[参考文献]

• [1]Joseph H.Silverman, John Tate(著), 足立 恒雄, 木田 雅成, 小松 啓一, 田谷 久雄(訳), "楕円曲線論入門", シュプリンガー・フェアラーク東京, 1995, ISBN4-431-70683-6, {3900円}.
  
• [2]三島 久典, 数学者の密室.
  
• [3]Ivars Peterson(著), 奥田 晃(訳), "コンピュータ・グラフィックスがひらく現代数学ワンダーランド", 新曜社, 1990(1刷), p21-59, ISBN4-7885-0270-0, {2800円}.
  
• [4]MorainのECPPプログラム.
  

[Homeに戻る]  [一覧に戻る]