echelon factoring algorithm


Here’s a specific example that’s missing from everyone’s repertoire, when it comes to having a general factoring method:

Example one

Let N=7477=61*127, and N88.01, and compute the following:

M=2(7477+1)=27478

now, X=mod(M,N-1), and gcd(X-[20],N), gcd(X-[21],N),…, gcd(X-[2k]2,N) such that [2k]2N.

It’ll find the factor, but we would have to use George Woltman’s FFT’s method to compute the M’s for larger numbers. In this example, Mmod(N-1)=246, and gcd(246-2,N)=61.

Also, calculate ln(7477)8.955, so, you could continue to check

gcd(X-[31],N),,gcd(X-[3k],N)

such that [3k]2sqrt(N), and gcd(X-[52]) such that [5k]2N, if a factor hasn’t shown itself. Unlike primality-proving, finding the factor would be the ”proof-in-the-pudding”!

We’d have the answer; that’s for sure! I call it a step or ”echelon”-factoring algorithm.

Example two

1500450271*5915587277=8876044532898802067

You’d use this fact to get past the first modpow()

N+1=8876044532898802067+1=22*3*(24+1)*(2*34*(2*(22*5*(22*53*(2*(22*7+1)+1)+1)+1)+1)*(23*3*52*7*(2*(2*(2*5+1)+1)+1)*(27*32+1)+1)+1)

M=2(8876044532898802067+1)

k=log2[8876044532898802067]=15 so, 1 huge step and 31 base two subtractions, and some base 3, 5, …, 43, etc! … find mod(2N+1,N-1), and gcd(M-[20],N), gcd(M-[21],N),gcd(M-[230],N), etc. and you’ll have a factor.

It’s the best, shortest method that you’ll ever use to check for factors, and it’s definitive, assuming we can conquer the enormous modular calculation!

In this last example, the number of steps is comparable to the 2 times 16th Root of N for the base 2 calculations alone. I couldn’t do the calculations by hand.

Title echelon factoring algorithm
Canonical name EchelonFactoringAlgorithm
Date of creation 2013-03-22 19:36:43
Last modified on 2013-03-22 19:36:43
Owner leavemsg2 (21852)
Last modified by leavemsg2 (21852)
Numerical id 11
Author leavemsg2 (21852)
Entry type AlgorithmMathworldPlanetmath
Classification msc 11Y05
Synonym step
Synonym echelon
Defines factoring algorithm