Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA.

It basically works like this:

  • You reverse the digits in $N$, let's call this value $Ň$

  • You pick an integer, $k$ (normally 1, but can be other values)

  • A variable, $Δ$, can be any integer value between the square root of $N$ and the square root of $Ň$

You then calculate four values, if any return a value other than 1, then you have one of your prime factors:

  • $gcd[N, (k × Ň) + Δ]$
  • $gcd[N, (k × Ň) - Δ]$
  • $gcd[N, (Δ × Ň) + k]$
  • $gcd[N, (Δ × Ň) - k]$

Using this algorithm and the GMP library, it would factor 18014417929109603 in 3 seconds.

I was wondering if there were any other algorithms which were faster than this, but just as easy to implement? I know the GNFS is the fastest, but it is also incredibly hard to implement.

share|improve this question
2  
Did you look into the naive quadratic sieve? It's reasonably sane to implement and kind of fun. There's also a good open-source implementation you can look into, MSieve. On a related note, the pdf feels and reads like snake oil... I whipped up a Python implementation and while 18014417929109603 factored in 5 seconds, 31226716938897156373 at least takes longer than 10 minutes. –  Thomas Oct 28 '12 at 0:00
    
Huh, that paper's author doesn't even know that an equation should have an $=$ sign in it. Also, there is no reasoning that the decimal system is in any way preferable for calculating the digit-reversal $Ň$ (why not use binary, ternary, 13-ary, ... system)? –  Paŭlo Ebermann Oct 28 '12 at 0:43
    
I've looked into the quadratic sieve, but I'm not a mathematician and find it hard to understand. It looks very promising if I could get it to work though. –  Sam Kennedy Oct 28 '12 at 1:13
add comment

2 Answers 2

up vote 6 down vote accepted

Pure nonsense. For choosing the random $\Delta$ between $\sqrt{\min(N, Ň)}$ and $\sqrt{\max(N, Ň)}$ there are too many possibilities for it to work. For example whenever the first and last digits of $N$ differ, you get something like $\frac{1}{10} \cdot \sqrt N$ possibilities (the exact formula doesn't matter).

So you can replace the first formula $gcd[N, (k × Ň) + Δ]$ with $k=1$ by this one: $gcd[N, \Delta]$. Try all $\Delta$ between $1$ and $\sqrt N$, the number of possibilities is within some small factor.

Compared to the division, computing $gcd(N, x)$ has the advantage that at each attempt you try all factors of $x$. This is good in case $N$ has some small factors, which in case of RSA is surely not true.

I see no advantage of the linked algorithm to trial division. Trying all primes up to $\sqrt N$ is probably faster, terminates also when $N$ is prime, and has a bounded time.

Summary: pure nonsense.

share|improve this answer
    
Are either of these better alternatives? coolissues.com/mathematics/Goldbach/goldbach.htm mirlabs.info/cddump/data/4437a108.pdf –  Sam Kennedy Oct 28 '12 at 2:05
1  
This doesn't really answer the title question though, even if it refutes the proposed algorithm. –  Thomas Oct 28 '12 at 2:27
    
I'm no expert in cryptography and have spent only few minutes reading it, but it looks bad too. Unfortunately, whenever it looks like it needs no advanced math, it can't be right (unless it's one of the known algorithms). Note that something as simple as Pollard's rho can factor a number like the above in a few milliseconds. –  maaartinus Oct 28 '12 at 2:27
    
@SamKennedy The second document is full of grammatical errors and references the original one, which pretty much seals its fate as crackpot material. The first one claims to solve three open mathematical questions (goldbach conjecture, twin primes conjecture, and the ubiquitous factoring problem) through a single quadratic equation.. not buying it. –  Thomas Oct 28 '12 at 2:33
    
@Thomas: Doesn't it? I'm basically saying that the choice of Ň gains nothing. So yes, there are better algorithms out there, and for number as small as the given one it's easy to implement. –  maaartinus Oct 28 '12 at 2:34
show 1 more comment

Yes there are several algorithms, as simple or even simpler as the proposed algorithm, that are expected to factor $N$ much faster. The simplest and oldest is the Sieve of Eratosthenes (which works for any $N$); there's also Fermat's factoring method, preferably with the easy sieve improvement to recognize squares efficiently (which works when $N$ is the product of two primes $P$ and $Q$ with $|P-Q|$ of the same order of magnitude as $\min(P,Q)$, which seems the aim of the article). Arguably, the more efficient Pollard's Rho is on the other side of the simplicity threshold.

The algorithm proposed in the question and article essentially attempts to factor a semi-prime $N=P\cdot Q$ by repeatedly picking a pseudo-random integer $R$ smaller than a few times $N$, and computing $G=\mathtt{GCD}(N,R)$, until that is not $1$. The last $G$ is generally either $P$ or $Q$ (the only other possibility, $G=N$, is rare).

Odds of success at each $\mathtt{GCD}$ test is about $1/P+1/Q$ (thus less than $N^{1/2}/2$ steps are expected). For a 1024-bit RSA key odds of success per $\mathtt{GCD}$ may be $2^{-510}\ll10^{-153}$. The distributed attack envisioned at the end of the article expects to make $10^{14}$ such $\mathtt{GCD}$ tests, and thus has odds less than $10^{-139}$ to succeed. Hélas, I have no reason to doubt that the article was accepted in an IEEE-endorsed conference despite absence of practical interest and discussion about its (in-)efficiency.

share|improve this answer
    
I quickly wrote a program using Pollard's Rho algorithm, it's much faster than than the original (factored 31226716938897156373 in 0.055 seconds). I have some questions about Pollard's Rho algorithm now, should I ask here or start a new question with the relevant topic? –  Sam Kennedy Oct 28 '12 at 16:29
    
@Sam Kennedy: Congratulations for implementing Pollard's Rho (I suggest a new question if you want info about that). Logical next steps may be Pollard's p-1 and improvements; then Quadratic Sieve and variations (MPQS, SIQS), where earlier work is reused to some degree; or Pollard's p+1 then ECM. –  fgrieu Oct 29 '12 at 9:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.