Re: Surrogate factoring demonstrated

jstevh_at_msn.com
Date: 02/26/05 

Date: 25 Feb 2005 15:24:35 -0800

jstevh@msn.com wrote:
> I think it'd help to show an actual example of surrogate factoring,
> which of course is a picked example, of a case where it works.
>

I'm still working on the algorithm and seeing what it will factor.

Here's one I just did.

M = 116565983987934769

T = 1331674354105829165393067963530771325

T^6 factored is

 ( 3^18 )( 5^12 )( 89^6 )( 479^6 )( 137573^6 )( 214213^6 )(
146655731^6) (10707563851^6 )

Iterations: 555547

Max is 8 times that or 4,444,376

Time/iteration: <deleted>
Number factored.
Initial Factorization:
f_1=247816937
f_2=470371337
Now checking its factors...
moving up a level

Success!
Factors:
 ( 247816937 )( 470371337 )
Product: 116565983987934769

In coming is 116565983987934769
Processing time: <deleted>
Number of digits: 18
bitLength=57

I'm still working on my idea about blocking primes, so I'm forcing in a
factor of 15 into T.

I'm trying to find a number the current algorithm does NOT factor.

James Harris

Relevant Pages

  • beta version of Victor Shoups book, "A Computational Introduction to Number Theory and Algebra&
    ... Computing with Large Integers ... The Basic Euclidean Algorithm ... Factoring and Computing Euler's phi-Function are Equivalent ... The Existence of Finite Fields ...
    (sci.crypt)
  • Re: Ultimate check, new way to factor or not?
    ... It's commonly known as a the "factoring sieve" and Fermat showed that ... It is listed as "algorithm ... "factoring with sieves" on pp.389. ... > when it defies the mathematics. ...
    (sci.crypt)
  • Re: Surrogate factoring demonstrated
    ... > The algorithm is so simple that it's amazing how often it does work. ... bits from T while multiplying the number of divisors of the cofactor of T ... > anything, but if you try it, you will be amazed at the high factoring ... Why don't you try running surrogate factoring by hand, on paper, using no ...
    (sci.math)
  • Re: Surrogate factoring demonstrated
    ... > The algorithm is so simple that it's amazing how often it does work. ... bits from T while multiplying the number of divisors of the cofactor of T ... > anything, but if you try it, you will be amazed at the high factoring ... Why don't you try running surrogate factoring by hand, on paper, using no ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)