A benchmark comparing ECM and triangle number factoring.

As a test I chose 2 equal length primes of 309
digits each with their ratio close to but less than (2).

My Python triangle number factoring program found the key
smaller triangle number in less than 40 seconds with just
over 4,234,121 iterations.

This program just uses a summing of the difference
of the triangle number that resides on the same index
that the semi-prime composite resides on.
Then increments by one to the next index plus
the difference will equal the starting sum then as the
iterations of each next index is added to this sum
until the sum equals a triangle number that
will be smaller than the original index triangle number.

The program just needs two values, the first difference
sum + the starting index which is the next index after
the composites index.

This smaller sum after many iterations will stop when
the program reveals a triangle number.
This is taken and added too the semi-prime, which the
program does not do for program simplicity.
This will equal a larger triangle number.
This larger triangle number is the target.
Then subtract the index of the smaller triangle number
from the target index and if odd will reveals one of the
factors.
If even just divide by 2 and it will produce the smaller
factor.

I entered this semi-prime composite on Dario's ECM
calculator and its still searching for the 2 factors
over 3 hours and at curve 157.
It hasn't' even found the 2 unknowns yet. Mine in less
than 40 seconds to find the smaller key triangle number.
Add a few minutes more and the semi-prime is factored.
These semi-primes where the ratio is close to (2) should
produce these factors very fast using ECM.

This is not a trivial semi-prime where the
(sqrt(semi-prime))/(sqrt(2)) has a difference this much
less than the smallest factor in this semi-prime.
Difference =
2.7589227391542147919580590602135707844050024634130020812
437926010661488747768086722197273839872324702343001905435
514487097315962132908536894963882590911220768e+157

Which means the smallest factor in my semi-prime is closer to the (sqrt(semi-prime))
or > (sqrt(semi-prime))/(sqrt(2))

Maybe this is why ECM is having a time trying to get these factors.

Here are the two primes with 309 digits each that are
the factors of the semi-prime I used in the benchmark test!

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859

359538626972463181545861038157804946723595395788461314546860162315465351611001926265416954644815072042240227759742786715317579537628833244985694861278837891845969618258052648190195896371115988140369645820920259833633655409693853416059037125722165175517329013747430538531505228028427798462090857128884811860889

Dan

Ps
ECM is still cranking after 3hrs and 15 minutes and still
only showing that the 617 digit is a composite.
What gives?
.

Relevant Pages

  • Re: Dik T. Winter says: Definition: sum{i in N} i = 0
    ... A figure is called triangle* iff ... sum summs infinitely many summands. ... Induction to the infinite is valid and sound, as long as measure is preserved. ... balls naturally numbered from 1, we insert balls 10n-9 through 10n, and remove ball n at each iteration n. ...
    (sci.math)
  • Putnam Exam 2004 -- [*SPOILERS*]
    ... triangle increases with the length of any side as long as the angle ... the first column of the matrix in the determinant is a multiple of u_n, ... S= the sum of the x_i with i in T. Then consider ... 2a/has perimeter and area equal. ...
    (sci.math)
  • Re: Putnam Exam 2004 -- [*SPOILERS*]
    ... the area and side lengths of a triangle satisfy ... > the first column of the matrix in the determinant is a multiple of u_n, ... > we can then divide through to make the constant be 1. ... > can divide X by c to get a sum which is a multiple of x1, ...
    (sci.math)
  • Re: Dik T. Winter says: Definition: sum{i in N} i = 0
    ... triangle is a figure without any corner, ... sum summs infinitely many summands. ... There is an obvious difference of your meaning of "proof" and the common ... "It is not very difficult to evaluate infinite sums. ...
    (sci.math)
  • Re: Question about the way Smith defines frames of an input signal for the STFT
    ... understanding this may have to do with that "equals sign with triangle ... process is performed at each frame with the input data redefined. ... of the data input set. ...
    (comp.dsp)
Loading