Arturo Magidin wrote:
> In article <1143563678.312272.25290@u72g2000cwu.googlegroups.com>,
>  <mluttgens@wanadoo.fr> wrote:
> >
> >Pubkeybreaker wrote:
> >> mluttgens@wanadoo.fr wrote:
> >> > Tim Peters wrote:
> >>
> >> > Let z^2 = x^2 + N, where z, x and N are integers.
> >> > Knowing N, is there no formula giving x ?
> >>
> >> Of course there is. Assume  N is odd, WLOG.
> >>
> >> Let  m =  product  p_i ^  a_i      for all primes p_i < sqrt(N)   and
> >> all a_i
> >> such that p_i ^a_i < sqrt(N)
> >>
> >>
> >> Then  x =    (  GCD(2^m -1, N)   -   N/GCD(2^m-1, N)/2
> >>
> >> Of course, computing   2^m-1  mod N   will be computationally
> >> expensive.....
> >
> > Is computing   2^m-1  mod N   computationally less expensive than
> > trying successive values of x until sqrt(x^2 + N) - INT (sqrt(x^2 + N) = 0 ?
>
> Computing b^n mod N is O(log(n)log^2(N)); Subtracting 1 is easy.
>
> I don't know how long it takes to do a square root. But the expected
> number of tries until you hit a perfect square for large N is pretty
> large.

Sure, but logarithms also take some computing time.

Marcel Luttgens