2

recently I've been looking at the interesting problem of RSA encryption and attempting to understand what it's so hard to find the factors then I came across this page.

Can anyone comment on it's validity?

http://www.naturalnumbers.org/Qfactor3.html

Derek James
  • 31
  • 4
  • 3
    Well, yes. If $\lceil \sqrt{N}\rceil^2 - N$ is a square, say $k^2$, then Fermat factorisation immediately finds two factors. If it's a semiprime, these are the two prime factors. However, $\lceil \sqrt{N}\rceil^2 - N$ is almost never a square. – Daniel Fischer Nov 25 '13 at 13:40
  • The factors of semi prime $N$ are found among one of the equations $([\sqrt N]+k)^2+N=x^2$ for $k\in[1,\sqrt N]$. For large $N$ this is practically as difficult as factoring $N$ directly. – abiessu Nov 25 '13 at 13:48
  • I love the amount of knowledge here!

    What about prime numbers, is it easy to determine if a number is Prime with 2048 bits, or, is it no different than just factoring iteratively ?

     – Derek James Nov 29 '13 at 15:06
  • Primality testing is a much much easier problem than factoring. – Fixee Sep 07 '15 at 13:52

0 Answers0