SQUFOF NTT Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) N UBASIC 50 / 200 [

Size: px

Start display at page:

Download "SQUFOF NTT Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) N UBASIC 50 / 200 ["

れいなたかぎ
5 years ago
Views:

1 SQUFOF

2 SQUFOF NTT Shanks SQUFOF SQUFOF Pentium III Pentium 4 SQUFOF 2.03 (Pentium 4 2.0GHz Willamette) N UBASIC 50 / 200 [ 01] 4 large prime

3 (%) (%) CPU1 Pentium III 700MHz (Coppermine) CPU2 Pentium 4 2GHz (Willamette) OS FreeBSD-4.5R 1 gcc version (release) [FreeBSD] 2 gcc version pgcc (release) CPU CPU CPU x86 CPU Pentium 4 (Northwood) Pentium 4 CPU Northwood Pentium 4 Willamette 2

4 Pentium III Pentium III Pentium 4 Pentium III Pentium 4 CPU Pentium III Pentium 4 Pentium 4 Pentium 4 CPU Athlon OS Linux 1 3% FreeBSD 4.x pgcc -Wall -fomit-frame-pointer -O6 -lm icc 2 1 gcc 3 C (ANSI-C ISO-C ) MMX, SSE, SSE2 2 SQUFOF SQUFOF [Rie93, pp ] Pascal SQUFOF [Rie93] SQUFOF ( ) ( ) 32 1 Linux version (root@neo), gcc version (Debian GNU/Linux) 2 Intel(R) C++ Compiler for 32-bit applications, Version

5 3 SQUFOF [Coh93, p.430] N 2 N 1 (mod 4) N 5N N 62 SQUFOF 2 N 2 62 first phase (%)

6 2 3 3 (3) SQUFOF SQUFOF ( (1 2 3 ) ( )) + (1 2 3 ) 1 = osqufof SQUFOF 2 first phase 0 1 Input: N (to be factored) Output: factor of N Cf max N if Cf max > 11 then Cf max 11 for Cf 3 to Cf max step by +2 do p osqufof(cf N, 2 17 Cf max 1 ) if p > Cf then return non-trivial factor of p return osqufof(n, 2 19 ) 1: SQUFOF SQUFOF 1 4 SQUFOF [Rie93, pp ] SQUFOF Pentium III [clock cycle] first phase 100 second phase 53 3 ( ) 5

7 [Fog00] div fsqrt instruction latency fsqrt first 1 phase 2 2 fsqrt (%) div (%) first phase second phase q i N + Pi 1 < = q i = < 2 N Q i 1 q i (%) (%) q i numerator = N + Pi if numerator Q i < Q i then q i = 1 else numerator q i = Q i 1 1 clock cycle penalty 26 clock cycles 1 1 clock cycle % (26 + 1) + (1 42%) 39 = 37 < 39 q i idiv (31 ) 5 float 6

8 penalty 26 clock cycle 10 [clock cycle] first phase 79 second phase = 20 clock cycles 39 clock cycles 4.2 first phase first phase [Rie93, pp ] SQUFOF first phase [Rie93, pp ] R[R 2 2, 3 (mod 4)] if Q i+1 3 > 1 then go to the next continued fraction else R Qi+1 if R 2 = Q i+1 then go to second phase go to the next continued fraction [Coh93, pp.39 41] 4 mod2 k mod2 k ± 1 mod 2 k (±1) 7

9 if not issquaremod256[q i+1 0xff] then go to the next continued fraction /* 83% discarded */ else /* compute mod2 8 1 */ tmp (Q i+1 0xff00ff) + (( Q i ) 0xff00ff) tmp tmp + tmp 2 16 tmp tmp + tmp 2 8 tmp tmp 0xff 6 if not issquaremod255[tmp] then go to the next continued fraction /* rest of 79% discarded */ R Qi+1 if R 2 = Q i+1 then go to second phase go to the next continued fraction issquaremod256[] 55 clock cycles issquaremod255[] 43 clock cycles mod index KB 7 39 clock cycles issquaremod255[] first phase second phase 2 2 (39 33) = 12 [clock cycle] +1 2 first phase 1 5 loop unroll 6 0x101 issquaremod255[0] = issquaremod255[1] KB 8

10 CPU ( ) [Mcycles/ ] [ ] Pentium III 2.45 (2.84) 1.87 (1.3GHz ) Pentium (4.69) 1.60 (2.53GHz ) Pentium III 1.2 Pentium gcc -mcpu=i386 -mcpu= 35 (3.7%) Time [cycle] : [Pentium III] 6 large prime p 1 ρ Pentium 4 9

11 e+16 1e+17 1e+18 1e+19 Time [cycle] N 3: N [Pentium III] e+06 1e+07 1e+08 1e+09 1e+10 Time [cycle] p 4: p [Pentium III] 10

12 [Coh93] Henri Cohen. A Course in Computational Algebraic Number Theory, Vol. 138 of Graduate Texts in Mathematics. Springer-Verlag, Boston, Basel, Berlin, Second Corrected Printing [Fog00] Agner Fog. How to optimize for the Pentium microprocessors, ( [Rie93] Hans Riesel. Prime Numbers and Computer Methods for Factorization, Vol. 126 of Progress in Mathematics. Birkhäuser, Boston, Basel, Berlin, second edition, [ 01]. 200, (JANT) 5. 11

2 2 ( M2) ( )

2 2 ( M2) ( ) 2007 3 3 1 2 P. Gaudry and R. Harley, 2000 Schoof 63bit 2 8 P. Gaudry and É. Schost, 2004 80bit 1 / 2 16 2 10 2 p: F p 2 C : Y 2 =F (X), F F p [X] : monic, deg F = 5, J C (F p ) F F p p Frobenius