(50G) Elliptic Curve Integer Factorization Programme - Gerald H - 06-25-2015 07:49 AM
While I am convinced that people are not supposed to live more than 50 years I'm still jogging on at the age of 62, so I decided to write a large(ish) programme.
The programme ecm takes a composite integer as input & returns a factor, found through the elliptic curve factorzing method.
ecm, while itself a short programme, has several sub-programmes integral to its functioning, as is my heart to my body, which qualify ecm to receive the attribute large
Code:
ecm
::
CK1&Dispatch
# FF
::
ID x00E
Z100_
ID x00D
;
;
x008
::
BINT0
4UNROLL
'
NULLLAM
BINT5
NDUPN
DOBIND
NULL{}
3GETLAM
Z1_
FPTR2 ^QSub
FPTR2 ^Z>R
% 999999999999.
%MIN
%RAN
%*
%IP
FPTR2 ^R>Z
1GETLAM
FPTR2 ^Z2BIN
ZERO_DO
INDEX@
DUP
BINT80h
#/
#1+
#>$
"Mul #: "
SWAP&$
BIGDISPROW2
DROP
FPTR2 ^#>Z
DUP
ZINT 128
FPTR2 ^QAdd
1GETLAM
FPTR2 ^ZNMin
DUP4PUTLAM
ID x00A
5GETLAM
3UNROLL
2GETLAM
3GETLAM
ID x009
IT
::
ExitAtLOOP
DUP
Z1_
Z>
OVER
3GETLAM
Z<
AND
NOT?SEMI
5GETLAM
2GETLAM
4GETLAM
BINT3
{}N
SWAP
;
BINT80h
+LOOP
ABND
OVER
NULLCOMP?
case2drop
Z0_
ROTDROP
;
x009
::
ROT
FPTR2 ^DupQIsZero?
case
::
4UNROLL3DROP
TRUE
;
FPTR2 ^Z>ZH
5UNROLL
3PICK
Z1_
5PICK
DUPDUP
FPTR2 ^RMULText
8PICK
FPTR2 ^RADDext
FPTR2 ^RMULText
5ROLL
FPTR2 ^RADDext
4PICK
FPTR2 ^ZMod
DUP
5PICK
ID x00F
ROTDUP
FPTR2 ^ZIsOne?
NOTcase
::
10UNROLL
BINT9
NDROP
TRUE
;
2DROP
'
NULLLAM
BINT7
NDUPN
DOBIND
FALSE
SWAP
FPTR2 ^ZBits
ONE_DO
::
3GETLAM
DUP
FPTR2 ^QAdd
5GETLAM
ID x00F
ROTDUP
FPTR2 ^ZIsOne?
NOTcase
::
5UNROLL
3DROPTRUE_
ExitAtLOOP
;
2DROP
Z3_
6GETLAM
FPTR2 ^ZSQ_
FPTR2 ^RMULText
7GETLAM
FPTR2 ^QAdd
1GETLAM
FPTR2 ^QMul
FPTR2 ^QMul
5GETLAM
FPTR2 ^ZMod
DUP
FPTR2 ^ZSQ_
2GETLAM
FPTR2 ^QMul
6GETLAM
DUP
FPTR2 ^QAdd
FPTR2 ^QSub
5GETLAM
FPTR2 ^ZMod
6GETLAM
OVER
6PUTLAM
FPTR2 ^RSUBext
FPTR2 ^QMul
3GETLAM
FPTR2 ^RNEGext
FPTR2 ^SWAPRSUB
5GETLAM
FPTR2 ^ZMod
3PUTLAM
ISTOP-INDEX
#1-
FPTR2 ^ZBit?
NOT?SEMI
6GETLAM
4GETLAM
FPTR2 ^QSub
5GETLAM
ID x00F
ROTDUP
FPTR2 ^ZIsOne?
NOTcase
::
5UNROLL
3DROPTRUE_
ExitAtLOOP
;
2DROP
Z-1_
3GETLAM
Z1_
FPTR2 ^QSub
ROT
FPTR2 ^QMul
5GETLAM
FPTR2 ^ZMod
DUPDUP
FPTR2 ^QMul
2GETLAM
FPTR2 ^QMul
6GETLAM
FPTR2 ^QSub
4GETLAM
FPTR2 ^QSub
5GETLAM
FPTR2 ^ZMod
DUP
6PUTLAM
4GETLAM
FPTR2 ^QSub
FPTR2 ^QMul
FPTR2 ^QSub
5GETLAM
FPTR2 ^ZMod
3PUTLAM
;
LOOP
SWAPDROPDUP
?SKIP
::
6GETLAM
SWAP
;
ABND
;
x00A
::
Z1_
OVER
ID x00C
4PICK
ID x00C
Z1_
FPTR2 ^QAdd
Z2_
FPTR2 ^ZNMax
::
BEGIN
2DUP
Z<
case
COLA_EVAL
::
DUP
4ROLL
FPTR2 ^RMULText
3UNROLL
Z1_
FPTR2 ^RADDext
;
AGAIN
;
2DROP
SWAPROT
Z2_
FPTR2 ^ZNMax
::
BEGIN
FPTR2 ^Prime+
2DUP
Z<
case
COLA_EVAL
::
DUP
4ROLL
FPTR2 ^RMULText
3UNROLL
;
AGAIN
;
2DROP
;
x00B
::
%ABS
%3
%MAX
%LN
DUP
%LN
%*
%SQRT
%EXP
;
x00C
::
DUP
Z2_
Z<
?SEMI
Z2_
OVER
FPTR2 ^Z>ZH
FPTR2 ^ZBits
SWAPDROP
#2/
#1+
FPTR2 ^RP#
ZEROSWAP
BEGIN
SWAPDROPDUP
3PICKOVER
FPTR2 ^ZDIVext
DROP
FPTR2 ^QAdd
Z2_
FPTR2 ^ZDIVext
DROP
2DUP
Z>
NOT_UNTIL
DROPSWAPDROP
;
x00D
::
FPTR2 ^3LAMBIND
Z0_
1GETLAM
FPTR2 ^Z2BIN
#1+_ONE_DO
"Curve #: "
INDEX@
#>$
&$
BIGDISPROW3
3GETLAM
BINT2
ZERO_DO
%RAN
% 999999999999.
%*
%IP
FPTR2 ^R>Z
OVER
FPTR2 ^ZMod
SWAPLOOP
3UNROLL
ZINT 27
OVER
BINT2
FPTR2 ^RP#
FPTR2 ^QMul
Z4_
4PICK
BINT3
FPTR2 ^RP#
FPTR2 ^RMULText
FPTR2 ^QAdd
4PICK
FPTR2 ^ZGcd
FPTR2 ^DupZIsOne?
ITE
::
DROPSWAP
3UNROLL
2GETLAM
ID x008
DUP
Z1_
Z>
OVER
3GETLAM
Z<
ANDcase
ExitAtLOOP
DROP
;
::
ROTROT2DROP
ExitAtLOOP
;
LOOP
ABND
FPTR2 ^DupQIsZero?
?SEMI
ROTDROP
;
x00E
::
DUP
FPTR2 ^Z>R
ID x00B
%2
%SQRT
%NROOT
%CEIL
FPTR2 ^R>Z
;
x00F
::
BINT0
3UNROLL
BEGIN
ROT#1+UNROT
DUPUNROT
FPTR2 ^ZDIVext
SWAP
4UNROLLDUP
Z0_
EQUAL
UNTIL
DROP
ZINT1_0_
4ROLL
ZERO_DO
DUPUNROT
5ROLL
FPTR2 ^QMul
FPTR2 ^QSub
LOOP
3PICK
FPTR2 ^ZIsNeg?
NOT?SEMI
BINT3
ZERO_DO
ROT
FPTR 6 4FB
LOOP
;
RE: HP 50G: Elliptic Curve Integer Factorization Programme - Gerald H - 07-04-2015 05:46 AM
Here the results of some factorizations of semi-primes composed of two factors with approx the same number of digits on emu48 on my computer, processor Intel(R) Core(TM) i7-4790 CPU @3.60 GHz, 4 Core, 8 logical processors.
First column is log to base 10 of input, second is time required to factorize in seconds.
The stats return a correlation coefficient of
0.6106
for the best fit of
T = 2.6759E-8*X^7.4441.
Conclusion: If no one, not even you, can come up with improvements or programme some part, especially IEGCD, in machine language, the programme is hopelessly slow.
18.0146 79.807
18.8923 98.5524
18.8975 10.0884
19.3222 36.252
19.4054 274.8845
19.4084 85.2894
19.4254 441.4695
19.6145 179.0726
19.7376 238.6617
19.8716 129.8376
20.4267 402.8607
21.2936 107.4248
21.3072 22.8505
21.3146 1662.9108
21.4127 60.436
21.425 222.3395
21.5316 42.5278
21.6174 60.3276
21.6857 192.4299
21.7322 182.1733
22.8705 57.5834
23.0025 540.8728
23.0466 730.3448
23.2181 504.7317
23.219 282.411
23.3225 1180.345
23.5486 996.9871
23.8556 5.2686
23.8902 524.1971
23.9313 5568.984
23.9404 1163.9684
24.0769 1983.0992
24.3113 1565.413
24.3773 1368.266
25.1759 3049.3097
25.3486 927.7865
25.8893 1080.844
26.33 3898.1266
26.9381 5411.0289
27.4156 304.9012
27.6004 477.2427
27.6311 1142.7007
27.7274 402.4984
28.0436 7964.2211
28.6526 493.1255
28.7634 5552.1494
28.8949 6964.2645
29.022 1977.3912
29.1465 18679.9346
29.3683 5317.1396
29.3936 2975.8624
29.4633 2270.5417
29.4973 5707.9138
29.5137 586.6985
29.5154 142.7861
29.5888 18.1981
29.6677 19448.0819
29.6937 6542.9614
30.8504 20809.2253
31.6527 317.5496
|