(50G) Elliptic Curve Integer Factorization Programme
06-25-2015, 07:49 AM (This post was last modified: 06-15-2017 01:41 PM by Gene.)
Post: #1
 Gerald H Senior Member Posts: 1,426 Joined: May 2014
(50G) Elliptic Curve Integer Factorization Programme
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 ;
07-04-2015, 05:46 AM
Post: #2
 Gerald H Senior Member Posts: 1,426 Joined: May 2014
RE: HP 50G: Elliptic Curve Integer Factorization Programme
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)